set - Transitive closure of a graph in Haskell -

the following program has purpose transitive closure of relation (as set of ordered pairs - graph) , test membership of ordered pair relation.

i tried make program efficient through use of data.set instead of lists , eliminating redundancies in generation of missing pair.

i know:

1. how use quickcheck verify correctness;
2. how calculate efficiency of program, if possible, or how compare similar solutions of problem (ex. transitive closure list ).

any criticism , suggestion appreciated.

import data.set s import data.foldable f (foldmap)  data truthvalue = f | u | t deriving (show,eq)  ismemberoftransitivegraph :: ord t => (t, t) -> set (t, t) -> truthvalue (x,y) `ismemberoftransitivegraph` gr   | s.member (x,y) closure = t -- suggested user5402   | s.member (y,x) closure = f -- suggested user5402   | otherwise = u     closure = transitiveclusureofgraph gr -- suggested user5402  transitiveclusureofgraph :: ord => set (a, a) -> set (a, a) transitiveclusureofgraph gr = f.foldmap (transitiveclosureofargument gr) domain     domain = s.map fst gr  transitiveclosureofargument :: ord => set (a, a) -> -> set (a, a) transitiveclosureofargument gr x = s.map ((,) x) $ recursiveimages gr (s.singleton x)  recursiveimages :: ord => set (a, a) -> set -> set recursiveimages gr imgs = f gr imgs s.empty     f :: ord => set (a, a) -> set -> set -> set   f gr imgs acc     | s.null imgs = acc     | otherwise = f gr (newimgs s.\\ acc) (s.union newimgs acc)         newimgs = f.foldmap (imaginsof gr) imgs  imaginsof :: (ord b, eq a) => set (a, b) -> -> set b imaginsof gr arg =  s.foldr (\(a,b) acc -> if == arg s.insert b acc else acc) s.empty gr 

**

example 1

**

somelessthan = s.fromlist [("1","2"),("1","4"),("3","4"),("2","8"),("3","5"),("4","7"),("4","8"),("3","9")]  > transitiveclusureofgraph somelessthan > fromlist [("1","2"),("1","4"),("1","7"),("1","8"),("2","8"),("3","4"),("3","5"),("3","7"),("3","8"),("3","9"),("4","7"),("4","8")]  `islessthan` b = (a,b) `ismemberoftransitivegraph`  somelessthan > "1" `islessthan` "8" > t > "8" `islessthan` "1" > f > "1" `islessthan` "9" > u > "9" `islessthan` "1" > u 

**

example 2

**

sometallerthan = s.fromlist  [("alexandre","andrea"),("andrea","john"),("george","frank"),("george","lucy"),("john","liza"),("julia","lucy"),("liza","bob"),("liza","frank")]  > transitiveclusureofgraph sometallerthan > fromlist [("alexandre","andrea"),("alexandre","bob"),("alexandre","frank"),("alexandre","john"),("alexandre","liza"),("andrea","bob"),("andrea","frank"),("andrea","john"),("andrea","liza"),("george","frank"),("george","lucy"),("john","bob"),("john","frank"),("john","liza"),("julia","lucy"),("liza","bob"),("liza","frank")]  `istallerthan` b = (a,b) `ismemberoftransitivegraph` sometallerthan > "alexandre" `istallerthan` "frank" > t > "frank" `istallerthan` "alexandre" > f > "alexandre" `istallerthan` "george" > u > "george" `istallerthan` "alexandre" > u 

**

example 3

**

incomeislessorequalthan = s.fromlist [("bob","liza"),("liza","tom"),("tom","bob"),("tom","mary"),   ("tom","tom")]  > s.filter (\(a,b) -> /= b) $ transitiveclusureofgraph incomeislessorequalthan  > fromlist [("bob","liza"),("bob","mary"),("bob","tom"),("liza","bob"),("liza","mary"),("liza","tom"),("tom","bob"),("tom","liza"),("tom","mary")] 

some comments:

1. some ideas quickcheck tests:

   • create random connected graph , verify every pair of points in transitive closure.
   • verify random graph transitive closure of transitive closure same doing transitive closure once.
   • verify code returns same answer implementation (such fgl library.)

however, when @ fgl library see use fixed graph test path query functions. know answers should tests.

another idea solve acm (programming competition) problem involves finding transitive closure of graph, , use code in solution. both timus , codeforces accept haskell programs.

2. in ismemberoftransitivegraph have common sub-expression transitiveclusureofgraph gr. ghc (and should) detect , factor out doesn't evaluated twice, doesn't that. moreover, being interpreter, ghci won't perform common sub-expression elimination. so, given transitiveclusureofgraph expensive operation, should write function like

this:

ismemberoftransitivegraph (x,y) gr   | s.member (x,y) closure = t   | s.member (y,x) closure = f   | otherwise              = u       closure = transitiveclusureofgraph gr in 

3. also, computing transitive closure entire graph expensive way determine if specific pair in closure. better way implement ismemberoftransitiveclosure perform depth-first search start @ 1 member of pair until a) either find other element or b) fill out connected component without finding other element. otherwise performing lot of work on other connected components irrelevant question trying answer.

4. if concerned efficiency, restrict node type int , use data.intset or data.bitset sets of nodes.