Mulțimi și relații

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 mulțimi, dar funcția dată ca prim argument are ca parametri atât cheia cât și valoarea intrării curente din dicționar (iar pentru fold și acumulatorul pentru rezultat). Ordinea parametrilor e aceeași ca la Set: (1) funcția, (2) colecția prelucrată (dicționarul), iar pentru fold ș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. Scrieți o funcție care ia ca parametri două dicționare de la șiruri la șiruri reprezentând funcții parțiale f₁ și f₂ și returnează dicționarul care reprezintă f₂ ⚪ f₁.

6. Se dă un dicționar care reprezintă o funcție parțială f definită pe șiruri, necirculară: adică nu există n și s pentru care fⁿ(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 fⁿ(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.

7. Fie un dicționar de la șiruri la șiruri reprezentând o funcție parțială f.
a) Scrieți o funcție (având ca parametru un astfel de dicționar) care returnează dicționarul reprezentând f² = f ⚪ f, și apoi o funcție care calculează dicționarul pentru fⁿ.
b) Modificați funcția astfel încât să genereze o excepție dacă fⁿ are un punct fix (există x cu fⁿ(x) = x)
c) Aplicați repetat funcția de mai sus pentru a determina dacă funcția f are un ciclu (se va genera fie o excepție, fie se ajunge la relația vidă).

8. 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"}.
O relație e simetrică atunci când, pentru orice X și Y, dacă Y e asociat lui X, atunci și X e asociat lui Y. Dicționarul conține toate elementele Y asociate cheii X sub formă de mulțime. Trebuie să verificăm atunci (pentru fiecare cheie X, parcurgând dicționarul), că luând orice element Y din mulțimea asociată lui X, și X se găsește în mulțimea asociată lui Y (luând Y ca și cheie). (Putem elimina de la bun început pe X din mulțimea pentru care verificăm, pentru că evident, dacă X asociat lui 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).

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

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