From: Ollie Frolovs <of12343@my.bristol.ac.uk>
To: caml users <caml-list@inria.fr>
Subject: [Caml-list] Creating a Map from custom type
Date: Thu, 14 Nov 2013 10:39:49 +0000 [thread overview]
Message-ID: <7389AC6E-C25D-43B3-9A39-E59F92EF35AB@my.bristol.ac.uk> (raw)
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
next reply other threads:[~2013-11-14 10:39 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-11-14 10:39 Ollie Frolovs [this message]
2013-11-14 10:56 ` David Allsopp
2013-11-14 11:02 ` Malcolm Matalka
2013-11-14 11:21 ` Mark Shinwell
2013-11-14 12:03 ` Yaron Minsky
2013-11-14 12:11 ` David House
2013-11-15 9:36 ` Ollie Frolovs
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=7389AC6E-C25D-43B3-9A39-E59F92EF35AB@my.bristol.ac.uk \
--to=of12343@my.bristol.ac.uk \
--cc=caml-list@inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).