# TP7 PFA

# **Correction**

**ensemble.mli**

module type ELT =
  sig
    type t
    val compare : t -> t -> int
  end 

module type S =
  sig
    type elt
    type t
    val vide : t
    val element_de : elt -> t -> bool
    val ajout : t -> elt -> t
    val union : t -> t -> t
    val intersection : t -> t -> t
    val vers_liste : t -> elt list 
  end
  
module MakeL (E : ELT) : S with type elt = E.t

module MakeLSort (E : ELT) : S with type elt = E.t

**ensemble.ml**

module type ELT =
  sig
    type t
    val compare : t -> t -> int
  end 

module type S =
  sig
    type elt
    type t
    val vide : t
    val element_de : elt -> t -> bool
    val ajout : t -> elt -> t
    val union : t -> t -> t
    val intersection : t -> t -> t
    val vers_liste : t -> elt list 
  end

module A : ELT = struct
  type t = int
  let compare n m = n - m
end 

module MakeL (E : ELT) =
  struct
    type elt = E.t
    type t = elt list
    let vide = []
    let rec element_de elt l=match l with
      |[]->false
      |hd::tl->if (compare elt hd)=0 then true else element_de tl
  
    let element_de x l = List.exists (fun y->E.compare x y == 0) l
    let ajout l x = x::l
    let ajout l x = if element_de x l then l else x::l
    let rec union l1 l2 = match l1 with
      | [] -> l2
      | x::tl1 -> union tl1 (ajout l2 x)
      
    let rec intersection l1 l2 = match l1 with
      | [] -> []
      | x::tl1 when (element_de x l2) -> ajout (intersection tl1 l2) x
      | _::tl1 -> intersection tl1 l2
    let rec vers_liste l = l
  end  
  
module L1 = MakeL(A);;

let l1 = L1.vide;;
Printf.printf("%b \n") (L1.element_de 1 l1);;
Printf.printf("%b \n") (L1.element_de 1 (L1.ajout L1.vide 1));;
List.iter (fun x -> Printf.printf("%d ") x) (L1.intersection [1; 2; 3] [2; 3; 4]);;
Printf.printf("\n");;
List.iter (fun x -> Printf.printf("%d ") x) (L1.union [1; 2; 3] [2; 3; 4]);;
Printf.printf("\n");;

(* doit afficher false, true, 2 3, 1 2 3 4 *)


module MakeLSort (E : ELT) : S with type elt = E.t = struct
  type elt = E.t
  type t = elt list

  let vide = []

  let rec element_de x l = match l with
    | [] -> false
    | y::_ when E.compare x y == 0 -> true
    | y::_ when E.compare x y < 0 -> false
    | _::s -> element_de x l

  let rec ajout l x = match l with
    | [] -> [x]
    | y::s when E.compare x y < 0 -> x::l
    | y::s -> y::(ajout s x)

  let rec union l1 l2 = match l1,l2 with
    | [], _ -> l2
    | _, [] -> l1
    | x1::s1, x2::s2 -> if E.compare x1 x2 < 0
      then x1::(union s1 l2)
      else x2::(union l1 s2)

  let rec intersection l1 l2 = match l1,l2 with
    | [], _ -> []
    | _, [] -> []
    | x1::s1, x2::s2 ->
      if E.compare x1 x2 < 0 then intersection s1 l2
      else if E.compare x1 x2 > 0 then intersection l1 s2
      else x1::(intersection s1 s2)

  let vers_liste l = l
end

module L2 = MakeLSort(A);;

let l2 = List.fold_left L2.ajout L2.vide [1; 2; 2; 5; 4; 3];;
List.iter (fun x -> Printf.printf("%d ") x) l2;;
Printf.printf("\n");;

(* doit afficher 1 2 3 4 5 *)

module MakeS (E : ELT) =
  struct
    type elt = E.t
    type t = V | N of t*elt*t
    let vide = V
    
    let rec split x t = match t with
        | V -> V, false, V
        | N(tl, v, tr) ->
          if E.compare x v < 0 then
            let rl, r, rr = split x tl in rl, r, N(rr, v, tr)
          else if E.compare x v > 0 then
            let rl, r, rr = split x tr in N(tl, v, rl), r, rr
          else tl, true, tr
    let rec union a1 a2 = match a1 with
      | V -> a2
      | N(t1, n, t2) -> let s1, _, s2 = split n a2 in N(union s1 t1, n, union s2 t2)
      
      
    let rec intersection t1 t2 =
        match t1, t2 with
        | V, _ -> V
        | _, V -> V
        | t1, t2 ->
          let vmax, new_t2 = sup_max t2
          in let l1, contained, _ = split vmax t1
          in let res = intersection new_t2 l1
          in if contained then ajout res vmax else res

  end

Commandes pour faire tourner tout ça :
ocamlc -c ensemble.mli
ocamlc -c ensemble.ml
ocamlc -o test ensemble.cmo
./test

**Questions**
*Mettez vos bouts de code entre le = et les guillemets pour avoir la coloration syntaxique*