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 RAA26384; Thu, 6 Nov 2003 17:41:11 +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 RAA26240 for ; Thu, 6 Nov 2003 17:41:10 +0100 (MET) Received: from hermes.py.intel.com (hermes.py.intel.com [146.152.216.3]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hA6Gf9127601 for ; Thu, 6 Nov 2003 17:41:09 +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 hA6Gf7Vi003432 for ; Thu, 6 Nov 2003 16:41:07 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 hA6GeJ0e028521 for ; Thu, 6 Nov 2003 16:40:31 GMT Received: from orsmsx332.amr.corp.intel.com ([192.168.65.60]) by orsmsxvs040.jf.intel.com (NAVGW 2.5.2.11) with SMTP id M2003110608410602840 for ; Thu, 06 Nov 2003 08:41:06 -0800 Received: from orsmsx409.amr.corp.intel.com ([192.168.65.58]) by orsmsx332.amr.corp.intel.com with Microsoft SMTPSVC(5.0.2195.5329); Thu, 6 Nov 2003 08:41:06 -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: [Caml-list] Efficient and canonical set representation? Date: Thu, 6 Nov 2003 08:41:04 -0800 Message-ID: <3C4C3612EC443546A33E57003DB4F0F914C26B@orsmsx409.jf.intel.com> Thread-Topic: Efficient and canonical set representation? Thread-Index: AcOkgDH6cwbDbP7ZEdeTmQDQtwIPNA== From: "Harrison, John R" To: Cc: "Harrison, John R" X-OriginalArrivalTime: 06 Nov 2003 16:41:06.0957 (UTC) FILETIME=[C68243D0:01C3A484] X-Scanned-By: MIMEDefang 2.31 (www . roaringpenguin . com / mimedefang) X-Loop: caml-list@inria.fr X-Spam: no; 0.00; johnh:01 ocaml:01 caml:01 variants:01 polymorphic:01 precisely:02 canonical:03 canonical:03 object:03 efficient:05 efficient:05 intersection:07 balanced:07 type:07 represented:07 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Does anyone know a representation of finite sets over an orderable = polymorphic type that's (1) efficient and (2) canonical? Even better would be a CAML or = OCaml implementation. More precisely I'm looking for: 1. Log-time lookup and insertion, and linear-time union, intersection = etc. 2. Equal sets are represented by the same object. For example, ordered lists satisfy (2) but only part of (1), while all = the variants of balanced trees I can remember that satisfy (1) --- AVL trees etc. --- = fail (2). Thanks, 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