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

[David Allsopp <dra-news@metastack.com>]

Ollie Frolovs wrote:
> I'm learning how to use Maps in OCaml and after having read the relevant
> chapter in Real World Ocaml i still do not understand what i need to do to
> solve my problem -
> 
> I defined a datatype in subroutes.mli:
> 
> open Core.Std
> 
> (** A data structure to store solved subproblems for
>     dynamic programming (Bellman 1961) approach to solving TSP *)
> type t
> 
> (** The empty data structure *)
> val empty : t
> 
> (** Store a solution to a subproblem *)
> val add : t -> (int list * int) -> (int * int list) -> t
> 
> (** Find a solution to a subproblem *)
> val find : t -> (int list * int) -> (int * int list) option
> 
> (** Convert the data structure to an association list.
>     Useful for printing but much too slow for anything else *)
> val to_list : t -> ((int list * int) * (int * int list)) list
> 
> 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.
> 
> Assuming that i do need to provide a comparator, what i don't understand
> is this -
> 
> On page 272 of RWO they create a comparator for a string to int Map as
> following:
> 
> module Reverse = Comparator.Make(struct
>   type t = string
>   let sexp_of_t = String.sexp_of_t
>   let t_of_sexp = String.t_of_sexp
>   let compare x y = String.compare y x
> end);;
>
> What is the type t - is it the type of the key only? Would, in my case it
> be type t = (int list * int) ?

Yes.

> Is there an easy way to have sexp part auto-generated/ignored? They
> discuss "with sexp" on later pages but it uses functors (which i am not
> yet familiar with) and i found that example very confusing.

Erm, at the risk of a politically-incorrect opinion, you'd be having a simpler time using the Standard Library, rather than Core! However, that maybe because you have to accept needing to read more of RWO first...

> Also, i do not understand the purpose of the comparison function. I just
> store different subroutes, there really isn't anything i would "compare"
> them with/for. I understand the compare function is necessary for the Map
> to be able to find things, but how do i define it for my type in the most
> painless way?

Yes - your data type is simply tuples, so the standard polymorphic compare will work. Using StdLib's Map, it's quite normal to have:

module MyMap = Map.Make(struct type t = (int list * int) let compare = compare end);;

(I would sometimes choose to write let compare = Pervasives.compare as let compare = compare can read oddly)

> I guess what i want, ideally, is like a hash from Python where i could
> just stuff a key and value into and not worry about the implementation. I
> understand that OCaml is strongly typed, so it cannot be that simple but
> as of now i don't know what to do to have this problem solved. I googled
> for explanations but did not find anything useful yet.

There's an example at http://caml.inria.fr/pub/docs/oreilly-book/html/book-ora132.html#toc187 (note that that example defines its compare function in detail, but that's because its choosing to care about the ordering - using Pervasives.compare is more appropriate in your case where you don't care what the ordering is, you simply need one!)

HTH,


David