1. Scrieți o funcție mapsetunion care ia ca
parametru o mulțime de șiruri și o funcție
f care pentru un șir returnează o mulțime
de șiruri, și care calculează reuniunea tuturor
mulțimilor obținute aplicând pe f
mulțimii de șiruri date.
mapsetunion f {s1, s2, ..., sn} = f(s1) ∪ f(s2) ∪ ... ∪ f(sn)
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. Scrieți o funcție care ia o listă de asociere cu perechi de tip (șir, întreg) și creează un dicționar în care fiecare șir e asociat cu suma tuturor valorilor cu care e asociat în listă.
Rezolvați problema a) direct; b) creând întâi un dicționar care pentru fiecare șir conține mulțimea tuturor întregilor asociați, și apoi folosește funcția map (din modulul Map) pentru a crea un dicționar cu aceleași chei, transformând valorile.
3. Implementați cu ajutorul lui fold din modulul Map
funcția filter care creează un nou dicționar doar cu
perechile din dicționarul dat care satisfac o funcție dată.
Documentația specifică tipurile pentru funcțiile fold și filter. Ele funcționează similar ca pentru liste și mulțimi, dar
funcția dată ca prim parametru primește ambele componente ale unei
intrări de dicționar: cheia și valoarea. Pentru fold, ordinea
parametrilor e aceeași ca la Set: 1) funcția, 2) colecția prelucrată
(dicționarul resp. mulțimea), și 3) valoarea inițială.
4. Scrieți o funcție care ia o listă de asociere cu perechi de tip
(șir, listă de întregi) și care creează un dicționar în care fiecare șir
e asociat mediei elementelor din listă.
Scrieți întâi o funcție care calculează media elementelor unei liste,
fără a o parcurge de două ori. Folosiți List.fold_left având ca
rezultat parțial o pereche cu numărul elementelor deja parcurse și suma lor.
5. 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 funcția fold din modulul
Map.
6. a) Fiind dată o funcție reprezentată ca dicționar, determinați dacă
funcția e o involuție, adică dacă e inversabilă și f-1 = f.
De exemplu, dacă dicționarul asociază șirul "x" cu șirul "y", verificați
dacă dicționarul asociază o valoare și lui "y", și dacă aceasta e "x".
b) 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ă.
De exemplu, dacă relația e pe șiruri, și "x" e în relație cu "x", "y" și
"z" (adică R("x", "x"), R("x", "y"), R("x", "z")), dicționarul asociază lui
"x" mulțimea de șiruri {"x", "y", "z"}.
Trebuie să verificăm atunci că pentru orice element e din mulțimea
asociată lui "x", "x" se află și în mulțimea asociată cheii
e. (Putem elimina de la bun început pe "x" din mulțimea pentru
care verificăm, pentru că evident, dacă "x" e în relație cu "x", asta
e chiar ce vrem să verificăm).
Pentru ambele variante ale problemei, verificarea trebuie făcută pentru
fiecare intrare din dicționar. Dacă măcar pentru o intrare răspunsul e
fals, rezultatul final e fals. Putem implementa cu excepții, asemănător
cu exemplul dat (sec. 5.1) pentru testul de membru în listă,
fosind iter din modulul Map, sau putem folosi direct
funcția for_all, disponibilă pentru dicționare și mulțimi (și
liste), care determină dacă o condiție (funcție booleană) e adevărată
pentru toate elementele colectiei (dicționar sau mulțime).
7. a) Fiind dată o funcție reprezentată ca dicționar, calculați inversa
functiei dacă există. În caz contrar semnalați o excepție: failwith
"functie neinversabila".
Deoarece considerăm doar domeniul efectiv de valori din partea dreaptă
a dicționarului, funcția e implicit surjectivă, deci e inversabilă
dacă și numai dacă e injectivă. Construim efectiv inversa folosind fold. Dacă la un moment dat, pentru o pereche (k, v) constatăm că
v e deja cheie în dicționarul parțial construit, înseamnă că
era asociată și altei chei, deci funcția nu e injectivă, și nici inversabilă.
b) 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.
De exemplu, reprezentăm relația
R = {("x", "y"), ("x", "t"), ("y", "y"), ("y", "z")}
printr-un dicționar care asociază lui "x" mulțimea {"y", "t"} și
lui "y" mulțimea {"y", "z"}. Atunci, inversa e R-1 =
{("y", "x"), ("y", "y"), ("z", "y"), ("t", "x")}. Ea e
reprezentată printr-un dicționar care nu conține cheia "x" (deoarece nu
apare în partea dreaptă în R), asociază lui "y" mulțimea {"x", "y"},
lui "z" mulțimea {"y"} și lui "t" mulțimea {"x"}.
Pentru a obține inversa, parcurgem dicționarul inițial cu fold,
și pentru fiecare element e din mulțimea v valoare
pentru cheia k adăugăm k la mulțimea asociată cheii e în rezultat.
8. 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 din modulul Map pentru a implementa a doua mapare.