I've recently tried to extend the Map in the standard library with extra
functionality. This is what I've tried doing:

In a file my_map.ml:

module type S =
  sig
    include Map.S
    val find_lt: key -> 'a t -> 'a
    val find_gt: key -> 'a t -> 'a
  end

module Make(Ord: Map.OrderedType) = struct
  include Map.Make(Ord)

  let find_almost move_f x n =
    let rec loop lastval n =
      match n, lastval with
      | Empty, None   -> raise Not_found
      | Empty, Some i -> i
      | Node(l, v, d, r, _) ->
          let c = Ord.compare x v in
          let lastval', next = move_f c lastval l d r in
          loop lastval' next
  in loop None n

  let move_lt c lastval l d r =
    if c <= 0 then lastval, l else Some d, r

  let move_gt c lastval l d r =
    if c < 0  then Some d, l else lastval, r

  let find_gt x n = find_almost move_gt x n
  let find_lt x n = find_almost move_lt x n
end

Can anyone tell me why the compiler complained about Empty being an unbound
constructor when it's declared in Map.Make, which I include?

Thanks
Yotam