[Caml-list] Creating a Map from custom type

[Caml-list] Creating a Map from custom type

[Ollie Frolovs]

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

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

[David Allsopp]

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 

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

[Malcolm Matalka]

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

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

[Mark Shinwell]

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

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

[Yaron Minsky]

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

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

[David House]

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

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

[Ollie Frolovs]

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