Transitive closure from a list using Haskell -

i need produce transitive closure on list using haskell.

so far got this:

import data.list qq [] = [] qq [x] = [x] qq x = vv (sort x)  vv (x:xs) = [x] ++ (member [x] [xs]) ++  (qq xs)  member x [y] = [(x1, y2) | (x1, x2) <- x, (y1, y2) <- qq (y), x2 == y1] 

output 1:

*main> qq [(1,2),(2,3),(3,4)] [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)] 

output 2:

*main> qq [(1,2),(2,3),(3,1)] [(1,2),(1,3),(1,1),(2,3),(2,1),(3,1)] 

the problem second output. instead of checking additional transitive closure on new produced list, returns result.

to prototype haskell code used python code:

def transitive_closure(angel):     closure = set(angel)     while true:         new_relations = set((x,w) x,y in closure q,w in closure if q == y)         closure_until_now = closure | new_relations             if closure_until_now == closure:             break             closure = closure_until_now         return closure  print transitive_closure([(1,2),(2,3),(3,1)]) 

output:

set([(1, 2), (3, 2), (1, 3), (3, 3), (3, 1), (2, 1), (2, 3), (2, 2), (1, 1)]) 

this right output need in haskell function.

how same thing in haskell code? (i need recreate if statement python code haskell code)

i'm not entirely of you're trying in haskell code. instead, port python code haskell.

for sake of simplicity, let's stick lists instead of involving sets. if need performance, using sets isn't more difficult; however, can't use comprehensions sets in haskell without serious acrobatics¹. if don't mind slower code, use nub² same effect lists.

i start writing functions type signature; makes easier think i'm implementing. we're taking list of pairs , producing list of pairs. means type going roughly be:

[(a, b)] → [(a, b)] 

however, want able compare left , right part of pairs each other ==. means have same type , have support ==. actual type is:

transitiveclosure ∷ eq ⇒ [(a, a)] → [(a, a)] 

now let's @ actual algorithm. main part while true loop. want transform recursion. best way think recursion break base case , recursive case. loop, corresponds stopping condition , loop body.

so base case? in code, loop's exit condition hidden inside body. stop when closure_until_now == closure. (this if-statement mentioned in question, coincidentally.)

in function definition, can specify logic guards, first part of our recursive function looks this:

transitiveclosure closure    | closure == closureuntilnow = closure 

this acts if statement. of course, haven't defined closureuntilnow yet! let's next. helper variable, put in where block after function definition. can define using same comprehension in python code, nub ensure remains unique:

  closureuntilnow =            nub $ closure ++  [(a, c) | (a, b) ← closure, (b', c) ← closure, b == b'] 

this code equivalent of first 2 lines in while loop.

finally, need our recursive case. if not done yet? in while loop, set closure closureuntilnow , iterate again. we'll same thing recursive call:

  | otherwise = transitiveclosure closureuntilnow 

since part of pattern guard, goes above where block. so, putting together, get:

transitiveclosure ∷ eq ⇒ [(a, a)] → [(a, a)] transitiveclosure closure    | closure == closureuntilnow = closure   | otherwise                  = transitiveclosure closureuntilnow   closureuntilnow =            nub $ closure ++ [(a, c) | (a, b) ← closure, (b', c) ← closure, b == b'] 

hopefully makes thinking involved in writing program clear.

¹this difficult because set not form haskell monad. monad in more general sense, doesn't conform class in prelude. can't use monad comprehensions. could use monad comprehensions rebindable syntax there, it's not worth it.

²nub stupidly named function removes duplicates list. think ocaml's dedup much better name it.