okasaki2.1.ml

(* "comparable" interface *)
module type Ord =
sig
  type t
  val lt : t -> t -> bool
  val lte : t -> t -> bool
  val eq : t -> t -> bool
end
 
(* implementation of Ord for integers *)
module IntOrd : Ord with type t = int =
struct
  type t = int
  let lt = (<)
  let lte = (<=)
  let eq = (=)
end
 
(* Set interface *)
module type Set =
sig
  (* abstract element and set type *)         
  type elem 
  type set  
  (* set operations *)
  val empty : set
  val insert : elem -> set -> set
  val member : elem -> set -> bool
end
 
(* implementation of a set paramterized over Ord *)
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 rec member x = function
      Leaf -> false
    | Node (a, y, b) ->
        if Elt.lt x y then member x a               (* two comparisons *)
        else if Elt.lt y x then member x b
        else true
end
 
(* instanciation of a set of comparable integers *)
module IntSet = UnbalSet(IntOrd)