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 UAA05206; Mon, 10 Nov 2003 20:49:21 +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 UAA04963 for ; Mon, 10 Nov 2003 20:49:20 +0100 (MET) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hAAJnK129682 for ; Mon, 10 Nov 2003 20:49:20 +0100 (MET) Received: from localhost (localhost [127.0.0.1]) by lri.lri.fr (8.12.10/jtpda-5.4) with ESMTP id hAAJS5UW026512 for ; Mon, 10 Nov 2003 20:28:05 +0100 (MET) Date: Mon, 10 Nov 2003 20:28:05 +0100 (MET) From: Julien Signoles X-X-Sender: signoles@lri To: caml-list@inria.fr Subject: RE: [Caml-list] Efficient and canonical set representation? In-Reply-To: Message-ID: References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-MailScanner: Found to be clean X-Loop: caml-list@inria.fr X-Spam: no; 0.00; signoles:01 signoles:01 lri:01 caml-list:01 pons:01 hash:01 hypothesis:01 implemented:01 lri:01 filliatr:01 mcvoy:01 fernandez:01 equality:01 nov:01 polymorphic:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Mon, 10 Nov 2003, Diego Olivier Fernandez Pons wrote: > Patricia sets seem to be what you are looking for. > (1). Efficient usual operations (lookup, insertion, union) > (2). Structural equality > > Their only problem is that they cannot handle polymorphic orderable > types but only integers... > > Hash the data, use this key to insert it in a patricia map and solve > the collisions by chaining in an ordered list (with the polymorphic > [compare] function). (1) and (2) still hold under usual hypothesis on > the rate of collisions. > > A few changes to JCF's implementation should be enough. I think JCF's Hmap module is what you want. A hmap is a map over hash-consed values implemented as Patricia Trees. See http://www.lri.fr/~filliatr/software.en.html for more details. Julien Signoles -- mailto:Julien.Signoles@lri.fr ; http://www.lri.fr/~signoles "In theory, practice and theory are the same, but in practice they are different" (Larry McVoy) ------------------- 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