In OCaml, is it possible to define Map in terms of Set?

Question

I have implemented a representation of sets (balanced search trees) in OCaml. It's actually a functor Make of signature

module Make :
  functor (T : ORDERED_TYPE) ->
sig
  type elt = T.t
  type t
  val empty : t
  val cons : elt -> t -> t
  val delete : elt -> t -> t
  val mem : elt -> t -> bool
  val cardinal : t -> int
end

where

 module type ORDERED_TYPE = sig type t val compare : t -> t -> int end

Now I'd like to implement a dictionary like Map in the standard library. It has to have a signature like

 module Make: functor (T : ORDERED_TYPE) -> sig
    type key = T.t
    type +'a t
    ...
 end

where t is the type of dictionaries.

Implementing balanced search trees again is not elegant, so I want to define dictionaries in terms of sets implemented as a functor above. Can I do that?

Answer 1

As Jeffrey noted, you Set interface is not expressive enough to conveniently implement Map on top of it. It would be simpler to implement Set from Map, by defining sets as maps from keys to unit value.

Another possibility, that I would recommend, is to first expose a module of balanced search trees with no encapsulation, with the sole purpose of providing an efficient data structure, that is entirely revealed by the interface. You are then free to reuse it for any data structure you like, including Map and Set, without having to play games to define one in term of the other. This may not be terribly important in this case (defining Set from Map is reasonable for most purposes), but is a better design in the general case, in my opinion.

In a nutshell: if you want to reuse implementations, then expose "implementation modules", and define your "interface modules" on top of them.