Liste

Modulul List (documentația OCaml)

Construirea de liste

1. Asemănător cu funcțiile din notițele de curs care construiesc lista cifrelor unui număr natural, scrieți:
a) funcții care construiesc lista cifrelor unui număr care satisfac o condiție anume (cifre impare, pare, mai mici decât 7, etc. la alegere), în ordine normală și inversă
b) o funcție care construiește lista cifrelor unui număr care satisfac o condiție dată ca parametru sub forma unei funcții cu tipul int -> bool.
c) Invers, dată fiind o listă de cifre, construiți numărul format doar din cifrele care respectă o condiție (dată ca parametru funcție cu tipul int -> bool). Rezolvați problema direct, recursiv, și apoi prin compunerea lui List.filter (selectarea cifrelor) cu List.fold_left (pentru construirea numărului).

2. Asemănător cu funcția fromto (din notițele de curs) care generează lista numerelor întregi dintr-un interval dat, scrieți o funcție care creează lista tuturor întregilor dintr-un interval dat, divizibili cu o valoare dată d.
Indicație: Găsiți cel mai mare număr divizibil din interval, și continuați pas cu pas.

3. a) Implementați funcția List.nth care returnează al n-lea element dintr-o listă.
Observați întâi în interpretor comportamentul funcției standard pentru valori ale lui n invalide (negative) sau prea mari (mai mari decât lungimea listei). Puteți produce excepția Invalid_argument mesaj apelând funcția invalid_arg mesaj, și excepția Failure mesaj apelând funcția failwith mesaj.
b) Implementați o funcție firstn care returnează o listă cu primele n elemente dintr-o listă dată.

4. Folosind funcțiile din modulul Random, scrieți o funcție care construiește o listă de n întregi aleatori, fiecare între 0 și b - 1.

Parcurgeri de liste

5. a) Implementați funcția List.filter folosind List.fold_right, urmând exemplul dat pentru List.map .
b) Implementați funcția List.exists care determină (returnează adevărat/fals) dacă există un element din listă care satisface o condiție (o funcție de element cu valoare booleană, dată ca parametru).
Implementarea poate fi asemănătoare cu cea a funcției mem de la curs. Puteți apoi exprima List.mem folosind List.exists ?

6. a) Implementați folosind List.fold_left 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ă.
b) Implementați similar o funcție sumif care calculează suma tuturor elementelor (presupuse întregi) pentru care funcția f e adevărată.

7. Implementați funcțiile List.split și List.combine care transformă o listă de perechi într-o pereche de liste, și invers.
Indicații: urmăriți din modulul List tipurile pe care trebuie să le aibă cele două funcții.
Scrieți tipare care combină liste și perechi, de exemplu (h1::t1, h2::t2) se potrivește cu o pereche de liste, ambele nevide. (a,b)::t identifică prima pereche dintr-o listă nevidă de perechi.
Pentru funcția split, va trebui să folosiți rezultatul apelului recursiv, adică o pereche de două liste. Și în let se pot folosi tipare: let (l1, l2) = split t in ...
Pentru funcția combine, care ia două argumente, le puteți combina pentru a folosi potrivirea de tipare pe perechi: let rec combine l1 l2 = match (l1, l2) with ...

8. Implementați funcția List.partition care ia ca parametru o funcție cu valori boolene și o listă și returnează o pereche de liste, cu elementele care satisfac, respectiv nu satisfac funcția f.
# List.partition (fun x -> x >= 5) [4;6;7;5;4;8;9] ;;
- : int list * int list = ([6; 7; 5; 8; 9], [4; 4])
Puteți să o scrieți cu una din prelucrările standard? Va fi final recursivă sau nu ?
Indicație: la fiecare pas, elementul curent se adaugă la una din listele din perechea-rezultat.

9. Scrieți o funcție care ia o listă de cifre și returnează valoarea numărului cu cifrele respective.

10. Scrieți o funcție care elimină duplicatele consecutive: ia ca parametru o listă și construiește o listă în care toate secvențele de elemente consecutive egale au fost înlocuite cu un singur element.
Indicație: puteți identifica prin tipar fragmente cu două elemente egale: e1 :: e2 :: t when e1 = e2

11. Scrieți o funcție care compară două liste după următoarea relație de ordine: o listă mai scurtă e "mai mică" decât una mai lungă; dacă lungimile sunt egale, ordonarea e determinată de prima pereche de elemente diferite. Evitați parcurgerea inutilă sau repetată a listelor. Funcția va returna un întreg negativ, 0 sau pozitiv în funcție de ordonarea celor două liste argument.

Sortarea prin interclasare

12. Scrieți o funcție care interclasează două liste, fiecare ordonată crescător, adică returnează lista cu elementele din ambele liste, ordonate.
Comparați primele elemente din ambele liste pentru a decide care va fi primul în rezultat, și apoi continuați cu listele rămase. Puteți da funcției ca parametru o pereche de două liste (l1, l2) și folosi un tipar pentru ambele elemente ale perechii:
let rec merge = function
  | (h1 :: t1, h2 :: t2) -> if h1 < h2 then ...
  | ... alte cazuri ... -> ...

13. Scrieți o funcție care desparte o listă în două liste a căror lungime diferă cu cel mult 1, punând alternativ câte un element în fiecare din liste. (Funcția va returna o pereche de liste).

14. 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. Folosiți funcțiile din cele două probleme anterioare.

Ce face funcția?

15. Încercând să folosească List.fold_right, cineva a scris:
let what f lst = List.fold_right (fun e r -> f r :: e) lst []
Interpretorul indică tipul ('a list -> 'a) ->' 'a list list -> 'a list
a) Explicați de ce funcția what poate fi aplicată doar când lst e o listă de liste.
b) Simplificând, particularizăm let what1 = what List.length și obținem o funcție care ia o listă de liste de întregi.
Argumentați (preferabil cu o demonstrație prin inducție) ce face funcția.
Marius Minea
Last modified: Thu Oct 12 19:00:00 EEST 2017