The below post is mostly lifted from an email I sent to the Core mailing list. It explains the type hackery we employ in order to get a really nice interface for maps, sets, hashtables and other such containers. It may look complex, but actually it works out remarkably simple to use, and ends up giving you a good number of static guarantees. I’ll use the example of hashtables, but the language readily translates into sets / maps.

There are two types of hashtables in core. Ones that use polymorphic comparison, and ones that use a specific comparision function that is hopefully more efficient and has non-surprising semantics (we basically think polymorphic comparison, despite its convenience, is too surprising to be an overall good thing).

The type of hashtables using polymorphic comparison is ('key, 'value) Hashtbl.Poly.t. The type of hashtables using, e.g., int comparison for the keys is ‘value Int.Table.t. Given the previous paragraph, you should always try to use Foo.Table when you can.

When you create a hashtable (e.g. using create, of_alist, or t_of_sexp), you must use the specific module name. i.e. let table = Int.Table.create () in. However, when you already have a hashtable in your hands, and you want to use accessor functions, you should just use Hashtbl.foo, regardless of what comparison function it uses.

To translate into Maps and Sets:

'value Foo.Table.t  ('key,'value) Hashtbl.Poly.t  Hashtbl.foo
'value Foo.Map.t    ('key,'value) Map.Poly.t      Map.foo
Foo.Set.t           'element Set.Poly.t           Set.foo

If you have your own type and want to make Table, Map and Set submodules, it’s really easy:

module T = struct
  type t = ... with compare, sexp
  let hash = (* your hash function, maybe Hashtbl.hash *)
end
include Comparable.Make(T)
include Hashable.Make(T)

Saying “with compare” generates you an efficient comparison function specialised to your type. (Note that all component types need to have comparison functions defined too, whether through “with compare” or through primitives.) The Comparable.Make functor adds in modules to make you satisfy the Comparable.S signature (basically the Set and Map modules, and a few more). The Hashable.Make functor adds in modules to make you satisfy Hashable.S (basically Hashtbl, as well as some others like Hash_set). If you don’t want the Hashable stuff, there is no need to define a hash function. (Although Hashtbl.hash is normally not a bad choice.)

Here’s how this all works under the hood:

The type of maps is “really” ('key, 'value, 'comparator) Map.t. Maps contain in their values the function that is used for comparing keys, i.e. a function of type 'key -> 'key -> int. But what is this “comparator” thing?

We can first motivate things by saying: it’s a pain to have to type Int.Map.find for int-maps, String.Map.find for string-maps, etc. etc. It’d be nice to have a single type and use Map.find for everything. But this presents a problem because of functions like Map.merge, which takes two maps and combines them. You need to know that the comparison functions are identical, but how can you do this?

So we have this extra comparator phantom type. Nothing in the actual representation has a type involving ‘comparator: it’s just for static checking. If you want to have a new comparison function, you must mint a new comparator type. (Including the Comparable signature does this for you.)

I originally wrote this last section with hashtables in mind, but due to a wrinkle, hashtables work a little differently. Maps and sets are fully comparator-ified, but we’re yet to completely cut over hashtables. As a result, the following code types but gives a runtime error:

Hashtbl.merge (Int.Table.create ()) (Hashtbl.Poly.create ())

(The situation is not fully terrible: the above example only works if one side is Hashtbl.Poly.) We’re working on fixing this inconsistency – expect to see it in a version of core soon.