-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Tuesday 04 September 2001 12:43 pm, Eray Ozkural (exa) wrote:

type Hypergraph n = Set (Set n)

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

Well. Obviously my constructor is failing here :) It should be hgraph edge_list     = mkSet (map mkSet edge_list) However, I still can't get it to work! Hypergraph> :type hgraph [ [1,2], [1] ] forall a. (Num a, Ord (Set a), Ord a) => Set (Set a) Hypergraph> elementOf (mkSet [1]) (hgraph [ [1,2], [1] ]) [type errors] .... Hypergraph> :type (mkSet [1]) forall a. (Num a, Ord a) => Set a Any help would be greatly appreciated. Regards, - -- Eray Ozkural (exa) 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 iD8DBQE7lKVDfAeuFodNU5wRAtslAJ9Hc9gIo/f+u0HWT8YlJxSOhlg2cgCeKQaj nj0LOmWB6PyI4m/f6adVMeM= =A7m7 -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi Dan, Thanks for your help. On Tuesday 04 September 2001 05:27 pm, Daan Leijen wrote:

Unfortunately, you don't show the type error that was returned.

It was a bit long. Anyway, here it is: Hypergraph> elementOf (mkSet [1]) (hgraph [ [1,2], [1] ]) <no file>:0: No instance for `Ord (Set a)' arising from use of `hgraph' at <no file>:0 In the second argument of `elementOf', namely `(hgraph [[1, 2], [1]])' in the definition of function `it': elementOf (mkSet [1]) (hgraph [[1, 2], [1]]) <no file>:0: Ambiguous type variable(s) `a' in the constraint `Ord a' arising from use of `hgraph' at <no file>:0 In the second argument of `elementOf', namely `(hgraph [[1, 2], [1]])' in the definition of function `it': elementOf (mkSet [1]) (hgraph [[1, 2], [1]]) <no file>:0: Ambiguous type variable(s) `a' in the constraint `Num a' arising from the literal `1' at <no file>:0 In the list element: 1 In the list element: [1] Okay, I guess I got it now. The (types of) elements of a Set ought to be instances of Ord. So I presume Edison supports only flat sets. So, this is not really a mathematical set, whichever set theory you take to be correct :) I guess a roughly working and more-efficient-than-list set type would be very useful for mathematicians and computer scientists. And writing one turns out to be extremely difficult, which set theory should one take? :) I particularly like the hyperset formulation, but then implementing hypergraphs might be a little circular. :))

However, I think that Hugs/GHCi is unable to figure out which numeric (Num a) instance you are using (Int,Integer, Double??). You can help the interpreter a little bit by

providing a type annotation:

...

elementOf (mkSet [(1::Int)]) (hgraph [ [1,2], [1] ])

or a constant with a type signature

...

list1 :: [Int] list1 = [1]

test = elementOf (mkSet list1) (hgraph [ [1,2], [1] ])

Hypergraph> elementOf (mkSet [(1::Int)]) (hgraph [ [1,2], [1] ]) <no file>:0: No instance for `Ord (Set Int)' arising from use of `hgraph' at <no file>:0 In the second argument of `elementOf', namely `(hgraph [[1, 2], [1]])' in the definition of function `it': elementOf (mkSet [(1 :: Int)]) (hgraph [[1, 2], [1]]) This does reduce the errors, but I guess this is just something that Edison is not up to (yet). I'm afraid I'll have to mimic the common imperative hypergraph representation, which means some more work for me :) Thanks, - -- Eray Ozkural (exa) 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 iD8DBQE7lQ9ZfAeuFodNU5wRAhuXAJ9WmGqXODtZO6oWSECAdD8ucwtwwACeJm6/ RKMKLPFWQDfKEhYHHN0f7TU= =jwu8 -----END PGP SIGNATURE-----

"Eray Ozkural (exa)" wrote:

Okay, I guess I got it now. The (types of) elements of a Set ought to be instances of Ord.

Yes, that's right. It's fairly easy to provide the required instances: module Hypergraph where import Set type Hypergraph a = Set (Set a) instance Ord a => Ord (Set a) where compare x y = compare (setToList x) (setToList y) hgraph :: Ord a => [[a]] -> Hypergraph a hgraph = mkSet . map mkSet Now it works as expected: $ ghci -package data ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 5.00.2, For Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package std ... linking ... done. Loading package lang ... linking ... done. Loading package concurrent ... linking ... done. Loading package posix ... linking ... done. Loading package util ... linking ... done. Loading package data ... linking ... done. Prelude> :load Hypergraph Compiling Hypergraph ( Hypergraph.hs, interpreted ) Ok, modules loaded: Hypergraph. Hypergraph> elementOf (mkSet [1]) (hgraph [ [1,2], [1] ]) True Cheers, Tom P.S. Nice to see a fellow K5'er on the Haskell lists. (I go my "tmoertel" on K5.)

"Eray Ozkural (exa)" wrote:

Thanks for the suggestion, but isn't this a bit inefficient?

No, it's *quite* inefficient. ;-) If you want something faster, you can use standard techniques like tacking a unique ID onto each distinct set element and performing more expensive comparisons only when IDs match. Consider it a manual compare-by-reference implementation. For example, here's a quick variation on the code I used earlier. This version uses an [(ID, elem)] representation for sets (type UidSet) underneath the Hypergraph representation. Usage is straightforward: You convert a list of edge lists into the new representation HypergraphRep, perform set operations as usual, and when you want to inspect a result, call hgraphUnRep to convert the representation to the normal Set-of-Sets form. I'm not sure if this is appropriate for your application, but it ought to give you a few ideas about what is possible without only minor tinkering. The disadvantage of this representation is that you must thread a unique-ID through set creation. You could use an unsafe variant if you wanted to eliminate the manual threading. ==== begin ==== module Hypergraph where import Set type Hypergraph a = Set (Set a) type UidSet a = Set (Int, a) type HypergraphRep a = UidSet (UidSet a) instance Ord a => Ord (Set a) where x <= y = (setToList x) <= (setToList y) compare x y = compare (setToList x) (setToList y) instance Show a => Show (Set a) where showsPrec p x = showsPrec p (setToList x) hgraph :: Ord a => [[a]] -> Hypergraph a hgraph = mkSet . map mkSet mkUidSet :: Ord a => Int -> [a] -> (Int, UidSet a) mkUidSet uid xs = (uid + length xs, mkSet (zip [uid..] xs)) hgraphR :: Ord a => Int -> [[a]] -> (Int, HypergraphRep a) hgraphR uid = hgraphR' (uid, []) hgraphR' :: Ord a => (Int, [UidSet a]) -> [[a]] -> (Int, HypergraphRep a) hgraphR' (uid, zs) [] = mkUidSet uid zs hgraphR' (uid, zs) (x:xs) = hgraphR' (uid', z:zs) xs where (uid', z) = mkUidSet uid x hgraphUnRep :: Ord a => HypergraphRep a -> Hypergraph a hgraphUnRep = mapSet (mapSet snd . snd) -- compare the two methods -- first, the normal representation bigHSet = hgraph [ [1..x] | x <- [1..1000] ] lilHSet = hgraph [ [0..x] | x <- [1..10] ] -- second, the new UidSet representation uid = 0 (uid', bigHSetR) = hgraphR uid [ [1..x] | x <- [1..1000] ] (uid'',lilHSetR) = hgraphR uid' [ [0..x] | x <- [1..10] ] ==== end ==== As a quick (and contrived) performance comparison, I computed the interection of two "disjoint" Hypergraphs. The first timing uses the normal representation, and the second the new variant. $ ghci -package data ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 5.00.2. [...] / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package std ... linking ... done. Loading package lang ... linking ... done. Loading package concurrent ... linking ... done. Loading package posix ... linking ... done. Loading package util ... linking ... done. Loading package data ... linking ... done. Prelude> :load Hypergraph Compiling Hypergraph ( Hypergraph.hs, interpreted ) Ok, modules loaded: Hypergraph. Hypergraph> :set +s Hypergraph> bigHSet `intersect` lilHSet [] (39.84 secs, 1058269360 bytes) Hypergraph> hgraphUnRep $ bigHSetR `intersect` lilHSetR [] (1.82 secs, 28345104 bytes) Cheers, Tom