From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.8 required=5.0 tests=DNS_FROM_RFC_POST, HTML_MESSAGE,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 6ED72BC37 for ; Thu, 17 Sep 2009 09:31:48 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AiMCAM+CsUrRVdvbkGdsb2JhbACCKC6PDYkEPwEBAQEJCQwHEwOwbIEwkDsBAwIEhBQF X-IronPort-AV: E=Sophos;i="4.44,402,1249250400"; d="scan'208,217";a="34450749" Received: from mail-ew0-f219.google.com ([209.85.219.219]) by mail3-smtp-sop.national.inria.fr with ESMTP; 17 Sep 2009 09:31:47 +0200 Received: by ewy19 with SMTP id 19so130346ewy.44 for ; Thu, 17 Sep 2009 00:31:47 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:cc:message-id:from:to :in-reply-to:content-type:mime-version:subject:date:references :x-mailer; bh=U/k3LEMbcUAbpqbMAzhDupffhmhmG0/YgKK9ySzRSno=; b=U+NiFGaPDzExOWWt+gqLhb3nxAEyL0AXCi0nB4q/qWSmMbN6IbZAdeWcOwrSb5s7IA ERY9oXnyVpB968d3G2tz3KqOwe1G4UwjVoz8aB1GF4AurDBzNJmNsJQzkPJnaFFsELqH xUVlZsDu/S0gRbXFHwjQuvMWMEthomrPPQrhk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=cc:message-id:from:to:in-reply-to:content-type:mime-version:subject :date:references:x-mailer; b=pzo7T5hc9uSwQ0SZYa7+OS7IBg3QOW4koZgZyKbJQKqKAHSO0Yn5y4V2jfuDHz9xz9 igWbgscDrVjSAZTaYuqx0SGVbGAwIHGlMbQKhc6mj+0O+xFh5cRMuZCKMc191v+EGzp7 oe9mqC1GeCM4VN8l2ALwkpj+Hz2M3JOvaMXg4= Received: by 10.211.132.3 with SMTP id j3mr179938ebn.81.1253172707256; Thu, 17 Sep 2009 00:31:47 -0700 (PDT) Received: from ?172.16.16.12? (AGrenoble-257-1-104-59.w90-27.abo.wanadoo.fr [90.27.23.59]) by mx.google.com with ESMTPS id 7sm914878eyb.12.2009.09.17.00.31.43 (version=TLSv1/SSLv3 cipher=RC4-MD5); Thu, 17 Sep 2009 00:31:45 -0700 (PDT) Cc: caml-list@yquem.inria.fr Message-Id: <710694E5-BA66-4B84-AE91-9CC5289EF3D6@gmail.com> From: Vincent Aravantinos To: Matthias Puech In-Reply-To: <4AB15AD4.4030809@cs.unibo.it> Content-Type: multipart/alternative; boundary=Apple-Mail-6--12406284 Mime-Version: 1.0 (Apple Message framework v936) Subject: Re: [Caml-list] Sets and home-made ordered types Date: Thu, 17 Sep 2009 09:31:40 +0200 References: <4AB11511.2050506@cs.unibo.it> <002e01ca36fd$37656c60$a6304520$@metastack.com> <4AB15AD4.4030809@cs.unibo.it> X-Mailer: Apple Mail (2.936) X-Spam: no; 0.00; home-made:01 intersection:01 pervasives:01 cstr:01 cstr:01 cheers:01 intersection:01 pervasives:01 cheers:01 caml-list:01 constructor:01 constructor:01 undefined:01 undefined:01 pair:01 --Apple-Mail-6--12406284 Content-Type: text/plain; charset=ISO-8859-1; format=flowed; delsp=yes Content-Transfer-Encoding: quoted-printable Le 16 sept. 09 =E0 23:38, Matthias Puech a =E9crit : >> In terms of a strictly pure implementation of a functional Set, it =20= >> would be >> odd to have a "find" function - you'll also get some interesting =20 >> undefined >> behaviour with these sets if you try to operations like union and >> intersection but I guess you're already happy with that! > > It seems to me rather natural to have it: otherwise, what's the =20 > point of > being able to provide your own compare, beside just checking for > membership of the class? I think that the ability to define your own 'compare' function in the =20= original Set module is more there to deal with different *orders* rather than =20 different equalities. > type t =3D F of t | G of t * t | A | B > I want to index values of type t according to their first constructor. > So in my set structure, there will be at most one term starting with > each constructor, and: > find (F(A)) (add (F(B)) empty) will return F(B) > > With a Set.find, it's easy: > > let compare x y =3D match x,y with > | (F,F | G,G | A,A | B,B) -> 0 > | _ -> Pervasives.compare x y > > module S =3D Set.Make ... > > With the Map solution, i'm obliged to define: > > type cstr =3D F' | G' | A' | B' > let cstr_of x =3D F _ -> F' | G _ -> G' etc. > > and then make a Map : cstr |--> t, which duplicates the occurrence of > the constructor (F' in the key, F in the element). Besides, I'm > responsible for making sure that the pair e.g. (G', F(A)) is not =20 > added. But maybe that's not so much of a duplicate that you think. Actually cstr is the type of your class equivalence on type t. It happens that you can have a representative for each class equivalence, which you store in your map, but that's not the class equivalence itself. What I mean is that if you see this through this particular interpretation, it's rather natural to have two types for two different kinds of objects. I think furthermore that this is easier to reason about. For instance the 'compare' function you define is actually not meant to compare objects of type t but their equivalence class representatives. Defining a good compare when reasoning about type t may be hard while when you are aware that you actually want a compare between class representatives this can turn out to be much easier (I ran recently in this kind of problem and this was definitely the case). Actually that's just one of the usual advantages of using distinct types to represent distinct notions. But your problem being trivially solved by your extension of Set with a 'find' function I understand that you would prefer this solution. Cheers, -- Vincent Aravantinos PhD Student - LIG - CAPP Team Grenoble, France +33.6.11.23.34.72 vincent.aravantinos@imag.fr http://membres-lig.imag.fr/aravantinos/ --Apple-Mail-6--12406284 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

Le 16 = sept. 09 =E0 23:38, Matthias Puech a =E9crit :

In terms of a strictly pure = implementation of a functional Set, it would = be
odd to have a "find" = function - you'll also get some interesting = undefined
behaviour with these = sets if you try to operations like union and
intersection but I guess you're already happy with = that! 

It seems to me rather natural to have = it: otherwise, what's the point of
being able to provide your own = compare, beside just checking for
membership of the = class?

I think that the ability to = define your own 'compare' function in the original
Set module = is more there to deal with different *orders* rather than = different
equalities.

type t =3D F of t | G of t * t | A | B
I want to = index values of type t according to their first constructor.
So in my = set structure, there will be at most one term starting with
each = constructor, and:
find (F(A)) (add (F(B)) empty) will return = F(B)

With a Set.find, it's easy:

let compare x y =3D match = x,y with
| (F,F | G,G | A,A | B,B) -> 0
| _ -> = Pervasives.compare x y

module S =3D Set.Make ...

With the = Map solution, i'm obliged to define:

type cstr =3D F' | G' | A' | = B'
let cstr_of x =3D F _ -> F' | G _ -> G' etc.

and then = make a Map : cstr |--> t, which duplicates the occurrence of
the = constructor (F' in the key, F in the element). Besides, = I'm
responsible for making sure that the pair e.g. (G', F(A)) is not = added.

But maybe that's not so much = of a duplicate that you think. 
Actually cstr is the type = of your class equivalence on type t.
It happens that you can = have a representative for each class 
equivalence, which = you store in your map, but that's not the = class 
equivalence itself.

What = I mean is that if you see this through this = particular
interpretation, it's rather natural to have two = types for two different
kinds of objects. I think furthermore = that this is easier to reason
about. For instance the = 'compare' function you define is actually not
meant to compare = objects of type t but their equivalence = class 
representatives. Defining a good compare when = reasoning about type t
may be hard while when you are aware = that you actually want a compare
between class representatives = this can turn out to be much easier
(I ran recently in this = kind of problem and this was definitely the
case). Actually = that's just one of the usual advantages of = using 
distinct types to represent distinct notions. = But your problem being
trivially solved by your = extension of Set with a 'find' function I
understand = that you would prefer = this solution.

Cheers,
--
Vincent Aravantinos
PhD Student - = LIG - CAPP Team
Grenoble, = France
+33.6.11.23.34.72

= --Apple-Mail-6--12406284--