(******************************************************************************)
(* Introduction ***************************************************************)
(******************************************************************************)

module type SET = sig
  type t 
  type set
  val empty : set 
  val length : set -> int 
  val mem : t -> set -> bool
  val add : t -> set -> set
  val remove : t -> set -> set
  val to_list : set -> t list
end;;



(******************************************************************************)
(* 1. Structures simples ******************************************************)
(******************************************************************************)

(* 1.1. Un exemple ************************************************************)

module IntSetByFun : (SET with type t = int) =
struct
  type t = int
  type set = (int -> bool) * int

  let empty = ((fun x -> false), 0)
  
  let length (f,l) = l 
  
  let mem x (f,l) = (f x)
  
  let add  y (f,l) = 
    if (f y) then (f,l) 
    else ((fun x -> if x = y then true else (f x)) , l+1)

  let remove y (f,l) = 
    if (f y) then ((fun x -> if x = y then false else (f x)) , l-1)
    else (f,l)
        
  let to_list (f,l) =  
    (* n : nombre d'éléments à trouver            *)
    (* i : élément à tester pour son appartenance *)
    let rec to_list_aux n i =
      if n = 0 then
	[]
      else if (f i) then
	i::(to_list_aux (n-1) (i+1)) 
      else
	(to_list_aux n (i+1))
    in to_list_aux l 0
end;;

module S = IntSetByFun;;

let t = S.empty;;
S.to_list t;;
let s = S.add 19 (S.add 52 (S.add 18 (S.add 32 (S.add 2 (S.add 13 (S.add 11 (S.add 9 (S.add 8 t))))))));;
S.to_list s;;
let r = S.remove 13 (S.remove 9 (S.remove 52 s));;
S.to_list r;;