From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 202A67EE25 for ; Thu, 14 Nov 2013 11:56:41 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of dra-news@metastack.com) identity=pra; client-ip=62.13.149.95; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dra-news@metastack.com"; x-sender="dra-news@metastack.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of dra-news@metastack.com designates 62.13.149.95 as permitted sender) identity=mailfrom; client-ip=62.13.149.95; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dra-news@metastack.com"; x-sender="dra-news@metastack.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@outmail149095.authsmtp.com) identity=helo; client-ip=62.13.149.95; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="dra-news@metastack.com"; x-sender="postmaster@outmail149095.authsmtp.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Am8BACSrhFI+DZVfnGdsb2JhbABagmZZU78ggSEWDgEBAQEBCAsJCRQogiUBAQEDAScTMxELAgEIGAoUEDIlAgQbE4dgBwMJwACPLjiDIIERA5gQgS+UBYIq X-IPAS-Result: Am8BACSrhFI+DZVfnGdsb2JhbABagmZZU78ggSEWDgEBAQEBCAsJCRQogiUBAQEDAScTMxELAgEIGAoUEDIlAgQbE4dgBwMJwACPLjiDIIERA5gQgS+UBYIq X-IronPort-AV: E=Sophos;i="4.93,699,1378850400"; d="scan'208";a="42719810" Received: from outmail149095.authsmtp.com ([62.13.149.95]) by mail2-smtp-roc.national.inria.fr with ESMTP; 14 Nov 2013 11:56:40 +0100 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt15.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rAEAud5h085262 for ; Thu, 14 Nov 2013 10:56:39 GMT Received: from romulus.metastack.com (cpc1-cmbg5-0-0-cust241.5-4.cable.virginm.net [81.98.252.242]) (authenticated bits=0) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rAEAubPp024214 for ; Thu, 14 Nov 2013 10:56:37 GMT Received: from remus.metastack.local (remus.metastack.com [172.16.0.1]) by romulus.metastack.com (8.14.2/8.14.2) with ESMTP id rAEAuaSs009642 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=FAIL) for ; Thu, 14 Nov 2013 10:56:36 GMT Received: from Remus.metastack.local ([fe80::547c:3c42:e1da:eda2]) by Remus.metastack.local ([fe80::547c:3c42:e1da:eda2%10]) with mapi id 14.03.0158.001; Thu, 14 Nov 2013 10:56:36 +0000 From: David Allsopp To: caml users Thread-Topic: [Caml-list] Creating a Map from custom type Thread-Index: AQHO4SXjTbJoMyUQME6DuycmKVsrtJokioMg Date: Thu, 14 Nov 2013 10:56:35 +0000 Message-ID: References: <7389AC6E-C25D-43B3-9A39-E59F92EF35AB@my.bristol.ac.uk> In-Reply-To: <7389AC6E-C25D-43B3-9A39-E59F92EF35AB@my.bristol.ac.uk> Accept-Language: en-GB, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [172.16.0.18] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Organization: MetaStack Solutions Ltd. X-Scanned-By: MIMEDefang 2.65 on 172.16.0.20 X-Server-Quench: 6f10d94e-4d1b-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd1ZAARAlZZVg1f DC4bFwdFRBksPQFF ChxFJgxfNlEAUAAU NkdBMnJSNkcdTBdX QSgKX0sqDxtuW2N0 aBpQbQ9YZEBNWEti UVZASkxQEQd2AxgD GRwbTRk8NXQzCTsi BQZiXHRZXUA0cEZ0 QgBSQ2wGMW5kPX0b BEEKagJVJQBXLBdF aE1/VHEIaGVWZ380 FlAlBR1jdQZ0ISFR BwUMNk4nCW0REzcg RhYNVTxnOEQdDysp KBluIUMHAEEUelkj KVZJ X-Authentic-SMTP: 61633634383431.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 81.98.252.242/25 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. Subject: RE: [Caml-list] Creating a Map from custom type 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 - >=20 > I defined a datatype in subroutes.mli: >=20 > open Core.Std >=20 > (** A data structure to store solved subproblems for > dynamic programming (Bellman 1961) approach to solving TSP *) > type t >=20 > (** The empty data structure *) > val empty : t >=20 > (** Store a solution to a subproblem *) > val add : t -> (int list * int) -> (int * int list) -> t >=20 > (** Find a solution to a subproblem *) > val find : t -> (int list * int) -> (int * int list) option >=20 > (** 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 >=20 > My current implementation uses associative lists, in subroute.ml: >=20 > open Core.Std > type t =3D ((int list * int) * (int * int list)) list > let empty =3D [] > let to_list x =3D x > let add t k v =3D List.Assoc.add t k v > let find t k =3D List.Assoc.find t k >=20 > 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. >=20 > Assuming that i do need to provide a comparator, what i don't understand > is this - >=20 > On page 272 of RWO they create a comparator for a string to int Map as > following: >=20 > module Reverse =3D Comparator.Make(struct > type t =3D string > let sexp_of_t =3D String.sexp_of_t > let t_of_sexp =3D String.t_of_sexp > let compare x y =3D 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 =3D (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 simp= ler 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 =3D Map.Make(struct type t =3D (int list * int) let compare = =3D compare end);; (I would sometimes choose to write let compare =3D Pervasives.compare as le= t compare =3D 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 wh= at the ordering is, you simply need one!) HTH, David=20