Transitive closure from a list using Haskell

Question

I need to produce transitive closure on list using Haskell.

So far I 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 is with second output. Instead of checking for additional transitive closure on the new produced list, it just returns result.

To prototype haskell code I used this Python code:

def transitive_closure(angel):
    closure = set(angel)
    while True:
        new_relations = set((x,w) for x,y in closure for 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 is right output that I need in my Haskell function.

How to do the same thing in my Haskell code? (I need to recreate if statement from Python code to the Haskell code)

Answer 1

I'm not entirely certain of what you're trying to do in your Haskell code. Instead, we could just port your Python code to Haskell.

For the sake of simplicity, let's just stick to lists instead of involving sets. If you really need performance, using sets isn't that much more difficult; however, we can't use comprehensions for sets in Haskell without some serious acrobatics¹. If we don't mind slower code, we could just use nub² to get the same effect with lists.

I like to start writing functions with the type signature; it makes it easier to think about exactly what I'm implementing. We're taking a list of pairs and producing another list of pairs. This means the type is going to roughly be:

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

However, we want to be able to compare the left and right part of the pairs to each other with ==. This means they have to be the same type and they have to support ==. So the actual type is:

transitiveClosure ∷ Eq a ⇒ [(a, a)] → [(a, a)]

Now let's look at your actual algorithm. The main part is the while True loop. We want to transform this to recursion. The best way to think about recursion is to break it up into the base case and the recursive case. For a loop, this corresponds roughly to the stopping condition and the loop body.

So what is the base case? In your code, the loop's exit condition is hidden inside the body. We stop when closure_until_now == closure. (This is the if-statement you mentioned in your question, coincidentally.)

In a function definition, we can specify logic like this with guards, so the first part of our recursive function looks like this:

transitiveClosure closure 
  | closure == closureUntilNow = closure

This acts just like your if statement. Of course, we haven't defined closureUntilNow yet! So let's do that next. This is just a helper variable, so we put it in a where block after the function definition. We can define it using the same comprehension as in your Python code, with nub to ensure it remains unique:

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

This code does the equivalent of the first two lines in your while loop.

Finally, we just need our recursive case. What do we do if we are not done yet? In your while loop, you just set closure to closureUntilNow and iterate again. We'll do exactly the same thing with a recursive call:

  | otherwise = transitiveClosure closureUntilNow

Since this is part of the pattern guard, it goes above the where block. So, putting it all together, we get:

transitiveClosure ∷ Eq a ⇒ [(a, a)] → [(a, a)]
transitiveClosure closure 
  | closure == closureUntilNow = closure
  | otherwise                  = transitiveClosure closureUntilNow
  where closureUntilNow = 
          nub $ closure ++ [(a, c) | (a, b) ← closure, (b', c) ← closure, b == b']

Hopefully this makes the thinking involved in writing this program clear.

¹This is difficult because Set does not form a Haskell Monad. It is a monad in a more general sense, but it doesn't conform to the class in the Prelude. So we can't just use monad comprehensions. We could use monad comprehensions with rebindable syntax to get there, but it's just not worth it.

²nub is a stupidly named function that removes duplicates from a list. I think OCaml's dedup is a much better name for it.

Answer 2

I haven't any clue what your haskell code should do, so I translated your python code verbatim (as closely as is possible) to haskell.

import Data.List
transitive_closure angel 
    | closure_until_now == closure = closure
    | otherwise                    = transitive_closure closure_until_now

        where new_relations = nub [(x,w) | (x,y) <- closure, (q,w) <- closure, q == y] 
              closure = nub angel
              closure_until_now = closure `union` new_relations

Let's go through the python and analyze what line corresponds to what in the Haskell.

closure = set(angel) => closure = nub angel. nub is just set.

while True: => Nothing! There are no 'while' loops in Haskell so recursion is your only choice.

new_relations = set((x,w) for x,y in closure for q,w in closure if q == y)
closure_until_now = closure | new_relations

becomes

new_relations = nub [(x,w) | (x,y) <- closure, (q,w) <- closure, q == y]
closure_until_now = closure `union` new_relations

Essentially the same thing. Not that the order of the declarations doesn't matter, since they aren't 'executed' like in an imperative language.

if closure_until_now == closure:
    break

becomes

| closure_until_now == closure = closure

I'll assume you are familiar with guards. If not, many before me have done a much better job explaining. The semantics of the python code says "if this condition is true, we exit the loop and go to 'return closure'". Since there is no loop in the Haskell, when you encounter the exit condition, you simply return a value instead of recursing.

closure = closure_until_now 

becomes

| otherwise                    = transitive_closure closure_until_now

If you pass the exit condition, the python will continue with the loop. The next iteration of the loop will use 'closure' as its input, which we set to be closure_until_now . So, in the Haskell version, the next 'iteration' of the 'loop' (ie the recursive function) will take closure_until_now as input.

For more robustness, you should use Data.Set. The only issue with Set is you cannot use list comprehension with it. However, you can trivially replace the list comprehension with maps, which exist for Set:

for = flip map
new_relations = nub $ concat $ concat $ 
                for closure (\(x,y) -> 
                    for closure (\(q,w) -> 
                                 if q == y then [(x,w)] else []
                                 )
                             )

It is a bit of a hack, I just use lists in order to "return nothing" if the condition is not true. It would probably be better to use something like Maybe in this case.