Exerciții rezolvate: Relații, funcții parțiale

Exercițiul 1. 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 fⁿ(s) = s . Scrieți o funcție rep care, fiind dat dicționarul care implementează funcția f, calculează pentru un șir s reprezentantul lui, adică valoarea fⁿ(s) cu n maxim pentru care fⁿ(s) e definit. (Dacă f(s) nu e definit, atunci n = 0, intrucât f⁰ e funcția identitate, și f⁰(s) = s există).
De exemplu, pentru f("a") = "b", f("b") = "c", f("d") = "c", f("e") = "f" avem rep("a") = rep("b") = rep("c") = rep("d") = "c", rep("e") = rep("f") = "f" .

În primul rând, definim modulul M pentru lucrul cu dicționare care au ca și cheie (domeniu de definiție) șiruri.

module M = Map.Make(String)

Să definim acum funcția reprezentant. Presupunem dicționarul m fixat, definit în exterior (îl vom scrie ulterior ca parametru). Fiind dat șirul x, ideea e de a vedea întâi dacă f(x) e definită, adică, dacă M.find x m dă o valoare sau generează o excepție. În cel din urmă caz, returnăm chiar pe x. În primul caz, căutăm mai departe reprezentantul lui f(x) (adică încercăm să aplicăm pe f mai departe) și îl returnăm.

let rec repr x = 
  try repr (M.find x m) 
  with Not_found -> x

Cum am tratat excepția, repr funcționează bine în cazul de bază, când x nu e găsit. Mai departe, dacă repr obține corect reprezentantul lui f(x) (adică al lui M.find x m), acesta e returnat și pentru x, deci prin inducție, funcția e corectă. Rămâne doar să definim funcția exterioară rep care ia ca parametru și dicționarul m (și apoi valoarea x): rep m x = repr x, deci rep m = repr :

let rep m =
  let rec repr x = 
    try repr (M.find x m) 
    with Not_found -> x
  in repr

Pentru a testa, definim un dicționar m adăugând succesiv perechi la M.empty :

let m = M.add "x" "y" (M.add "y" "z" (M.add "z" "t" M.empty));;
rep m "z";;

Sau, pentru o scriere mai ușoară, am putea defini întâi o funcție care creează un dicționar pornind de la perechile date într-o listă:

let map_of_pairs = List.fold_left (fun m (x, y) -> M.add x y m) M.empty

La fiecare pas, funcția acumulează în rezultatul parțial m un dicționar în care a mai adăugat și perechea curentă din listă. Putem apela atunci pentru test:

rep (map_of_pairs [("x", "y"); ("y", "z"); ("z", "t")]) "z";;

Exercițiul 2. Scrieți o funcție care reunește două dicționare de la șiruri la mulțimi de șiruri.

Scriem întăi o funcție asemănătoare cu funcția addpair de la curs: vrem să adăugăm o mulțime s la intrarea de dicționar pentru un șir x .

module M = Map.Make(String)
module S = Set.Make(String)

let addset x s m =
  let oldset = try M.find x m with Not_found -> S.empty
  in M.add x (S.union oldset s) m

Funcția caută întâi intrarea de dicționar pentru x, returnând mulțimea vidă, dacă x nu e găsit. Apoi, rescriem intrarea pentru x în rezultat cu reuniunea dintre mulțimea veche și cea nouă.

Funcția căutată se poate atunci scrie remarcabil de scurt :

let mapmerge = M.fold addset

Să explicăm această definiție. Funcția scrisă are nevoie de doi parametri, cele două dicționare de reunit. Pentru M.fold, primul reprezintă dicționarul peste care se iterează, și care va furniza argumentele x (cheia șir) și s (valoarea mulțime) pentru addset. Al doilea dicționar e valoarea inițială pentru M.fold, care e furnizată inițial ca argumentul m pentru addset, reprezentând rezultatul care se actualizează în timpul iterării peste primul dicționar. Deci, funcția auxiliară addset definită înainte e exact cea necesară pentru a produce reuniunea, iterând peste primul dicționar, pornind cu al doilea ca valoare inițială.

Pentru a testa ușor cele scrise, folosim funcția de la curs care creează un dicționar dintr-o listă de perechi:

let addpair m (x, y) =
  let oldset = try M.find x m with Not_found -> S.empty
  in M.add x (S.add y oldset) m
let setmap_of_pairs = List.fold_left addpair M.empty

și o folosim ca să creăm cele două dicționare de combinat:

let m = mapmerge (setmap_of_pairs [("x", "y"); ("x", "z"); ("y", "t")])
  (setmap_of_pairs [("x", "a"); ("a", "b"); ("a", "c")]);;

Pentru a vizualiza rezultatul, creăm lista de perechi (cheie, valoare) folosind M.bindings și transformăm a doua componentă din mulțime în listă, cu S.elements, pentru că listele pot fi vizualizate direct în interpretor:

List.map (fun (x, y) -> (x, S.elements y)) (M.bindings m);;

[("a", ["b"; "c"]); ("x", ["a"; "y"; "z"]); ("y", ["t"])]

Exercițiul 3. Fiind dată o relație pe o mulțime de șiruri 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ă.

Scriem în primul rând definiția matematică: relația R ⊆ S × S e simetrică dacă ∀ x, y ∈ S, (x, y) ∈ R → (y, x) ∈ R.

Considerăm obițnuitele module de dicționare și mulțimi peste șiruri:

module M = Map.Make(String)
module S = Set.Make(String)

Pentru implementarea relației ca funcție parțială (dicționar) f_R: S → P(S) trebuie să verificăm pentru fiecare cheie x din dicționar (cu M.for_all) și apoi pentru fiecare șir y din multimea găsită (cu S.for_all) că și x se găsește în mulțimea pentru cheia y

Funcția M.for_all are tipul for_all : (key -> 'a -> bool) -> 'a t -> bool deci are ca al doilea argument dicționarul și ca prim argument o funcție booleană de cheie și valoare din dicționar, despre care se verifică dacă e satisfăcută pentru fiecare pereche cheie-valoare. Similar, funcția S.for_all are tipul for_all : (elt -> bool) -> t -> bool, deci are ca al doilea argument mulțimea și ca prim argument funcția booleană despre care se verifică dacă e adevărată pentru fiecare element din mulțime. Funcția pe care dorim s-o scriem are deci schema:

let is_symm m = M.for_all (fun x vs -> S.for_all (fun y -> ...) vs) m

unde vs e valoarea mulțime din dicționar, iar în locul ... trebuie să verificăm dacă și (y, x) aparține relației. Într-o primă încercare, putem scrie asta ca S.mem x (M.find y m):

let is_symm m =
  M.for_all (fun x vs -> S.for_all (fun y -> S.mem x (M.find y m)) vs) m

Soluția nu este însă completă, pentru că y poate să nu existe în dicționar, ceea ce va genera o excepție. În acest caz, răspunsul este însă negativ (fals), relația nu e simetrică. Mai putem simplifica funcția folosită pentru M.for_all renunțând la scrierea argumentului vs care apare în ultima poziție în stânga și în dreapta:

let is_symm m =
  try M.for_all (fun x -> S.for_all (fun y -> S.mem x (M.find y m))) m
  with Not_found -> false

Putem verifica funcția pe un dicționar construit cu funcția setmap_of_pairs din problema precedentă:

is_symm (setmap_of_pairs [("x", "y"); ("x", "z"); ("y", "x"); ("z", "x")])

Marius Minea

Last modified: Sat Nov 2 19:00:00 EET 2013