(* Corrige d'Introduction à la programmation *)
(* Exercices sur les listes : opérations ensemblistes *)
(* Ancien TD 8 *)

(* --------------------------------------------------------- *)

(* Les opérations ensemblistes sur les listes *)

let rec union l1 l2=
 match (l1,l2) with
 	([],l2) -> l2
 	|(x::r1,l2) -> if Membre x l2 then union r1 l2 else x::(union r1 l2);;
 
let rec inter l1 l2=
  match (l1,l2) with
 	([],_) -> []
 	|(x::r1,l2) -> if Membre x l2 then x::(inter r1 l2) else inter r1 l2;;
 
 let rec diff l1 l2=
  match (l1,l2) with
 	([],_) -> []
 	|(x::r1,l2) -> if Membre x l2 then diff r1 l2 else x::(diff r1 l2);;
 
 let diff_sym l1 l2= diff (union l1 l2) (inter l1 l2);;

(* --------------------------------------------------------- *)

(* Les opérations ensemblistes sur les listes triées *)

let rec union_trie l1 l2 = 
 match (l1,l2) with ([],[]) -> []
                  | (l ,[]) -> l
                  | ([], l) -> l
                  | (t1::r1,t2::r2) ->
                 if(t1 < t2) then t1::(union_trie r1 (t2::r2)) else
                 if(t1 > t2) then t2::(union_trie r2 (t1::r1)) else
               (*if(t1 = t2) *)        union_trie r2 (t1::r1);;

 
(* union_trie [1;2;5;7;10] [1;7;8;10];; *)
(* - : int list = [1; 2; 5; 7; 8; 10]   *)
 
let rec inter_trie l1 l2 = match (l1,l2) with 
   (t1::r1,t2::r2) -> if(t1 < t2) then    inter_trie r1 (t2::r2) else
                      if(t1 > t2) then    inter_trie r2 (t1::r1) else
                    (*if(t1 = t2) *) t1::(inter_trie r1 r2)
 | _ -> [];;

 
(* inter_trie [1;2;5;7;10] [1;7;8;10];; *)
(* - : int list = [1; 7; 10] *)

let rec difference_trie l1 l2 = 
 match (l1,l2) with ([],_) -> []
                  | (l ,[]) -> l
                  | (t1::r1,t2::r2) ->
                if(t1 < t2) then t1 ::(difference_trie r1 (t2::r2)) else 
                if(t1 > t2) then      (difference_trie r2 (t1::r1)) else 
              (*if(t1 = t2) *)         difference_trie r1 r2;;
 
(* difference_trie [1;2;5;7;10] [1;7;8;10];; *)
(* - : int list = [2; 5] *)

let rec diffsym_trie l1 l2 = 
 match (l1,l2) with ([],[]) -> []
                  | (l ,[]) -> l
                  | ([], l) -> l
                  | (t1::r1,t2::r2) -> 
                if(t1 < t2) then t1 ::(diffsym_trie r1 (t2::r2)) else 
                if(t1 > t2) then t2 ::(diffsym_trie r2 (t1::r1)) else 
              (*if(t1 = t2) *)         diffsym_trie r1 r2;;

 
(* diffsym_trie [1;2;5;7;10] [1;7;8;10];; *)
(* - : int list = [2; 5; 8]               *)

(* Le produit cartésien *)

let rec concat l1 l2 =
  match (l1,l2) with
        ([],l2) -> l2
        |(x::r1,l2) -> x::concat r1 l2;;

let rec produitcartesien l1 l2 = match (l1,l2) with
| ([t1],[t2]) -> [(t1,t2)]
| ([t1],t2::r2) -> (t1,t2)::(produitcartesien [t1] r2)
| (t1::r1,[t2]) -> (t1,t2)::(produitcartesien r1 [t2])
| (t1::r1,t2::r2) -> 
	concat (produitcartesien [t1] (t2::r2)) (produitcartesien r1 (t2::r2))
| _ -> [];;
 
(* produitcartesien [1;2;5;7;10] [1;7;8;10];; *)
(* - : (int * int) list = 
%  [1, 1; 1, 7; 1, 8; 1, 10; 2, 1; 2, 7; 2, 8; 2, 10; 5, 1; 5, 7; 5, 8;
%   5, 10; 7, 1; 7, 7; 7, 8; 7, 10; 10, 1; 10, 7; 10, 8; 10, 10] *)