type 'a ens = | Vide | Ens of ('a * 'a ens);; exception Ensemble_vide;; let tete e = match e with |Vide -> raise Ensemble_vide |Ens(a,b) -> a;; let queue e = match e with |Vide -> raise Ensemble_vide |Ens(a,b) -> b;; let rec appartient el ensemble = match ensemble with |Vide -> false |Ens(t,q) -> if t = el then true else appartient el q;; let ajoute el ens = if appartient el ens then ens else Ens(el,ens);; let (@+) el ens = ajoute el ens;; let rec union ens1 ens2 = match ens1 with |Vide -> ens2 |Ens(t,q) -> t @+ (union q ens2) ;; let (@|) ens1 ens2 = union ens1 ens2;; let rec cardinal = function | Vide -> 0 | Ens(t,q) -> if appartient t q then cardinal q else 1 + cardinal q;; let rec applique f ens = match ens with |Vide -> Vide |Ens(t,q) -> Ens(f(t),applique f q);; let rec parties = function |Vide -> Ens(Vide,Vide) |Ens(t,q) -> (parties q) @| (applique (ajoute t) (parties q));; let rec liste_el = function |Vide -> [] |Ens(a,e) -> a::liste_el(e);; let rec ens_of_list = function |[] -> Vide |t::q -> t @+ (ens_of_list q);; let rec retire el ens = match ens with |Vide -> Vide |Ens(t,q) -> if t = el then q else Ens(t, retire el q);; let rec selec pred ens = match ens with |Vide -> Vide |Ens(t,q) -> if pred t then Ens(t,selec pred q) else selec pred q;; let rec parties_taille_n ens n = selec (fun x -> cardinal x = n) (parties ens);; let rec existe pred ens = match ens with |Vide -> false |Ens(t,q) -> if pred t then true else existe pred q;; let rec pour_tout pred ens = match ens with |Vide -> true |Ens(t,q) -> if pred t then pour_tout pred q else false;; let partition pred ens = let rec temp pred ens e1 e2 = match ens with |Vide -> (e1,e2) |Ens(t,q) -> if pred t then temp pred q (Ens(t,e1)) e2 else temp pred q e1 (Ens(t,e2)) in temp pred ens Vide Vide;; let projection rang couple = match couple with |(a,b) -> if rang = 0 then a else b;; let p0 (a,b) = a;; let p1 (a,b) = b;; let rec couples el ens = match ens with |Vide -> Vide |Ens(t,q) -> Ens((el,t),couples el q);; let rec produit_cart ens1 ens2 = match ens1 with |Vide -> Vide |Ens(t,q) -> (couples t ens2) @| (produit_cart q ens2);; let rec inter ens1 ens2 = match ens1 with |Vide -> Vide |Ens(t,q) -> if appartient t ens2 then Ens(t,inter q ens2) else inter q ens2;; let rec complement ens univers = match univers with |Vide -> Vide |Ens(t,q) -> if appartient t ens then complement ens q else Ens(t,complement ens q );; let rec difference ens1 ens2 = match ens1 with |Vide -> Vide |Ens(t,q) -> if appartient t ens2 then difference q ens2 else Ens(t,difference q ens2);; let est_inclus ens1 ens2 = if inter ens1 ens2 = ens1 then true else false;; let est_egal ens1 ens2 = (est_inclus ens1 ens2) && (est_inclus ens2 ens1);; let max2 a b = if a >= b then a else b;; let rec max ens = match ens with |Vide -> raise Ensemble_vide |Ens(t,Vide) -> t |Ens(t,q) -> max2 t (max q);; exception Cle_inconnue;; let rec assoc cle ens = match ens with |Vide -> raise Cle_inconnue |Ens(t,q) -> if fst t = cle then snd t else assoc cle q;; let rec ens_assoc cle ens = match ens with |Vide -> Vide |Ens(t,q) -> if fst t = cle then Ens(snd t,ens_assoc cle q) else ens_assoc cle q;; (* essais *) let a = ens_of_list [1;2;3];; let a2 = ens_of_list [2;4;6;8;10];; parties a;; cardinal (parties a);; liste_el(applique liste_el (parties a));; let p el = el > 2;; selec p a;; existe p a;; pour_tout p a;; #trace parties;; parties a;; #untrace parties;; liste_el (projection 1 (partition p a));; existe (fun x-> x <2) a;; liste_el (couples 5 a);; let b = ens_of_list ['a';'b';'c';'d';'e'];; liste_el (produit_cart a b);; cardinal (produit_cart a b) = (cardinal a) * (cardinal b);; inter a a2;; let base = ens_of_list [("albert","12");("barnabe","11");("claude","12");("desire","13");("barnabe","rugby");("desire","danse")];; let base = Ens(("albert","12"),Ens(("barnabe","11"),Ens(("claude","12"),Ens(("desire","13"),Ens(("barnabe","rugby"),Vide)))));; assoc "barnabe" base;; ens_assoc "barnabe" base;; (*------------------------ L O G I Q U E -------------------------------*) let et2 x y = match x,y with |true,true -> true |_ -> false;; let non2 = function |true -> false |false -> true;; let et x y = if x then y else false;; let ou x y = if x then true else y;; let non x = if x then false else true;; let nand x y = non(et x y);; let ouex x y = ou (et x (non y)) (et (non x) y);; let imp x y = ou (non x) y;; let equiv x y = ou (et x y) (et (non x) (non y));; (*problème avec les répétitions -> liste*) let rec map f liste = match liste with |[] -> [] |t::q -> (f t)::(map f q);; let rec concat list1 list2 = match list1 with |[] -> list2 |t::q -> t::(concat q list2);; let rec applique_list f_list list = match f_list with |[] -> [] |ft::fq -> concat (map ft list) (applique_list fq list);; let table_bool connect = applique_list (map connect [true;false]) ([true;false]);; let boo = ens_of_list [true;false];; liste_el (produit_cart boo boo);; let compris_entre min max = function x -> et (x >= min) (x <= max);; let ens1 = ens_of_list [1;2;3;4;5;6;7;8;9];; selec (compris_entre 3 5) ens1;;