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

module type Set = sig
  type elt
  type t

  val vide : t
  val cardinal : t -> int
  val appartient : elt -> t -> bool
  val ajout : elt -> t -> t
  val compare : t -> t -> int

  val union : t -> t -> t
  val min : t -> elt
  val fold : (elt -> 'a -> 'a)  -> t -> 'a -> 'a
  val for_all : (elt -> bool) -> t -> bool
end

module Ensemble(X:TypeOrdonne) : Set with type elt = X.t = struct
  type elt = X.t
  type t = X.t list

  let vide = []
  let cardinal = List.length
  let appartient = List.mem
  let ajout x l = x::l
  let union = (@)
  let compare l1 l2 = 
    let s1 = List.sort X.compare l1 in
    let s2 = List.sort X.compare l2 in
    let rec comp l1 l2 = 
      match l1,l2 with
        [] , [] -> 0
      | _ , [] -> 1
      | [] , _ -> -1
      | x1::r1 , x2::r2 -> 
          let c = X.compare x1 x2 in
          if c=0 then comp r1 r2 else c
    in comp s1 s2
         
  let min l = 
    match List.sort X.compare l with
        [] -> raise Not_found
      | x::_ -> x
               
  let fold f s acc = List.fold_left (fun acc x -> f x acc) acc s
  let for_all = List.for_all
end

This document was generated using caml2html