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

[Malcolm Matalka <mmatalka@gmail.com>]

Hello!

Here is an example of a module where I creates and uses a map where the
key is two tuples.

https://github.com/orbitz/ocaml-pastry/blob/master/lib/pastry/routing_table.ml#L3

Ollie Frolovs <of12343@my.bristol.ac.uk> writes:

> Hello, list!
>
> 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) ?
> 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.
>
> 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?
>
> 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. 
>
> Please help?!
>
> — Ollie