Re: [Caml-list] Efficient and canonical set representation?

[Eray Ozkural <exa@kablonet.com.tr>]

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) <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 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