In OCaml, is it possible to define Map in terms of Set?
functor, module, ocaml
Solution
Seems to me a map is a (partial) function, which is a set of ordered pairs. If you define your comparison function correctly I think it can be done. You might have to add a function to the Set interface to account for the fact that two values can compare equal for purposes of membership but not actually be equal values. It doesn't seem possible to define the lookup function for the map with the current interface.
Problem
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?