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 EAA15123; Fri, 7 Nov 2003 04:52:15 +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 EAA15283 for ; Fri, 7 Nov 2003 04:52:14 +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 hA73qC119493 for ; Fri, 7 Nov 2003 04:52:12 +0100 (MET) Received: (qmail 26019 invoked by uid 0); 7 Nov 2003 03:57:19 -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:57:19 -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:52:05 +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: <200311070552.05862.exa@kablonet.com.tr> X-Loop: caml-list@inria.fr X-Spam: no; 0.00; eray:01 ozkural:01 caml-list:01 haskell:01 vertices:01 iterative:01 pins:99 abstraction:01 haskell:01 bug:01 faq:01 faq:01 beginner's:01 beginners:01 eray:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hello John, I forgot to mention: this is exactly the same question that I asked aeons ago for representing hypergraphs on haskell list. (For those who didn't remember: a hypergraph is basically a collection of sets whose elements are drawn from a finite set X, it is the generalization of a graph in which each edge connects multiple vertices rather than 2) Of course there is a way to represent hypergraphs efficiently, but it's not a functional way. In the optimal and general purpose iterative method, you use the equivalent of adjacency list representation extended to hypergraphs: basically an array of pins (for each net) and an array of nets (for each pin). Since you are asking this question, you probably already know this. I am pretty sure a good ocaml implementation doesn't exist, but the idea is the same as in C and you can code it ;) If speed isn't a paramount concern over abstraction at the present you can hack the Hypergraph module that uses edison which I had posted to haskell list. If you can't find it or can't get it to work, let me know and structure monster will try to help :) Regards, 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). > > 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 -- 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