Exerciții rezolvate: Liste

Exercițiul 1. Implementați o funcție de concatenare a două liste.

Soluție. OCaml are operatorul de concatenare și funcția echivalentă List.append . (Atenție, List.concat, face altceva, e un alt nume pentru List.flatten, care face o listă dintr-o listă de liste: List.flatten [[1;2;3];[4];[5;6]] = [1;2;3;4;5;6] .) Implementând însă singuri concatenarea, putem vedea mai bine că ea nu este o operație elementară (deoarece nu avem acces direct la sfârșitul listei, ci doar la primul element). Trebuie să parcurgem până la capăt prima listă, și apoi, revenind, să adăugăm elementele ei (de la ultimul spre primul) în capul celei de-a doua liste:

let rec append l1 l2 = match l1 with
  | [] -> l2
  | h :: t -> h :: append t l2

val append : 'a list -> 'a list -> 'a list = <fun> (* tipul funcției, dedus de OCaml; nu se scrie în program *)
Potrivirea de tipare (cu match ... with ...) și parcurgerea se face aici după prima listă: dacă e vidă, nu e nimic de făcut (se returnează lista a doua); altfel, știm că primul element din rezultat va fi capul primei liste, și pentru rest, trebuie concatenată coada primei liste cu lista a doua. Se face un apel recursiv pentru fiecare element, și rezultatul (compunerea cap-coadă) se calculează abia la revenirea din apel. Deci funcția nu e recursivă la dreapta, și consumă stivă proporțional cu lungimea primei liste. Din acest motiv, evităm pe cât posibil concatenarea pentru liste lungi.

Prelucrarea se poate exprima direct și cu List.fold_right, care parcurge lista de la coadă la cap. Funcția de prelucrare la fiecare pas e foarte simplă: adăugarea elementului curent la coada listei (rezultatul acumulat). Valoarea inițială pentru parametrul acumulator e tocmai lista a doua. Deci,

let append l1 l2 = List.fold_right (fun h t -> h :: t) l1 l2
Cum avem aceleași argumente în stânga și în dreapta, ele se pot omite (f x = g x e echivalent cu f = g, două funcții sunt egale când valorile în orice punct sunt egale):
let append = List.fold_right (fun h t -> h :: t)

Exercițiul 2. Implementați o funcție countif care ia ca parametru o funcție f cu valori boolene și o listă și returnează numărul de elemente pentru care funcția f e adevărată.

Soluție Funcția va fi asemănătoare cu List.filter, care deasemenea ia ca parametru o funcție booleană de element și returnează lista tuturor elementelor care satisfac condiția, de exemplu:
List.filter (fun x -> x > 3) [1;5;4;-8;6;-3] care returnează lista numerelor mai mari decăt 3: [5;4;6] .
(de fapt, funcția cerută e lungimea listei care ar fi returnată de List.filter, dar ar fi ineficient să construim explicit lista și s-o parcurgem încă o dată).

În expresia de mai sus, e important de înțeles că o funcție cu valori boolene (adevărat sau fals) înseamnă o condiție asupra argumentului (adevărat, dacă o îndeplinește, fals, dacă nu). Funcția List.filter (ca și cea pe care o vom scrie) poate lucra cu orice astfel de funcție dată ca parametru, de exemplu fun x -> x mod 2 = 0 (numărul e par), fun (x, y) -> x < y (perechea are primul element mai mic decât al doilea), fun s -> String.length s > 5 (șirul are mai mult de 5 caractere), etc. Dacă notăm o astfel de funcție cu f, a verifica condiția pentru o anumită valoare înseamnă a da lui x acea valoare, adică a aplica funcția lui x: f x .

Putem implementa funcția countif direct: lista vidă nu are elemente, deci nici elemente care satisfac vreo condiție (oricare ar fi aceasta). Altfel, numărăm câte elemente din coada listei satisfac condiția (recursiv, cu aceeași funcție), și adăugăm 1 sau 0, după cum capul listei o satisface sau nu.

let rec countif f = function
  | [] -> 0
  | h :: t -> countif f t + if f h then 1 else 0

val countif : ('a -> bool) -> 'a list -> int = <fun>
Această funcție face adunarea după ce revine din apelul recursiv, deci în momentul ultimului apel, fiecare din cele anterioare va fi în așteptarea rezultatului și consumă loc pe stivă (în total, proporțional cu lungimea listei). Acest lucru nu e de dorit pentru liste foarte lungi. Rescriem deci funcția pentru a fi final recursivă, folosind un parametru suplimentar care acumulează rezultatul parțial (elementele numărate pânâ în acel punct). În acest caz, cum countif_t nu mai are nimic de făcut după apelul recursiv decât să returneze tocmai rezultatul acestuia, compilatorul poate implementa apelul ca un salt, iar recursivitatea ca un ciclu, fără a se mai consuma memorie pe stivă pentru parametri, adresă de revenire, etc.
let rec countif_t r f = function
  | [] -> r
  | h :: t -> countif_t (r + if f h then 1 else 0) f t

val countif_t : int -> ('a -> bool) -> 'a list -> int = <fun>
Calculul e același: se adună 1 sau 0 după cum elementul curent satisface sau nu condiția (funcția booleană f), dar se face înainte de apelul recursiv, actualizând valoarea parametrului acumulator r .
Funcția countif_t trebuie apelată inițial cu valoarea 0 pentru parametrul r: inițial nu s-a parcurs și numărat niciun element.
Pentru a face vizibilă doar funcția cerută countif (cu un parametru funcție și altul listă), putem declara funcția auxiliară countif_t în interior, cu let ... in ... ; atunci countif_t nu mai are nevoie de parametrul f, întrucât el nu se modifică, și îl poate folosi pe cel al funcției exterioare.
let countif f =
  let rec countif_t r = function
    | [] -> r
    | h :: t -> countif_t (r + if f h then 1 else 0) t
  in countif_t 0
Putem să implementăm countif și folosind List.fold_left. Trebuie doar să definim funcția care actualizează rezultatul parțial acumulat, adunând 1 sau 0 după cum elementul curent satisface sau nu condiția f ; valoarea inițială de la care se pornește e 0. Parametrul listă peste care se iterează ar apare ultimul și în stânga și în dreapta, deci se poate omite în definiție.
let countif f = List.fold_left (fun r e -> r + if f e then 1 else 0) 0

Cu oricare din variante, putem apela, de exemplu countif (fun x -> x mod 2 = 0) [1;5;2;-6;3;4] care dă lista tuturor elementelor pare: [2; -6; 4] .

Exercițiul 3. Construiți lista de cifre în baza 10 a unui întreg, de la cea mai semnificativă la cea mai puțin semnificativă (a unităților).

Soluție. Urmăm același tipar de prelucrare a numerelor: un număr e o cifră (n mod 10), precedat eventual de alt număr (n/10) . O exprimare directă ar concatena lista cifrelor obținută recursiv pentru n/10 la ultima cifră a numărului (de fapt, lista cu unic element cu această cifră). Pentru cazul de bază, dacă numărul e de o singură cifră, returnăm doar lista cu acea cifră, sau, echivalent, concatenăm lista vidă cu ea.

let rec listcif n = (if n < 10 then [] else listcif (n/10)) @ [n mod 10]

val listcif : int -> int list = <fun>
Din nou, această funcție nu e final recursivă, deci încercăm transformarea ei. Folosim un parametru suplimentar (inițial lista vidă) pentru a acumula lista de cifre, începând de la coadă. La fiecare pas, ultima cifră va fi adăugată ca și cap al vechii liste. Dacă am ajuns la un număr e de o singură cifră, ne oprim și returnăm lista acumulată; altfel, se apelează recursiv funcția cu lista actualizată și restul numărului (n/10).
let rec listcif_t tail n =
  let t1 = n mod 10 :: tail in if n < 10 then t1 else listcif_t t1 (n/10)

val listcif_t : int list -> int -> int list = <fun>
Putem "ascunde" această funcție auxiliară folosind let ... in ... și lăsând vizibilă doar funcția cerută, cu parametru număr, care o apelează pe cea auxiliară cu lista vidă ca valoare inițială pentru parametrul în care se acumulează cifrele.
let listcif =
  let rec listcif_t tail n =
    let t1 = n mod 10 :: tail in if n < 10 then t1 else listcif_t t1 (n/10)
  in listcif_t []
În final, putem defini o funcție care funcționează corect și pentru numere negative, construind lista cifrelor pentru valoarea absolută.
let listcif_int n = listcif (abs n)

Exercițiul 4. Implementați o funcție fromto a b care construiește lista tuturor întregilor de la a la b inclusiv.

Soluție Structura recursivă a problemei e simplă: dacă a > b, rezultatul e lista vidă. Altfel, identificăm un element și obținem recursiv restul: lista conține unul din capetele intervalului, la care se adaugă lista întregilor din intervalul (de lungime cu 1 mai mică) obținut prin eliminarea capătului.

Mai departe, soluția depinde (surprinzător de mult!) de capătul de la care parcurgem intervalul. Dacă pornim cu a, funcția se scrie mai direct, construind lista rezultat din primul element, și coada listei (provenind din apelul recursiv):

let rec fromto a b = if a > b then [] else a :: fromto (a+1) b

val fromto : int -> int -> int list = <fun>
Funcția nu este însă final recursivă (tail recursive): construcția listei cu :: se face după revenirea din apel. Deci, la momentul ultimului apel (cel mai adânc) e nevoie de memorie pe stivă pentru toate apelurile anterioare, proporțional cu lungimea intervalului [a, b].
Încercarea de a folosi funcția pe intervale lungi (de exemplu List.length (fromto 1 1000000) ) va depăși de regulă dimensiunea stivei (încercați!).

Rescriem funcția în mod final recursiv, folosind un parametru suplimentar r pentru a acumula lista rezultat. În acest caz e natural să descompunem intervalul pornind de la capătul din dreapta: aceasta e plasat în capul listei parțial construite (inițial vidă), care conține deja elementele din dreapta lui. Când intervalul a devenit vid prin micșorare, rezultatul e gata construit în lista r și poate fi returnat.

let fromto a = 
  let rec fromtob r b = 
    if a > b then r else fromtob (b::r) (b-1)
  in fromtob []
Apelul List.length (fromto 1 1000000) se încheie cu succes acum (și chiar pentru numere mult mai mari).

Exercițiul 5*. Sortați o listă prin interclasare (mergesort), despărțind lista în două jumătăți, sortând recursiv fiecare din ele, și apoi interclasând cele două liste sortate.

Rezolvăm succesiv cele două părți componente: despărțirea și interclasarea, pentru a le combina apoi în funcția recursivă de sortare.

Despărțirea unei liste e cea mai simplă: nu avem alte cerințe, elementele pot fi puse în orice ordine; vom produce o pereche de liste cu lungimi egale sau aproape egale (± 1) . Pentru a putea lucra cu liste lungi, scriem o funcție final recursivă, acumulând rezultatul într-un parametru de tip pereche de liste (inițial vide). Dacă lista are cel puțin două elemente, acestea sunt fiecare plasate într-una din jumătățile rezultatului. Dacă lista are un singur element, e adăugat la prima listă din rezultat. Pentru lista vidă, se returnează rezultatul acumulat.

let split =
  let rec splitr (r1, r2) = function
    | e1::e2::l -> splitr (e1::r1, e2::r2) l
    | [e1] -> (e1::r1, r2)
    | [] -> (r1, r2)
  in splitr ([], [])

val split : '_a list -> '_a list * '_a list = <fun>
Pentru interclasarea a două liste ordonate, examinăm capetele acestora (dacă ambele sunt nevide). Cel mai mic va fi și primul element din rezultat; pentru rest, interclasăm recursiv perechea de liste rămasă după ce am eliminat elementul cel mai mic din capul listei de care aparține. Dacă una din liste e vidă, rezultatul interclasării e cealaltă listă: putem scrie acest lucru folosind două tipare (simetrice unul celuilalt), cu același rezultat.
let rec merge = function
    | ([], l) | (l, []) -> l
    | (h1::t1 as l1, (h2::t2 as l2)) ->
      if h1 < h2 then h1 :: merge (t1, l2) else h2 :: merge (l1, t2)

val merge : 'a list * 'a list -> 'a list = <fun>
Cu sintaxa tipar as nume (de exemplu h1 :: t1 as l1) putem să ne referim cu un nume la întregul obiect care se potrivește tiparului, când avem nevoie de el ca atare, nu doar de părțile lui componente, de exemplu, în merge (l1, t2) .

Funcția merge scrisă astfel e simplă, dar nu e final recursivă; mai mult, pentru sortare, va trebui s-o folosim repetat. Dacă însă cele două liste din perechea argument ar fi sortate invers față de sortarea dorită în rezultat (de exemplu, ([5;3;1;0], [10;6;-4]) când dorim o listă crescătoare), am putea construi în mod natural rezultatul în de la coadă la cap (punănd în listă întâi pe 10, apoi [6;10], [5;6;10], etc.).

Scriem atunci o funcție mergecmp parametrizată după sensul comparării, cu o funcție cmp de tipul 'a -> 'a -> bool, cum sunt operatorii < și > . Ea are deasemenea un parametru r în care acumulează rezultatul parțial. Dacă una din listele din pereche e vidă, elementele celeilalte trebuie adăugate în ordine inversă la rezultat (cu funcția standard List.rev_append); altfel, dacă cmp h1 h2 (adică h1 e înainte de h2 în ordinea dorită, (<) h1 h2 sau altfel scris h1 < h2), atunci h2 e cel care trebuie adăugat la rezultat, pentru ca h1 să ajungă ulterior înaintea lui, etc.

let rec mergecmp cmp r = function
  | ([], l) | (l, []) -> List.rev_append l r
  | (h1::t1 as l1, (h2::t2 as l2)) ->
    if cmp h1 h2 then mergecmp cmp (h2::r) (t2, l1) else mergecmp cmp (h1::r) (l2, t1)

val mergecmp : ('a -> 'a -> bool) -> 'a list -> 'a list * 'a list -> 'a list = <fun>
Ca deobicei, putem "ascunde" funcția cu parametrul auxiliar (acumulatorul r pentru rezultat), iar operatorul cmp rămâne ca parametru al funcției exterioare, care poate fi folosit și în interior:
let mergec cmp =
  let rec mergecmp r = function
    | ([], l) | (l, []) -> List.rev_append l r
    | (h1::t1 as l1, (h2::t2 as l2)) ->
      if cmp h1 h2 then mergecmp (h2::r) (l1, t2) else mergecmp (h1::r) (l2, t1)
  in mergecmp []

val mergec : ('a -> 'a -> bool) -> 'a list * 'a list -> 'a list = <fun>
Suntem acum gata să combinăm despărțirea și interclasarea pentru sortare. Mai trebuie să putem schimba la fiecare pas sensul în care sortăm (ca să avem rezultatul în ordine crescătoare, vrem jumătățile în ordine descrescătoare, și jumătățile jumătăților din nou în ordine crescătoare, etc.). Pentru asta, e suficient să schimbăm ordinea argumentelor funcției de comparare cmp :
let flip cmp x y = cmp y x

val flip : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c = <fun>
Deci, funcția flip cmp va efectua exact comparația opusă funcției cmp .

Rămâne faptul că split produce o pereche de liste, din care vrem să obținem o pereche de liste sortate, dar funcția de sortare lucrează pe o singură listă. Putem defini simplu o funcție pairmap care aplică o funcție elementelor unei perechi, și returnează perechea rezultatelor:

let pairmap f (x, y) = (f x, f y)

val pairmap : ('a -> 'b) -> 'a * 'a -> 'b * 'b = <fun>
Cu acestea, funcția dorită se scrie extrem de concis:
let rec mergesort cmp = function
  | _ :: _ :: _ as l -> mergec cmp (pairmap (mergesort (flip cmp)) (split l))
  | l -> l
Cazul recursiv e cel al listelor de cel puțin două elemente; tiparul _ :: _ :: _ as l ne asigură că lista are structura de două elemente urmate de coada listei, fără a le denumi, și folosind mai departe doar lista întreagă l . Cazul rămas e cel al listei de cel mult un element, care e deja sortată (indiferent de ordinea dorită). Prelucrarea se urmărește din interior spre exterior: lista se desparte într-o pereche de două liste (split l), asupra ambelor elemente ale perechii se aplică cu pairmap funcția mergesort (flip cmp) care le sortează în ordinea inversă celei dorite cmp pentru lista finală; perechea obținută e interclasată în ordinea dorită cu funcția mergec cmp .

Putem apela funcția: mergesort (<) [1; -4; 5; 100; -49; 43; 67; 2; 5; -9] si va produce lista sortată crescător: [-49; -9; -4; 1; 2; 5; 5; 43; 67; 100] .

Marius Minea
Last modified: Sat Oct 19 12:00:00 EEST 2013