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

module type ISET = sig
  type t
  type elt
  val empty: t
  val add: elt -> t -> t
  val union: t -> t -> t
  val mem: elt -> t -> bool
end

module Set(E: ELT): ISET with type elt = E.t = struct

  type elt = E.t

  type t = elt list
    (* triée par ordre croissant, sans doublons *)

  let empty = []

  let rec add x = function
    | [] -> [x]
    | y :: tl as s ->
        let c = E.compare x y in
        if c = 0 then s
        else if c < 0 then x :: s
        else y :: add x s

  let rec mem x = function
    | [] -> false
    | y :: s ->
        let c = E.compare x y in
        c = 0 || c > 0 && mem x s

  let rec union s1 s2 = match s1, s2 with
    | [], s | s, [] ->
        s
    | x1 :: r1, x2 :: r2 ->
        let c = E.compare x1 x2 in
        if c = 0 then union r1 r2
        else if c < 0 then x1 :: union r1 s2
        else x2 :: union s1 r2

end

(* Le code est écrit un peu différemment de celui de l'exercice 2.42
   pour éviter d'appeler plusieurs fois E.compare sur les mêmes
   éléments. (E.compare est potentiellement maintenant une comparaison
   coûteuse.) *)

This document was generated using caml2html