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 0EB237EE25 for ; Fri, 15 Nov 2013 10:36:27 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of of12343@my.bristol.ac.uk) identity=pra; client-ip=209.85.212.181; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="of12343@my.bristol.ac.uk"; x-sender="of12343@my.bristol.ac.uk"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of of12343@my.bristol.ac.uk) identity=mailfrom; client-ip=209.85.212.181; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="of12343@my.bristol.ac.uk"; x-sender="of12343@my.bristol.ac.uk"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-wi0-f181.google.com) identity=helo; client-ip=209.85.212.181; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="of12343@my.bristol.ac.uk"; x-sender="postmaster@mail-wi0-f181.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Av0CAOPphVLRVdS1lGdsb2JhbABagz+tH5JWgSMWDgEBAQEHCwsJEiqCJQEBBAFuCwULCxgNITQBBQEKEgYTEoddAwkGBAEIoh+UdQNhiHyPLzMHgyCBEQOZP4UPiWJBhFM X-IPAS-Result: Av0CAOPphVLRVdS1lGdsb2JhbABagz+tH5JWgSMWDgEBAQEHCwsJEiqCJQEBBAFuCwULCxgNITQBBQEKEgYTEoddAwkGBAEIoh+UdQNhiHyPLzMHgyCBEQOZP4UPiWJBhFM X-IronPort-AV: E=Sophos;i="4.93,706,1378850400"; d="scan'208";a="42920136" Received: from mail-wi0-f181.google.com ([209.85.212.181]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 15 Nov 2013 10:36:26 +0100 Received: by mail-wi0-f181.google.com with SMTP id f4so706130wiw.8 for ; Fri, 15 Nov 2013 01:36:26 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:content-type:mime-version:subject:from :in-reply-to:date:cc:content-transfer-encoding:message-id:references :to; bh=NBmO+XrJTV7JJh+MkqXfEZOHpt8bzMCRhf4bDq+9TEs=; b=UOGM1/4boawwF3OMyP4KZp1SMmIpb2o0+cvrv6OVywfxSWvgBzssibASZ7v2n16XUj uYXDTPLH+2OQC3UZz+rU7iadNP7XWGGvlprv/Vh+kgZW7pePrPI2IJzT1sjO6SZBDK65 1aQl0YY/coqXBp5u1e6D5eoosHmYiqsM5cHB7D5mEKix2essxvQoI+Ntwda6/zKzRUit qHJjIB+KmWaO8Hw60VbpjZox0Kulb/WdmtAA0fTHSLtjuwg6+uC7YYWyfBMTDXy0lWvV YNrHB749Cf3TXi3m8I27AUCjGvk2p/pT9Fjmb73bTDbDMgK1wE274JxWoRL3aumeWQ5B KBUA== X-Gm-Message-State: ALoCoQkIyuoWAat+EdnjLy3N/sYWdVjlqF8uC4i68iv5hsmpIbxX4gpMAVOd6+b9/MENmn+uYh8C X-Received: by 10.180.107.193 with SMTP id he1mr6574182wib.50.1384508186391; Fri, 15 Nov 2013 01:36:26 -0800 (PST) Received: from [10.0.0.92] (94.197.121.163.threembb.co.uk. [94.197.121.163]) by mx.google.com with ESMTPSA id fu1sm3313808wib.8.2013.11.15.01.36.23 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 15 Nov 2013 01:36:25 -0800 (PST) Content-Type: text/plain; charset=windows-1252 Mime-Version: 1.0 (Mac OS X Mail 7.0 \(1822\)) From: Ollie Frolovs In-Reply-To: Date: Fri, 15 Nov 2013 09:36:20 +0000 Cc: David House , Yaron Minsky , Mark Shinwell , Malcolm Matalka Content-Transfer-Encoding: quoted-printable Message-Id: <2AB0CEC4-E3FF-47B1-8554-612BE4CDBB26@my.bristol.ac.uk> References: <7389AC6E-C25D-43B3-9A39-E59F92EF35AB@my.bristol.ac.uk> To: caml users X-Mailer: Apple Mail (2.1822) Subject: Re: [Caml-list] Creating a Map from custom type Thank you David, Yaron, Mark & Malcolm!=20 I managed to replace the associative list with a map and now my OCaml imple= mentation of "Dynamic Programming Treatment of the Travelling Salesman Prob= lem=94 (Bellman, 1961) can easily handle N=3D20 which is more than enough f= or 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 t= he basics of functors. So much to learn still!=20 Thanks again. =97 Ollie On 14 Nov 2013, at 12:11, David House wrote: > To follow up on Mark's example, you can use the following slightly > more general idiom: >=20 > module My_thing =3D struct > module T =3D struct > type t =3D int * string * string with sexp, compare > end > include T > include Comparable.Make(T) >=20 > let do_some_stuff t =3D ... > end >=20 > 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. >=20 > We do this on basically every type in core, since you'll want to use > everything in a set sooner or later :) >=20 > 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: >=20 > module My_thing =3D struct > module T =3D struct > type t =3D ... with sexp, compare, bin_io > let hash =3D Hashtbl.hash > let to_string t =3D ... > let of_string t =3D ... > let module_name =3D "My_lib.My_thing" (* for the toplevel *) > end > include T > include Identifiable.Make(T) >=20 > (* other functions here *) > end >=20 > If you want the string representation to be the same as the sexp > representation, that's possible too with only a little more > clunkiness: >=20 > module My_thing =3D struct > module T =3D struct > module T' =3D struct > type t =3D ... with sexp, compare, bin_io > end > include T' > include Sexpable.To_stringable(T') > let hash =3D Hashtbl.hash > let module_name =3D "My_lib.My_thing" (* for the toplevel *) > end > include T > include Identifiable.Make(T) >=20 > (* other functions here *) > end >=20 > On 14 November 2013 12:03, Yaron Minsky 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: >>=20 >> utop # let map =3D Map.Poly.of_alist_exn [1, "one"; 2, "two"; 3, "three"= ];; >> val map : (int, string) Map.Poly.t =3D >>=20 >> 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. >>=20 >> 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. >>=20 >> y >>=20 >> On Thu, Nov 14, 2013 at 6:21 AM, Mark Shinwell wrote: >>> On 14 November 2013 10:39, Ollie Frolovs wro= te: >>>> 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 ty= pe (int list * int) and the values have the type (int * int list). If i und= erstood it correctly, because the key is a tuple and not one of the built-i= n 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 >>> I think you need something like: >>>=20 >>> module Key =3D struct >>> type t =3D int list * int with sexp, compare >>> end >>>=20 >>> module My_map =3D Map.Make (Key) >>>=20 >>> Then, for example: >>>=20 >>> let map =3D >>> My_map.add My_map.empty >>> ~key:([42], 0) >>> ~data:(1, [2]) >>>=20 >>> 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. >>>=20 >>> Mark >>>=20 >>> -- >>> 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 >>=20 >> -- >> 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