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 EAA14701; Fri, 7 Nov 2003 04:43:17 +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 EAA14475 for ; Fri, 7 Nov 2003 04:43:15 +0100 (MET) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from eposta.kablonet.com.tr ([62.248.102.66]) by concorde.inria.fr (8.11.1/8.11.1) with SMTP id hA73hE118434 for ; Fri, 7 Nov 2003 04:43:14 +0100 (MET) Received: (qmail 24650 invoked by uid 0); 7 Nov 2003 03:48:21 -0000 Received: from unknown (HELO 195.174.173.82) (exa@kablonet.com.tr@195.174.173.82) by 0 with SMTP; 7 Nov 2003 03:48:21 -0000 From: Eray Ozkural Reply-To: erayo@cs.bilkent.edu.tr Organization: Bilkent University CS Dept. To: "Harrison, John R" , Subject: Re: [Caml-list] Efficient and canonical set representation? Date: Fri, 7 Nov 2003 05:43:07 +0200 User-Agent: KMail/1.5.93 References: <3C4C3612EC443546A33E57003DB4F0F914C26B@orsmsx409.jf.intel.com> In-Reply-To: <3C4C3612EC443546A33E57003DB4F0F914C26B@orsmsx409.jf.intel.com> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200311070543.07791.exa@kablonet.com.tr> X-Loop: caml-list@inria.fr X-Spam: no; 0.00; eray:01 ozkural:01 caml-list:01 amortized:01 hash:01 eray:01 ozkural:01 erayo:01 bilkent:01 bilkent:01 ankara:01 kde:01 kde:01 erayo:01 malfunction:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thursday 06 November 2003 18:41, 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. > > 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). It will be pretty hard to get 2. Not unless you are using disjoint sets :) You basically want O(1) for set equality, I suppose. Now, I think you wish to insert a new set in amortized O(lgn) time like in a disjoint set implementation. You can still use edison, isn't it good enough for you? I'm saying this, because I don't think there is a straightforward functional way. I have on my mind 2-universal hash functions, but here I am facing bugs of my own. I'm not in the structure monster mode right now it seems :) Cheers, -- Eray Ozkural (exa) Comp. Sci. Dept., Bilkent University, Ankara KDE Project: http://www.kde.org www: http://www.cs.bilkent.edu.tr/~erayo Malfunction: http://mp3.com/ariza GPG public key fingerprint: 360C 852F 88B0 A745 F31B EA0F 7C07 AE16 874D 539C ------------------- 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