How to create the IntSet type with core? [joke]

[Malcolm Matalka]

It's very handy cleverness though!

Yaron Minsky <yminsky at janestreet.com> writes:

> We try to be pretty conservative most of the time, but yeah, there's a
> bit of cleverness here....
>
> y
>
> On Mon, Nov 12, 2012 at 3:51 AM, Francois Berenger
> <francois.berenger.working at gmail.com> wrote:
>> I think this google group should be renamed to: ocaml-type-junkies
>> ;)
>>
>> On Friday, November 9, 2012 6:11:14 PM UTC+9, David House 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.ber... 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. ;)
>>> >