Relații și dicționare

Modulul Map (documentația OCaml)

1. 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ă.

2. Scrieți o funcție care ia o listă de șiruri de caractere și creează un dicționar în care fiecare șir e asociat cu numărul aparițiilor din listă

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. Pentru tipurile colecție (liste, mulțimi, dicționare) e util să avem funcții care ne spun dacă există un element care satisface o anume condiție, respectiv dacă toate elementele satisfac condiția.
Implementați funcțiile exists și for_all pentru dicționare, folosind fold. Ele iau ca parametru o funcție booleană de cheie și valoare (care exprimă condiția) și dicționarul în care se face căutarea. (Ele există ca funcții standard, deci puteți vedea tipul lor în documentație).
Încercați să scrieți prelucrarea folosind o excepție pentru a întrerupe parcurgerea dacă răspunsul nu mai depinde de restul elementelor (true pentru exists, resp. false pentru for_all). În acest caz puteți folosi mai simplu iter. Urmați exemplul cu liste de la curs și din notițe (sec. 5.1).

5. Implementați cu ajutorul lui fold funcția standard map care construiește un dicționar în care toate valorile au fost transformate folosind o funcție dată ca parametru.

6. Scrieți o funcție care primește un dicționar de la șiruri la întregi și o listă de șiruri și returnează mulțimea tuturor valorilor din dicționar care corespund șirurilor din listă.
Parcurgeți lista cu List.fold_left. Când folosiți find, tratați excepția Not_found pentru a adăuga o valoare la mulțimea-acumulator doar când cheia e găsită în dicționar.

7. Scrieți o funcție care primește o funcție și un dicționar și returnează maximul valorilor funcției pentru toate intrările dicționarului, sau generează excepția Not_found pentru un dicționar vid.
Funcția-parametru are ca argumente cheia și valoarea unei intrări, și poate returna valori arbitrare. Folosiți fold pentru parcurgere, și max (definită implicit pentru orice tip) pentru a compara valorile returnate de funcția parametru.

8. 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₁.

9. Scrieți o funcție care ia ca parametru un dicționar reprezentând o funcție parțială f de la șiruri la șiruri și calculează pentru un șir s numărul maxim n pentru care fⁿ(s) e definit, respectiv generează o excepție dacă șirul fⁿ(s) e ciclic (definit pentru orice n).
De exemplu, pentru f("a") = "b", f("b") = "c", f("d") = "e", f("e") = "f", f("f") = "e", avem depth("x") = 0, depth("a") = 2, depth("b") = 1, iar depth("d") generează excepție (la fel pentru "e" și "f").
Indicație: La parcurgerea pornind de la s rețineți mulțimea tuturor șirurilor deja întâlnite pentru a detecta un eventual ciclu.

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

11. 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).

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