Exerciții rezolvate: 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 *)

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

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>

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>

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

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>

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>

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 []

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>

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 []

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>

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>

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>

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>

let flip cmp x y = cmp y x

val flip : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c = <fun>

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>

let rec mergesort cmp = function
  | _ :: _ :: _ as l -> mergec cmp (pairmap (mergesort (flip cmp)) (split l))
  | l -> l

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] .