Re: [Caml-list] Creating a Map from custom type

[David House <dhouse@janestreet.com>]

To follow up on Mark's example, you can use the following slightly
more general idiom:

module My_thing = struct
  module T = struct
    type t = int * string * string with sexp, compare
  end
  include T
  include Comparable.Make(T)

  let do_some_stuff t = ...
end

Then My_thing will satisfy the Comparable signature, which means
you'll have My_thing.Map, as well as My_thing.Set, My_thing.equal,
My_thing.(<) etc.

We do this on basically every type in core, since you'll want to use
everything in a set sooner or later :)

The "gold standard" for such types is the Identifiable signature. This
is basically the union of the Comparable signature, the Hashable
signature (which gives you hashtables, hash-sets etc.) and the
Stringable signature (to/from strings). You can get there with just a
little more work:

module My_thing = struct
  module T = struct
    type t = ... with sexp, compare, bin_io
    let hash = Hashtbl.hash
    let to_string t = ...
    let of_string t = ...
    let module_name = "My_lib.My_thing" (* for the toplevel *)
  end
  include T
  include Identifiable.Make(T)

  (* other functions here *)
end

If you want the string representation to be the same as the sexp
representation, that's possible too with only a little more
clunkiness:

module My_thing = struct
  module T = struct
    module T' = struct
      type t = ... with sexp, compare, bin_io
    end
    include T'
    include Sexpable.To_stringable(T')
    let hash = Hashtbl.hash
    let module_name = "My_lib.My_thing" (* for the toplevel *)
  end
  include T
  include Identifiable.Make(T)

 (* other functions here *)
end

On 14 November 2013 12:03, Yaron Minsky <yminsky@janestreet.com> wrote:
> It's worth noting that if you want a simply polymorphic map, you can
> have one, you just need to be explicit about what you're doing:
>
> utop # let map = Map.Poly.of_alist_exn [1, "one"; 2, "two"; 3, "three"];;
> val map : (int, string) Map.Poly.t = <abstr>
>
> which is probably the lowest-pain approach.  Polymorphic compare
> (which is what this is based on) has some downside, but is perfectly
> good for many use-cases.  RWO covers in detail the pitfalls of
> polymorphic compare, but it doesn't mean you should avoid it,
> especially when you're getting started.
>
> As for David's point about Core vs the stdlib, I think creating a map
> with a polymorphic comparison function is actually quite a bit easier
> in Core than it is with the stdlib, since no functor application is
> required.
>
> y
>
> On Thu, Nov 14, 2013 at 6:21 AM, Mark Shinwell <mshinwell@janestreet.com> wrote:
>> On 14 November 2013 10:39, Ollie Frolovs <of12343@my.bristol.ac.uk> wrote:
>>> My current implementation uses associative lists, in subroute.ml:
>>>
>>> open Core.Std
>>> type t = ((int list * int) * (int * int list)) list
>>> let empty = []
>>> let to_list x = x
>>> let add t k v = List.Assoc.add t k v
>>> let find t k = List.Assoc.find t k
>>>
>>> I would like to use a Map instead. The key for my Map must have the type (int list * int) and the values have the type (int * int list). If i understood it correctly, because the key is a tuple and not one of the built-in simple data types (string, int, etc), because of this i have to provide a custom comparator. This is first thing that i am not sure of.
>>
>> I think you need something like:
>>
>> module Key = struct
>>   type t = int list * int with sexp, compare
>> end
>>
>> module My_map = Map.Make (Key)
>>
>> Then, for example:
>>
>>   let map =
>>     My_map.add My_map.empty
>>       ~key:([42], 0)
>>       ~data:(1, [2])
>>
>> The "with compare" auto-generates a "compare" function for
>> you.  Using explicit comparison functions, as Core strongly
>> encourages, does unfortunately mean a bit more code at times
>> but is arguably vastly more sustainable as your codebase
>> grows.  In such scenarios it becomes increasingly unlikely
>> that the correct notion of comparison on one of your many
>> abstract types coincides with the structural comparison
>> on whatever implementation those types happen to have today.
>>
>> Mark
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa.inria.fr/sympa/arc/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs