Indicație: instanțiați un modul pentru lucrul cu mulțimi de șiruri: module S = Set.Make(String) și folosiți iteratorul S.fold . Acesta funcționează similar cu List.fold_right, având 3 parametri: 1) o funcție care ia un element de mulțime și o valoare de tipul rezultatului dorit și returnează un rezultat actualizat; 2) mulțimea pe care se iterează; 3) valoarea inițială (de tipul rezultatului dorit). De exemplu, S.fold (fun e r -> r + String.length e) ss 0 va aduna lungimile tuturor șirurilor din mulțimea ss (presupusă definită).
2. Se dă un dicționar (map) care reprezintă
o funcție parțială f definită pe
șiruri, necirculară: adică nu
există n și s pentru
care fn(s) = s . Scrieți o funcție
depth care, fiind dat dicționarul care implementează
funcția f, calculează pentru un
șir s numărul maxim n pentru care
fn(s) e definit.
De exemplu, pentru f("a") = "b", f("b") = "c", f("d") = "c",
avem depth("a") = 2, depth("b") = depth("d") = 1, depth("c") = depth("altceva") = 0.
Suplimentar, calculați suma valorilor depth(s) pentru toate
valorile s din dicționar, folosind Map.fold .
3. Implementați cu ajutorul lui Map.fold funcția Map.filter, care creează un nou dicționar doar cu perechile din dicționarul dat care satisfac o funcție dată.
4. Fiind dată o relație pe S implementată ca dicționar de la S la P(S) (mulțimea părților lui S), scrieți o funcție care determină dacă relația e simetrică.
5. Fiind dată o relație R pe S implementată ca dicționar de la S la P(S) (mulțimea părților lui S), scrieți o funcție care returnează inversa relației, R-1, reprezentată în același mod.
6. Folosind funcția de la problema 1, calculați compunerea a două relații pe șiruri, fiecare dată ca dicționar care pentru fiecare șir conține mulțimea de șiruri cu care acesta se află în relație. Puteți folosi Map.map pentru a implementa a doua mapare.
7. Folosind funcția scrisă la problema 5, calculați ca punct fix închiderea tranzitivă a unei relații, folosind formulele de la curs.