From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id PAA03445; Fri, 7 Nov 2003 15:19:38 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id PAA03088 for ; Fri, 7 Nov 2003 15:19:36 +0100 (MET) Received: from hermes.py.intel.com (hermes.py.intel.com [146.152.216.3]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hA7EG3100074 for ; Fri, 7 Nov 2003 15:16:06 +0100 (MET) Received: from petasus.py.intel.com (petasus.py.intel.com [146.152.221.4]) by hermes.py.intel.com (8.12.9-20030918-01/8.12.9/d: outer.mc,v 1.66 2003/05/22 21:17:36 rfjohns1 Exp $) with ESMTP id hA7EG1Ll008746 for ; Fri, 7 Nov 2003 14:16:01 GMT Received: from orsmsxvs040.jf.intel.com (orsmsxvs040.jf.intel.com [192.168.65.206]) by petasus.py.intel.com (8.12.9-20030918-01/8.11.6/d: large-inner.mc,v 1.5 2003/10/14 21:47:05 root Exp $) with SMTP id hA7EFGF1001177 for ; Fri, 7 Nov 2003 14:15:25 GMT Received: from orsmsx331.amr.corp.intel.com ([192.168.65.56]) by orsmsxvs040.jf.intel.com (NAVGW 2.5.2.11) with SMTP id M2003110706160018242 ; Fri, 07 Nov 2003 06:16:00 -0800 Received: from orsmsx409.amr.corp.intel.com ([192.168.65.58]) by orsmsx331.amr.corp.intel.com with Microsoft SMTPSVC(5.0.2195.5329); Fri, 7 Nov 2003 06:16:00 -0800 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable X-MimeOLE: Produced By Microsoft Exchange V6.0.6487.1 Subject: RE: [Caml-list] Efficient and canonical set representation? Date: Fri, 7 Nov 2003 06:15:59 -0800 Message-ID: <3C4C3612EC443546A33E57003DB4F0F914C26E@orsmsx409.jf.intel.com> Thread-Topic: [Caml-list] Efficient and canonical set representation? Thread-Index: AcOk4jqAQkzgs5IpRuej4lmc87sZzwATelEA From: "Harrison, John R" To: , Cc: "Harrison, John R" X-OriginalArrivalTime: 07 Nov 2003 14:16:00.0280 (UTC) FILETIME=[AB568980:01C3A539] X-Scanned-By: MIMEDefang 2.31 (www . roaringpenguin . com / mimedefang) X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 johnh:01 conceptually:01 ocaml:01 caml:01 equality:01 equality:01 sml:01 user-defined:02 necessarily:02 comparison:02 clearer:02 canonical:03 canonical:03 pointer:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk | You basically want O(1) for set equality, I suppose. Actually, no --- perhaps I should have made clearer what I *really* = want. The efficiency of comparison wasn't my motivation, but rather elegance and aesthetics. And I meant "canonical" with respect to ordinary structural equality, not necessarily pointer equality, so the problem is potentially a bit easier than you might have thought. I want to be able to treat an abstract type in a truly abstract way, and not worry about special-purpose equality relations on certain types. Otherwise it's an ugly mess dealing with complicated nestings like sets of pairs of lists of sets. Now, I think the right solution, conceptually speaking, is to allow user-defined equality on abstract types. But as far as I know this = cannot be done in OCaml, and I've never met much enthusiasm for the idea among the CAML or SML experts. So a poor second best is to define abstract types in a canonical way,=20 which was the starting-point of my question. After your remarks and Brian's, I'm starting to wonder if it is possible at all to do what I want. Maybe I should be looking for an impossibility proof instead... John. ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners