How to create the IntSet type with core?
Johan Mazel
johan.mazel at gmail.com
Mon Nov 26 07:43:29 GMT 2012
I tried to create some submodule as explained in the second paragraph:
"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)"
I however get some syntax error with "with".
Is there some special tricks involved in terms of compilation
(preprocessing maybe) ?
Le vendredi 9 novembre 2012 18:11:14 UTC+9, David House a écrit :
>
> 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/20121125/f64f8aba/attachment-0001.html>
More information about the core
mailing list