okasaki_set.sml

signature Set =
sig
  type Elem
  type Set
  val empty : Set
  val insert : Elem * Set -> Set
  val member: Elem * Set -> bool
end

signature Ordered =
  (* a totally ordered type and its comparison functions *)
sig
  type T
  val eq : T * T -> bool
  val lt : T * T -> bool
  val leq : T * T -> bool
end

functor UnbalancedSet (Element: Ordered) : Set = struct
  type Elem = Element.T

  datatype Tree = E |T of Tree * Elem * Tree

  type Set = Tree

  val empty = E

  fun member (x, E) = false
    | member (x, T (a, y, b)) =
      if Element.lt (x, y) then member (x, a)
      else if Element.lt (y, x) then member (x, b) else true

  fun memberOptimal (x, E, _) = false
    | memberOptimal (x, T(E, y, E), nil) = false
    | memberOptimal (x, T(E, y, E), last) = Element.eq(x, hd (last)) orelse Element.eq(x, y)
    | memberOptimal (x, T(a, y, b), last) =
      if Element.lt(x, y) then memberOptimal(x, a, nil) else memberOptimal(x, b, y :: nil)


  fun insert (x, E) = T (E, x, E)
    | insert (x, s as T (a, y, b)) =
    if Element.lt (x, y) then T (insert (x, a), y, b)
    else if Element.lt (y, x) then T (a, y, insert (x, b))
    else s

  exception Found
  fun insertOptimal (x, E) = T (E, x, E)
    | insertOptimal (x, s as T(l, v, r)) =
      let
        fun inner (elem, E) = T(E, elem, E)
        | inner (elem, T(E, v', E)) =
          if Element.eq(elem, v') then raise Found
          else if Element.lt(elem, v') then T(T(E, elem, E), v', E) else T(E, v', T(E, elem, E))
        | inner (elem, set as T(l', v', r')) =
          if Element.lt (x, v') then T(inner(x, l'), v', r')
          else T(l', v', inner(x, r'))
      in
        inner(x, s)
      end
      handle
        Found => s

end