Exerciții rezolvate: Mulțimi

Exercițiul 1. Implementați o funcție care returnează produsul cartezian a două mulțimi.

Vom rezolva problema în mai multe variante, în funcție de modul de reprezentare al mulțimilor.
Într-o primă variantă, reprezentăm mulțimi prin liste.

a) Listă de liste. O opțiune e să producem rezultatul ca listă de liste, câte una pentru fiecare element al celei de-a doua liste/mulțimi. Scriem o primă funcție care ia ca parametru o listă [a1; a2; ...; an] și un element b și produce lista perechilor având ca element secund b: [(a1, b); (a2, b); ...; (an, b)] . Cum fiecare element din lista rezultat se obține dintr-un element al listei inițiale, descriem această corespondență printr-o funcție: din elementul e se formează perechea (e, b) și aplicăm funcția întregii liste, folosind iteratorul List.map :

let pairs_of_list l b = List.map (fun e -> (e, b)) l

val pairs_of_list : 'a list -> 'b -> ('a * 'b) list = <fun>

Apelând pairs_of_list [1;2;3] 'a' obținem rezultatul (int * char) list = [(1, 'a'); (2, 'a'); (3, 'a')] .
Rămâne să aplicăm această funcție repetat pentru fiecare element celei de-a doua liste, ceea ce se poate face tot cu List.map . Funcția pairs_of_list ia ca parametru o listă și un element, deci pair_of_list l1 poate fi aplicată succesiv fiecărui element al listei l2:

let cartprod l1 = List.map (pairs_of_list l1)

cartprod [1;2;3] ['a';'b'] produce ca rezultat o listă de liste: (int * char) list list = [[(1, 'a'); (2, 'a'); (3, 'a')]; [(1, 'b'); (2, 'b'); (3, 'b')]]
Dacă dorim o listă de perechi (pe un singur nivel), putem să-i aplicăm funcția List.flatten .

b) Listă de perechi. O altă variantă e să obținem direct o listă de perechi. Pentru că vom aplica repetat funcția care creează o listă de perechi dintr-un element și o listă, îi dăm un argument suplimentar pr, o listă de perechi la care să acumuleze rezultatul.

Putem atunci să scriem funcția aplicând List.fold_left . Pentru aceasta trebuie să descriem pasul de prelucrare cu o funcție de doi parametri (primul e rezultatul parțial, și al doilea e elementul listei), care descrie modul în care rezultatul e actualizat după prelucrarea fiecărui element. În acest caz, funcția adaugă perechea formată cu elementul listei la lista de perechi deja obținută:

let addpairs l1 pr b = List.fold_left (fun r e1 -> (e1, b) :: r) pr l1

List.fold_left aplică prelucrarea listei l1, pornind cu lista de perechi pr ca valoare inițială; ea va adăuga pe rând la pr perechile (e1, b) cu e1 din lista l1, și b fixat, primit ca parametru. La sfârșit vom avea deci: (an, b)::...::(a2, b)::(a1, b)::rp dacă lista l1 = [a1;a2;...;an] .

Mai departe, e suficient să aplicăm această funcție fiecărui element din lista a doua, din nou cu List.fold_left: pornim de la lista vidă, care e actualizată la fiecare element b al listei l2 de funcția addpairs l1, care adaugă toate perechile formate cu b și elementele listei l1:

let cartprod l1 l2 = List.fold_left (addpairs l1) [] l2

sau mai scurt, pentru că l2 apare ca parametru în ambele părți:

let cartprod l1 = List.fold_left (addpairs l1) []

Apelând cartprod [1;2;3] ['a';'b'] obținem (int * char) list = [(3, 'b'); (2, 'b'); (1, 'b'); (3, 'a'); (2, 'a'); (1, 'a')] .

c) Mulțimi. În OCaml, pentru a defini mulțimi, ne trebuie un tip ordonat de elemente. Pentru un exemplu cât mai simplu, vom face produsul cartezian între mulțimi de caractere și mulțimi de șiruri. Un exemplu mai general e descris aici.

Întâi trebuie să definim un modul care să aibă la bază tipul pereche dorit (char * string) și o relație de ordine -- putem folosi funcția predefinită compare care funcționează automat pe orice tip compus.

module CSPair = struct
  type t = char * string
  let compare = compare
end

Definim apoi trei module mulțime, parametrizate cu modulele pentru cele trei tipuri de elemente (caractere, șir, și perechi între cele două).

module C = Set.Make(Char)
module S = Set.Make(String)
module CS = Set.Make(CSPair)

Când lucrăm cu mulțimi, va trebui să folosim funcțiile din modulul potrivit (C.add, S.add, CS.add), spre deosebire de cele cu liste (List.mem, List.iter, List.map, etc.) care sunt polimorfe și se pot folosi pe orice tip de listă.

Acum, similar cu soluția de la punctul b), definim o funcție addpairs care ia ca parametru o mulțime s1 (de primul tip, caracter) și un element b de al doilea tip (șir) și o mulțime de perechi, și adaugă la ea toate perechile între un element din prima mulțime și elementul b.

let addpairs s1 b = C.fold (fun e1 -> CS.add (e1, b)) s1

Pentru aceasta, mulțimea s1 e parcursă cu iteratorul S.fold. Funcția aplicată de acest iterator e funcția de element e1 care adaugă perechea (e1, b) la acumulator (rezultatul parțial): fun e1 acc -> CS.add (e1, b) acc . Cum acumulatorul apare în ambele părți ale definiției, el poate fi omis: fun e1 -> CS.add (e1, b), o funcție cu tipul: char -> CS.t -> CS.t, deci care ia un caracter și o mulțime de perechi și produce o nouă mulțime de perechi. Această funcție e aplicată de C.fold mulțimii (de caractere) s1 și oricărei valori inițiale de mulțimi de perechi, și va produce o mulțime care conține în plus noile perechi.

Mai departe, funcția addpairs s1 (care adaugă perechi iterând peste mulțimea s1) trebuie iterată peste mulțimea s2, deasemenea cu fold, însă pentru al doilea modul: S.fold. Valoarea inițială pentru parametrul care acumulează rezultatul e mulțimea vidă de perechi, CS.empty :

let cartprod s1 s2 = S.fold (addpairs s1) s2 CS.empty

Cu acestea am definit funcția produs cartezian. Întrucât nu avem o notație directă pentru constante de tip mulțime, e mai simplu să le introducem ca liste, și scriem funcții care convertesc liste în mulțimi (pentru ambele tipuri). Acestea iterează peste liste și adaugă succesiv elementele la o mulțime, inițial vidă. În final, putem vizualiza rezultatul tot ca listă, cu funcția elements care convertește o mulțime la listă.

let set_of_clist = List.fold_left (fun r e -> C.add e r) C.empty
let set_of_slist = List.fold_left (fun r e -> S.add e r) S.empty

CS.elements (cartprod (set_of_clist ['a';'b';'c']) (set_of_slist ["1"; "2"])) dă rezultatul [('a', "2"); ('a', "1"); ('b', "2"); ('b', "1"); ('c', "2"); ('c', "1")] .

Exercițiul 2. Implementați o funcție care returnează mulțimea părților (submulțimilor) unei mulțimi.

Presupunem că am obținut deja mulțimea P(A_n) a părților pentru o mulțime A_n cu n elemente, și mai adăugăm un element a_n+1 obținând mulțimea A_n+1. Fiecare element (mulțime) din P(A_n) face parte și din P(A_n+1) . Adăugând a_n+1 la orice astfel de element (mulțime) obținem deasemenea o mulțime care e un element al lui P(A_n+1) . Numărul de elemente s-a dublat, de la 2ⁿ la 2ⁿ⁺¹ .

a) Listă de liste

Scriem o funcție care implementează această transformare, lucrând cu liste de liste (pentru mulțimea părților). Funcția ia ca parametru o listă de liste și un nou element, și produce o listă de două ori mai lungă, care conține toate listele-element ale listei inițiale, și deasemenea toate listele obținute prin adăugarea noului element la vechile liste-element.

Putem implementa funcția iterând cu List.fold_left prin lista de liste (reprezentând vechea mulțime a părților), pornind chiar de la aceeași listă. La fiecare pas, funcția de prelucrare primește rezultatul parțial acumulat ll (o listă de liste), și una din listele el element al listei de liste de prelucrat, adaugă noul element ne la lista el și pe acest rezultat la acumulator: adaugă la rezultatul acumulat lista la care e

let addelt llst ne = List.fold_left (fun ll el -> (ne :: el) :: ll) llst llst

Se obține în final o listă dublă ca dimensiune (la lista inițială s-au adăugat tot atâtea elemente). Pentru a aplica această dublare pentru fiecare element al mulțimii (listei) pentru care vrem să obținem mulțimea părților, iterăm peste ea tot cu List.fold_left și funcția de dublare scrisă anterior. Ea are exact structura necesară lui List.fold_left: primul argument e rezultatul parțial (lista de liste care se va dubla la fiecare aplicare), iar al doilea e elementul care va parcurge succesiv lista pentru care calculăm mulțimea părților. Valoarea inițială de la care pornim e [[]], lista/mulțimea cu un singur element (lista/mulțimea vidă), care e chiar mulțimea părților mulțimii vide.

let powset = List.fold_left addelt  [[]]

Apelând powset [1;2;3] obținem int list list = [[3; 1]; [1]; [3; 2; 1]; [2; 1]; [3]; []; [3; 2]; [2]] .

b) Mulțime de mulțimi Din nou, pentru simplitate, considerăm mulțimi de șiruri. Definim un modul pentru mulțimi de șiruri, și încă unul pentru mulțimi de astfel de mulțimi:

module S = Set.Make(String)
module SS = Set.Make(S)

Urmănd același tipar din problema anterioară, scriem o funcție care crește mulțimea părților cu încă un element în plus din mulțimea originală. Pentru aceasta, iterăm cu SS.fold peste o mulțime de mulțimi. Dacă r e rezultatul parțial acumulat, s mulțimea curentă parcursă din mulțimea de mulțimi, și e noul element, atunci la r adăugăm pe s împreună cu e, pornind ca acumulator chiar cu mulțimea parcursă:

let addelem e ps = SS.fold (fun s r -> SS.add (S.add e s) r) ps ps

Această funcție care dublează numărul elementelor trebuie aplicată repetat, iterând peste mulțimea inițială, și pornind de la mulțimea cu un singur element, mulțimea vidă:

let powset s = S.fold addelem s (SS.singleton S.empty)

Pentru a testa mai ușor, folosim și aici o funcție prin care putem crea mulțimea inițială dintr-o listă:

let set_of_list = List.fold_left (fun r e -> S.add e r) S.empty

Apelând doar powset (set_of_list ["a"; "b"; "c"]) obținem o mulțime, care nu e vizualizată direct de interpretor. Pentru a o vizualiza, o transformăm în listă, cu SS.elements, și mai mult, transformăm fiecare element al ei în listă, cu List.map S.elements :

List.map S.elements (SS.elements (powset (set_of_list ["a";"b";"c"])))

Obținem astfel: S.elt list list = [[]; ["a"]; ["a"; "b"]; ["a"; "b"; "c"]; ["a"; "c"]; ["b"]; ["b"; "c"]; ["c"]] . O altă variantă e să scriem o funcție care tipărește elementele unei mulțimi, folosind SS.iter pentru a itera prin mulțimea de mulțimi, și S.iter pentru mulțimile componente.

Marius Minea

Last modified: Sat Oct 19 20:00:00 EEST 2013