I think this google group should be renamed to: ocaml-type-junkies<br>;)<br><br>On Friday, November 9, 2012 6:11:14 PM UTC+9, David House wrote:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">There is already an Int.Set module! :)

<br>

<br>Here is a five-minute guide to the set / map / hashtable setup inside

<br>core. I'll use the example of hashtables, but the language readily

translates into sets / maps.

<br>

<br>There are two types of hashtables in core. Ones that use polymorphic

<br>comparison, and ones that use a specific comparision function that is

<br>hopefully more efficient and has non-surprising semantics (we

<br>basically think polymorphic comparison, despite its convenience, is

too surprising to be an overall good thing).

<br>

<br>The type of hashtables using polymorphic comparison is ('key, 'value)

<br>Hashtbl.Poly.t. The type of hashtables using, e.g., int comparison for

<br>the keys is 'value Int.Table.t. Given the previous paragraph, you

should always try to use Foo.Table when you can.

<br>

<br>When you create a hashtable (e.g. using [create], [of_alist], or

<br>[t_of_sexp]), you must use the specific module name. I.e. [let table =

<br>Int.Table.create () in]. However, when you already have a hashtable in

<br>your hands, and you want to use accessor functions, you should just

use Hashtbl.foo, regardless of what comparison function it uses.

<br>

<br>To translate into Maps and Sets:

<br>

<br>'value Foo.Table.t  ('key,'value) Hashtbl.Poly.t  Hashtbl.foo

<br>'value Foo.Map.t    ('key,'value) Map.Poly.t      Map.foo

<br>Foo.Set.t           'element Set.Poly.t           Set.foo

<br>

<br>--

<br>

<br>If you have your own type and want to make Table, Map and Set

<br>submodules, it's really easy:

<br>

<br>module T = struct

<br>  type t = ... with compare, sexp

<br>  let hash = (* your hash function, maybe Hashtbl.hash *)

<br>end

<br>include Comparable.Make(T)

<br>include Hashable.Make(T)

<br>

<br>Saying "with compare" generates you an efficient comparison function

<br>specialised to your type. (Note that all component types need to have

<br>comparison functions defined too, whether through "with compare" or

<br>through primitives.) The Comparable.Make functor adds in modules to

<br>make you satisfy the Comparable.S signature (basically the Set and Map

<br>modules, and a few more). The Hashable.Make functor adds in modules to

<br>make you satisfy Hashable.S (basically Hashtbl, as well as some others

<br>like Hash_set). If you don't want the Hashable stuff, there is no need

<br>to define a hash function. (Although Hashtbl.hash is normally not a

<br>bad choice.)

<br>

<br>--

<br>

<br>Here's how this all works under the hood:

<br>

<br>The type of maps is "really" ('key, 'value, 'comparator) Map.t. Maps

<br>contain in their values the function that is used for comparing keys,

<br>i.e. a function of type 'key -> 'key -> int. But what is this

"comparator" thing?

<br>

<br>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.

<br>But this presents a problem because of functions like Map.merge, which

<br>takes two maps and combines them. You need to know that the comparison

functions are identical, but how can you do this?

<br>

<br>So we have this extra comparator phantom type. Nothing in the actual

<br>representation has a type involving 'comparator: it's just for static

<br>checking. If you want to have a new comparison function, you must mint

<br>a new comparator type. (Including the Comparable signature does this

<br>for you.)

<br>

<br>I originally wrote this last section with hashtables in mind, but it

<br>appears that hashtables work slightly differently: they just assert

<br>that the hashing functions are physically equal inside [merge]; you

<br>don't get a compile-time error for something like [Hashtbl.merge

<br>(Int.Table.create ()) (String.Table.create ())].

<br>

<br>On Fri, Nov 9, 2012 at 8:14 AM, Francois Berenger

<br><<a href="javascript:" target="_blank" gdf-obfuscated-mailto="Ikv84FzJ7D8J">francois.ber...@<wbr>gmail.com</a>> wrote:

<br>> Hello,

<br>>

> I'm converting some standard code to use core.

<br>>

<br>> How do I do this in core:

<br>>

<br>> module IntSet =

<br>>   Set.Make

<br>>     (struct

<br>>       let compare = Pervasives.compare

<br>>       type t = int

<br>>     end)

<br>>

<br>> Thanks a lot,

<br>> F.

<br>>

<br>> PS: yes, I opened Core.Std and did not die from it. ;)

<br>>

<br></blockquote>