How to create the IntSet type with core?

[David House]

I wrote these notes up into a blog post here:

https://ocaml.janestreet.com/?q=node/112

On Fri, Nov 9, 2012 at 9:10 AM, David House <dhouse at janestreet.com> wrote:
> There is already an Int.Set module! :)
>
> Here is a five-minute guide to the set / map / hashtable setup inside
> core. 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 it
> appears that hashtables work slightly differently: they just assert
> that the hashing functions are physically equal inside [merge]; you
> don't get a compile-time error for something like [Hashtbl.merge
> (Int.Table.create ()) (String.Table.create ())].
>
> On Fri, Nov 9, 2012 at 8:14 AM, Francois Berenger
> <francois.berenger.working at gmail.com> wrote:
>> Hello,
>>
>> I'm converting some standard code to use core.
>>
>> How do I do this in core:
>>
>> module IntSet =
>>   Set.Make
>>     (struct
>>       let compare = Pervasives.compare
>>       type t = int
>>     end)
>>
>> Thanks a lot,
>> F.
>>
>> PS: yes, I opened Core.Std and did not die from it. ;)
>>