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 EAA00747; Wed, 12 Nov 2003 04:54:00 +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 EAA00731 for ; Wed, 12 Nov 2003 04:53:59 +0100 (MET) Received: from hermes.jf.intel.com (fmr05.intel.com [134.134.136.6]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hAC3Yp103573 for ; Wed, 12 Nov 2003 04:35:02 +0100 (MET) Received: from petasus.jf.intel.com (petasus.jf.intel.com [10.7.209.6]) by hermes.jf.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 hAC3ZGfj022655; Wed, 12 Nov 2003 03:35:16 GMT Received: from orsmsxvs040.jf.intel.com (orsmsxvs040.jf.intel.com [192.168.65.206]) by petasus.jf.intel.com (8.11.6-20030918-01/8.11.6/d: inner.mc,v 1.35 2003/05/22 21:18:01 rfjohns1 Exp $) with SMTP id hAC3T0r24625; Wed, 12 Nov 2003 03:29:00 GMT Received: from orsmsx331.amr.corp.intel.com ([192.168.65.56]) by orsmsxvs040.jf.intel.com (SAVSMTP 3.1.1.32) with SMTP id M2003111119344913469 ; Tue, 11 Nov 2003 19:34:49 -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); Tue, 11 Nov 2003 19:34:48 -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: Tue, 11 Nov 2003 19:34:47 -0800 Message-ID: <3C4C3612EC443546A33E57003DB4F0F914C277@orsmsx409.jf.intel.com> Thread-Topic: [Caml-list] Efficient and canonical set representation? Thread-Index: AcOouuSUhEptF47qRY2+gFsBPURXUAAC+sQQ From: "Harrison, John R" To: "Brian Hurt" Cc: "Ocaml Mailing List" , "Harrison, John R" X-OriginalArrivalTime: 12 Nov 2003 03:34:48.0485 (UTC) FILETIME=[EC6D3D50:01C3A8CD] 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 equality:01 tree:02 tree:02 comparison:02 canonical:03 let:04 structural:04 structural:04 efficient:05 obvious:06 balanced:07 i'm:07 i'm:07 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk | I've been batting around ideas for ways to do balanced trees so that = no=20 | matter what order you add things, you always get the same tree. But = even=20 | assuming you could do this, doing a structural compare is still O(N). = So=20 | you might as well let the trees be different. Right, but see my second message --- I'm only interested in canonicity up to structural equality and I'm happy with O(N) comparison. So it's just the "no matter what order you add things you get the same tree" property that I care about. But it's not yet obvious to me whether I can even achieve that much. 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