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

module Iset: ISET = struct

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

  let empty = []

  let rec add x = function
    | [] -> [x]
    | y :: _ as s when x = y -> s
    | y :: _ as s when x < y -> x :: s
    | y :: s -> y :: add x s

  let rec mem x = function
    | [] -> false
    | y :: _ when x <= y -> x = y
    | _ :: s -> mem x s

  let rec union s1 s2 = match s1, s2 with
    | [], s | s, [] ->
        s
    | x1 :: r1, x2 :: r2 when x1 = x2 ->
        x1 :: union r1 r2
    | x1 :: r1, x2 :: _ when x1 < x2 ->
        x1 :: union r1 s2
    | _, x2 :: r2 ->
        x2 :: union s1 r2

end

(* L'intérêt de faire du type t un type abstrait est qu'on peut alors
   garantir l'invariant que la liste est toujours triée dans l'ordre
   croissant et sans doublons. *)

This document was generated using caml2html