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

[Yaron Minsky]

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