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 QAA06075; Fri, 7 Nov 2003 16:27:37 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id QAA05961 for ; Fri, 7 Nov 2003 16:27:36 +0100 (MET) Received: from smtp2.mathworks.com (smtp2.mathworks.com [144.212.95.218]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hA7FRY121241 for ; Fri, 7 Nov 2003 16:27:35 +0100 (MET) Received: from mail-vif.mathworks.com (fred-ce0.mathworks.com [144.212.95.18]) by smtp2.mathworks.com (8.11.7/8.11.7) with ESMTP id hA7FRQ800421; Fri, 7 Nov 2003 10:27:26 -0500 (EST) Received: from MESSAGE-AH.ad.mathworks.com (ex-01-ah.mathworks.com [144.212.95.156]) by mail-vif.mathworks.com (8.11.7/8.11.7) with ESMTP id hA7FRPj26989; Fri, 7 Nov 2003 10:27:25 -0500 (EST) X-MimeOLE: Produced By Microsoft Exchange V6.0.6487.1 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Subject: RE: [Caml-list] Efficient and canonical set representation? Date: Fri, 7 Nov 2003 10:27:25 -0500 Message-ID: Thread-Topic: [Caml-list] Efficient and canonical set representation? Thread-Index: AcOk4jqAQkzgs5IpRuej4lmc87sZzwATelEAAASMXbA= From: "Fred Smith" To: "Harrison, John R" , , X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 fsmith:01 mathworks:01 -fred:01 erayo:01 bilkent:01 caml-list:01 conceptually:01 bug:01 faq:01 faq:01 beginner's:01 beginners:01 arrays:01 bin:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk I guess what you're looking for are sorted arrays: 1) O(log n) lookup and insertion via binary search 2) O(n) union and intersection are simple 3) Equal sets are represented by structurally equivalent objects. -Fred > -----Original Message----- > From: owner-caml-list@pauillac.inria.fr=20 > [mailto:owner-caml-list@pauillac.inria.fr] On Behalf Of=20 > Harrison, John R > Sent: Friday, November 07, 2003 9:16 AM > To: erayo@cs.bilkent.edu.tr; caml-list@inria.fr > Cc: Harrison, John R > Subject: RE: [Caml-list] Efficient and canonical set representation? >=20 >=20 > | You basically want O(1) for set equality, I suppose. >=20 > Actually, no --- perhaps I should have made clearer what I=20 > *really* want. The efficiency of comparison wasn't my=20 > motivation, but rather elegance and aesthetics. And I meant=20 > "canonical" with respect to ordinary structural equality, not=20 > necessarily pointer equality, so the problem is potentially a=20 > bit easier than you might have thought. >=20 > I want to be able to treat an abstract type in a truly=20 > abstract way, and not worry about special-purpose equality=20 > relations on certain types. Otherwise it's an ugly mess=20 > dealing with complicated nestings like sets of pairs of lists of sets. >=20 > Now, I think the right solution, conceptually speaking, is to=20 > allow user-defined equality on abstract types. But as far as=20 > I know this cannot be done in OCaml, and I've never met much=20 > enthusiasm for the idea among the CAML or SML experts. >=20 > So a poor second best is to define abstract types in a canonical way,=20 > which was the starting-point of my question. >=20 > After your remarks and Brian's, I'm starting to wonder if it=20 > is possible at all to do what I want. Maybe I should be=20 > looking for an impossibility proof instead... >=20 > John. >=20 > ------------------- > To unsubscribe, mail caml-list-request@inria.fr Archives:=20 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 ------------------- 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