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 OAA24286; Mon, 10 Nov 2003 14:25:44 +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 OAA24163 for ; Mon, 10 Nov 2003 14:25:43 +0100 (MET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hAADPg126513 for ; Mon, 10 Nov 2003 14:25:42 +0100 (MET) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.10/jtpda-5.4) with ESMTP id hAADPcqY006499 ; Mon, 10 Nov 2003 14:25:38 +0100 (CET) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id OAA44666 ; Mon, 10 Nov 2003 14:24:42 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id OAA1769506 ; Mon, 10 Nov 2003 14:24:37 +0100 Date: Mon, 10 Nov 2003 14:24:35 +0100 (NFT) From: Diego Olivier Fernandez Pons To: johnh@ichips.intel.com cc: caml-list@inria.fr Subject: RE: [Caml-list] Efficient and canonical set representation? In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; pons:01 pons:01 etu:99 caml-list:01 hash:01 hypothesis:01 fernandez:01 fernandez:01 equality:01 polymorphic:01 polymorphic:01 olivier:02 olivier:02 canonical:03 types:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, > 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... 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. Diego Olivier ------------------- 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