How to create the IntSet type with core?

[David House]

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. ;)
>