okasaki2.2.ml

module type Ord =
sig
  type t
  val lt : t -> t -> bool
  val lte : t -> t -> bool
  val eq : t -> t -> bool
end
 
module IntOrd : Ord with type t = int =
struct
  type t = int
  let lt = (<)
  let lte = (<=)
  let eq = (=)
end
 
module type Set =
sig
  type elem
  type set
  val empty : set
  val insert : elem -> set -> set
  val member : elem -> set -> bool
end
 
module UnbalSet(Elt : Ord) : Set with type elem = Elt.t =
struct
  type elem = Elt.t
  type 'a tree = 
      Leaf 
    | Node of 'a tree * 'a * 'a tree
  type set = elem tree 
 
  let empty = Leaf
  let rec insert x = function
      Leaf -> Node (Leaf, x, Leaf)
    | Node (a, y, b) as s -> 
        if Elt.lt x y then Node (insert x a, y, b)
        else if Elt.lt y x then Node (a, y, insert x b) 
        else s
 
  let member x s = 
    let rec member_aux x s z =
      match s with
          Leaf -> x = z  (* comparing for equality when reaching a leaf *)
        | Node(a, y, b) -> 
            if Elt.lt x y then member_aux x a z   (* only one comparison *)
            else member_aux x b y
    in
      match s with
          Leaf -> false
        | Node(_, y, _) -> member_aux x s y             
end
 
module IntSet = UnbalSet(IntOrd)