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 SAA27282; Thu, 6 Nov 2003 18:03:25 +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 SAA27021 for ; Thu, 6 Nov 2003 18:03:24 +0100 (MET) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hA6H3N128897 for ; Thu, 6 Nov 2003 18:03:23 +0100 (MET) Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id hA6H3FC24964; Thu, 6 Nov 2003 11:03:16 -0600 (CST) Date: Thu, 6 Nov 2003 11:04:11 -0600 (CST) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: "Harrison, John R" cc: caml-list@inria.fr Subject: Re: [Caml-list] Efficient and canonical set representation? In-Reply-To: <3C4C3612EC443546A33E57003DB4F0F914C26B@orsmsx409.jf.intel.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 hash:01 hash:01 ocaml:01 ocaml:01 caml:01 equality:01 exists:01 nov:01 polymorphic:01 trivial:01 match:02 tree:02 precisely:02 comparison:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thu, 6 Nov 2003, Harrison, John R wrote: > 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. Two is the tricky one to implement. Imagine a case where I have set A with it's elements, and set B with all the elements less one of set A, but inserted in a different order. B is a different object than A (the two sets are not equal). Now you add that one last element from A, you want the insert routine to return A. This means that the insert routine has to know that A exists, and has to compare the new B to A to determine that it should return A and not B. It can be done but it's not trivial. Games with structure definitions don't help, because Ocaml will happily allocate different structures with the same data (this is why 1. == 1. is false). With a balanced tree structure you can implement the naive equality comparison in linear time (the sequence i/2^i converges, allowing you enumerate the elements in linear time). If you need faster (average) compares, there are a number of short cuts you can do. For example, you can keep the number of elements currently in the set handy, and if the number of elements don't match, obviously the sets won't be equal. Fancier, you can also keep a hash of all elements in the set- the hashs aren't equal, you can gaurentee the sets aren't equal. Be carefull with defining your hash function so the order elements were added isn't important. Brian ------------------- 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