[Camllist] Efficient and canonical set representation?

Harrison, John R
 Brian Hurt
 Eray Ozkural
 Eray Ozkural
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20031107 (03:52) 
From:  Eray Ozkural <exa@k...> 
Subject:  Re: [Camllist] Efficient and canonical set representation? 
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. Logtime lookup and insertion, and lineartime 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 camllistrequest@inria.fr Archives: > http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: > http://caml.inria.fr/FAQ/ Beginner's list: > http://groups.yahoo.com/group/ocaml_beginners  Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr> 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 camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners