Logică și structuri discrete - Relații: Exerciții

1. Ordini parțiale Orice limbaj de programare definește o ordine de evaluare pentru expresii. În C, operatorii &&  ||  , (virgula pentru secvențiere) și ? : (condițional) își evaluează întâi primul operand și apoi al doilea (la && și || dacă mai e nevoie; la condițional, după caz, al doilea sau al treilea operand). Pentru ceilalți operatori, ordinea de evaluare e nespecificată, adică poate fi oricare (de exemplu, f(x) + g(x) poate apela întâi g și apoi f înainte de a face suma).
Asemănător sunt ordonate și efectele laterale (engl. side effects, atribuirile/citirile/scrierile) în cadrul unei expresii. Pentru &&  ||  , ? : efectele laterale din evaluarea primului operand au loc înainte de a evalua restul expresiei. Pentru o funcție, efectele laterale din evaluarea argumentelor (și a expresiei care ne dă funcția apelată -- obișnuit un nume de funcție, dar poate fi o expresie) au loc înaintea apelului funcției. În rest, ordinea de aplicare a efectelor laterale în cadrul evaluării unei expresii nu e precizată.
Deci, între pașii de evaluare e definită o ordine parțială (ea e specificată între anumiți pași, nu neapărat între toți). Dacă într-o expresie asupra aceluiași obiect se fac două scrieri sau o citire și o scriere care nu sunt ordonate, rezultatul e nedefinit și compilatorul dă un avertisment.
De exemplu, expresia v[i] = i++ are următorii pași de evaluare:

• a) evaluarea lui v (se obține adresa tabloului, primul operand al lui [])
• b) evaluarea lui i (se obține indicele, al doilea operand al lui [])
• c) evaluarea adresei lui v[i] (a operatorului [], combinând adresa tabloului și indicele)
• d) evaluarea lui i (din partea dreaptă)
• e) evaluarea operatorului ++ (produce aceeași valoare obținută la d)
• f) efectul lateral al lui ++ (incrementează pe i)
• g) efectul lateral al atribuirii (valoarea obținută în pasul e) la adresa calculată în pasul c)

• a < c și b < c (operanzii înaintea operatorului [])
• d < e și d < f (operandul înaintea operatorului ++ și a efectului lateral cauzat de acesta)
• c < g și e < g (operanzii înaintea operatorului =)

2. Map.find și excepții 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 fold_left și 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.

3. Maximul din dicționar 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.

4. Închiderea tranzitivă Considerăm funcții parțiale reprezentate prin dicționare de la șiruri la șiruri. Ele sunt un caz particular de relații (pe șiruri), care asociază unui element cel mult un element (șirurile care nu sunt chei în dicționar nu au asociată vreo valoare).
Pornind de la exemplul de compunere a două funcții date ca dicționare
a) Scrieți o funcție care ia un dicționar reprezentând o funcție f și un număr n și returnează dicționarul reprezentând compunerea lui f cu ea însăși de n ori.
b) Privind f ca relație R (mulțime de perechi) scrieți o funcție care luând un dicționar (pentru R) și un număr n returnează mulțimea perechilor din R^≤n = R ∪ R² ∪ ... ∪ Rⁿ.
c) Calculați închiderea tranzitivă a relației R, găsind prima valoare n pentru care R^≤n = R^≤n+1 . Folosiți o pereche (R^≤n-1, Rⁿ) din care calculați (R^≤n, Rⁿ⁺¹).
d) (opțional). Tipăriți dicționarul în formatul dot după exemplul următor:

digraph {
  foo -> bar;
  bar -> baz;
}