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

[Francois Berenger]

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 <javascript:>> 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. ;) 
> > 
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ocaml.org/pipermail/core/attachments/20121112/6209c199/attachment-0001.html>