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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 69AE77EE25 for ; Thu, 14 Nov 2013 12:02:18 +0100 (CET) Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of mmatalka@gmail.com) identity=pra; client-ip=209.85.212.173; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="mmatalka@gmail.com"; x-sender="mmatalka@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of mmatalka@gmail.com designates 209.85.212.173 as permitted sender) identity=mailfrom; client-ip=209.85.212.173; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="mmatalka@gmail.com"; x-sender="mmatalka@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-wi0-f173.google.com) identity=helo; client-ip=209.85.212.173; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="mmatalka@gmail.com"; x-sender="postmaster@mail-wi0-f173.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnoCAEyshFLRVdStlGdsb2JhbABaDoJYWYNIvCuBIRYOAQEBAQcLCwkSKoIlAQEEASMEGQEbEQwBAwELBgULAwwCBSECAg8BBA8RAQUBIhMbh1MBAwkGAQQIoQKMBFODCYRdChknDWSJAQEBBAyBHY4DMweCa4FGA5gQkCBBhBQ/ X-IPAS-Result: AnoCAEyshFLRVdStlGdsb2JhbABaDoJYWYNIvCuBIRYOAQEBAQcLCwkSKoIlAQEEASMEGQEbEQwBAwELBgULAwwCBSECAg8BBA8RAQUBIhMbh1MBAwkGAQQIoQKMBFODCYRdChknDWSJAQEBBAyBHY4DMweCa4FGA5gQkCBBhBQ/ X-IronPort-AV: E=Sophos;i="4.93,699,1378850400"; d="scan'208";a="35499480" Received: from mail-wi0-f173.google.com ([209.85.212.173]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 14 Nov 2013 12:02:17 +0100 Received: by mail-wi0-f173.google.com with SMTP id ey16so537156wid.0 for ; Thu, 14 Nov 2013 03:02:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type:content-transfer-encoding; bh=r8yo80k1f4jH+ZchLAY126jR/wU+zWpROKZQiJDOoU0=; b=fMZD7gbREinqKJb+pqsG0THbNmLZEQYeMi2hMlGhKvI4Pv0QMXcqJB5O1PhLj8tL/K 7PN3jdkQX3IZ026JQAvRH8d/Pw9lsUmeKOg9ZBR+EPHLyhzb4O8SLw0CZAm2/IGkHFai cTiyJqEV05N8sLac7xmWs+cR4CPdC+sot5aqyJ5SwQLAdBwBjV27BO1upbpYLaf5noUv 6xrZ59h1gVkXma15yNAYAZsfEUTNCAQyFhd80LMVZUvuo7BHQtcasLuhtsaTs5oBAI7U kgDT2gJWakFatyJhOzcj1Q8/7dsEWnUBXBZ0f9M125CgJ8W9hzSp9qIs2qAfMvHHbfYZ 5vig== X-Received: by 10.180.97.5 with SMTP id dw5mr1807858wib.42.1384426937424; Thu, 14 Nov 2013 03:02:17 -0800 (PST) Received: from localhost ([2a01:7e00::f03c:91ff:fe70:2696]) by mx.google.com with ESMTPSA id gb1sm3815897wic.0.2013.11.14.03.02.16 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 14 Nov 2013 03:02:16 -0800 (PST) From: Malcolm Matalka To: Ollie Frolovs Cc: caml users References: <7389AC6E-C25D-43B3-9A39-E59F92EF35AB@my.bristol.ac.uk> Date: Thu, 14 Nov 2013 11:02:16 +0000 In-Reply-To: <7389AC6E-C25D-43B3-9A39-E59F92EF35AB@my.bristol.ac.uk> (Ollie Frolovs's message of "Thu, 14 Nov 2013 10:39:49 +0000") Message-ID: <87ppq3dz5z.fsf@gmail.com> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Caml-list] Creating a Map from custom type 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 writes: > Hello, list! > > I=E2=80=99m learning how to use Maps in OCaml and after having read the r= elevant chapter in Real World Ocaml i still do not understand what i need t= o do to solve my problem =E2=80=93 > > I defined a datatype in subroutes.mli: > > open Core.Std > > (** A data structure to store solved subproblems for=20 > 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 =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 > > 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 unders= tood it correctly, because the key is a tuple and not one of the built-in s= imple data types (string, int, etc), because of this i have to provide a cu= stom comparator. This is first thing that i am not sure of. > > Assuming that i do need to provide a comparator, what i don=E2=80=99t und= erstand is this =E2=80=93 > > On page 272 of RWO they create a comparator for a string to int Map as fo= llowing: > > 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 =E2=80=93 is it the type of the key only? Would, in my= case it be type t =3D (int list * int) ? > Is there an easy way to have sexp part auto-generated/ignored? They discu= ss =E2=80=9Cwith sexp=E2=80=9D 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=E2=80=99t anything i would =E2= =80=9Ccompare=E2=80=9D 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 ju= st stuff a key and value into and not worry about the implementation. I und= erstand that OCaml is strongly typed, so it cannot be that simple but as of= now i don=E2=80=99t know what to do to have this problem solved. I googled= for explanations but did not find anything useful yet.=20 > > Please help?! > > =E2=80=94 Ollie