Using Set: Hypergraph type

Eray Ozkural (exa) erayo@cs.bilkent.edu.tr
Tue, 4 Sep 2001 12:43:44 +0300


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Greetings all!

I'm a new Haskell user. I've used Haskell for a number of small hacks and I 
can say that this is a brilliant language.

I was just working on a hypergraph implementation in haskell. A hypergraph, 
for those not familiar with it, is a family of sets which are subsets of a 
vertex set X. I went straight along the mathematical definition, and I 
decided to try the Edison library that came along with my ghc-5.00.2

Without further ado, here is the code:

type Hypergraph n = Set (Set n)

- -- hgraph constructor
- -- takes a list of edges
hgraph edge_list
    = unionManySets (map mkSet edge_list)

My trouble is that this does not seem to work well. Perhaps it's my lack of 
experience wih Edison, but the types do not seem to be right and the 
following expression fails to evaluate:

Hypergraph> elementOf (mkSet [1]) (hgraph [ [1,2], [1] ])

I expect "True" in response to this query. Anyway, I think this is not ghc 
specific. (I enabled -fglasgow-exts, no difference. I get a lot of type 
errors...)

What do you think is wrong with this code? It now seems to me that I may not 
be able to use Edison for my ADT, so how would you recommend me to go about 
coding this mathematical definition? All I need is to be able to define a set 
of sets in a convenient way; it also has to be halfway efficient. Should I 
implement this with lists, or is there an alternative set implementation 
which allows me to accomplish a decent hypergraph definition? [*]

Regards,

[*] I could also use a mix of arrays and lists it seems, similar to the edge 
list and pin list representations used in imperative code. But that does not 
give me the interface a set implementation would :)

- -- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara
www: http://www.cs.bilkent.edu.tr/~erayo
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE7lKJQfAeuFodNU5wRAtyBAJ0SCRLAV5u4IBkt3B2VIYB04l9LNACeNL0Y
GE9TPhrWoPY6rH58ZDSdweg=
=IdNC
-----END PGP SIGNATURE-----