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

[Ollie Frolovs <of12343@my.bristol.ac.uk>]

Thank you David, Yaron, Mark & Malcolm! 

I managed to replace the associative list with a map and now my OCaml implementation of "Dynamic Programming Treatment of the Travelling Salesman Problem” (Bellman, 1961) can easily handle N=20 which is more than enough for my project since i'm using clustering techniques to split the graph into subgraphs. I also learned a lot about modules, interfaces, maps and even the basics of functors. So much to learn still! 

Thanks again.

— Ollie

On 14 Nov 2013, at 12:11, David House <dhouse@janestreet.com> wrote:

> 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