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=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id C437BBC37 for ; Thu, 17 Sep 2009 10:41:05 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ah4CAHSTsUpRZ90xkWdsb2JhbACbJwEBAQEJCwoHEwPCSYQYBQ X-IronPort-AV: E=Sophos;i="4.44,402,1249250400"; d="scan'208";a="46747965" Received: from mtaout03-winn.ispmail.ntl.com ([81.103.221.49]) by mail4-smtp-sop.national.inria.fr with ESMTP; 17 Sep 2009 10:40:37 +0200 Received: from aamtaout01-winn.ispmail.ntl.com ([81.103.221.35]) by mtaout03-winn.ispmail.ntl.com (InterMail vM.7.08.04.00 201-2186-134-20080326) with ESMTP id <20090917084036.ASA5579.mtaout03-winn.ispmail.ntl.com@aamtaout01-winn.ispmail.ntl.com>; Thu, 17 Sep 2009 09:40:36 +0100 Received: from romulus.metastack.com ([81.102.132.77]) by aamtaout01-winn.ispmail.ntl.com (InterMail vG.2.02.00.01 201-2161-120-102-20060912) with ESMTP id <20090917084035.TCYW13254.aamtaout01-winn.ispmail.ntl.com@romulus.metastack.com>; Thu, 17 Sep 2009 09:40:35 +0100 Received: from Tenor ([172.16.0.8]) (authenticated bits=0) by romulus.metastack.com (8.14.2/8.14.2) with ESMTP id n8H8eV4W024656 (version=TLSv1/SSLv3 cipher=AES128-SHA bits=128 verify=NO); Thu, 17 Sep 2009 09:40:33 +0100 From: "David Allsopp" To: "'Matthias Puech'" , References: <4AB11511.2050506@cs.unibo.it> <002e01ca36fd$37656c60$a6304520$@metastack.com> <4AB15AD4.4030809@cs.unibo.it> In-Reply-To: <4AB15AD4.4030809@cs.unibo.it> Subject: RE: [Caml-list] Sets and home-made ordered types Date: Thu, 17 Sep 2009 09:39:58 +0100 Message-ID: <005201ca3772$70e81da0$52b858e0$@metastack.com> MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable X-Mailer: Microsoft Office Outlook 12.0 Thread-Index: Aco3Fgz6uvaEi2ekTDSyU7q3uJOCYwAWjWSw Content-Language: en-gb Organization: MetaStack Solutions Ltd. X-Scanned-By: MIMEDefang 2.65 on 81.102.132.77 X-Cloudmark-Analysis: v=1.0 c=1 a=-KxNoFz5fAkA:10 a=wEa39JaL-CwA6j8i0k0A:9 a=ZoMeVNlA_Cj9sQP6Lz84KpDbxVAA:4 X-Spam: no; 0.00; home-made:01 model:01 intersection:01 intersection:01 trivial:01 struct:01 syntax:01 syntax:01 wrote:01 caml-list:01 functions:01 constructor:01 constructor:01 undefined:01 undefined:01 Matthias Puech wrote: > David Allsopp a =E9crit : > > Is it not possible to model your requirement using Map.Make instead = - > > where the keys represent the equivalence classes and the values = whatever > > data you're associating with them? >=20 > Yes, that's exactly the workaround I ended up using, although I'm not > very happy with it because, among other things, these keys/class > disciminant get duplicated (once inside the key, once inside the > element). I'm getting more concrete below. While I agree that the duplication is unfortunate, it is only one word = (the number needed in each instance to store the Constructor value for the = key - you get the Constructor "for free" with a tuple as it's "stored" in the = tag of the block allocated to hold the tuple.) > > 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! > For union and inter, I don't see how their behavior would be = undefined, > since neither the datastructure nor the functions are changed. The element put into the sets on intersection and union is undefined. = Say you have the trivial case with just one equivalence class=20 type u =3D A of int module MySet =3D Set.Make(struct type t =3D u let compare x y =3D 0 end) So your sets will all be singletons. What is the result of: MySet.inter (MySet.singleton (A 1)) (MySet.singleton (A 2)) In 3.11.1, it's the singleton set containing [A 2] but the definition intersection reasonably allows for it to be [A 1] instead. However, this = of itself isn't an argument against having [find] - it's just that what = you're doing already isn't really a set. > Besides, I'm responsible for making sure that the pair e.g. (G', F(A)) = is not added. Jacques Garrigue has a syntax extension (PolyMap, I think is its name) = which may help you here - it allows you to enforce this invariant = automatically (and provides neater syntax for it). But I agree that for your case = adding a "find" method to a custom (i.e. copied) version of Set is probably the = way forward - I'm just not sure that you'll convince the guys at Inria to = add the method to the standard library's version of Set.Make! David