Geek Answers Handbook

Transitional closure from a list using Haskell

I need to create a transitive list closure 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 the second exit. Instead of checking for additional transitive closure in the newly released list, it simply returns the result.

For the haskell code prototype, 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 the correct conclusion that I need in my Haskell function.

How to do the same in my Haskell code? (I need to recreate the instruction iffrom Python code to Haskell code)

+4
source share
2 answers

, Haskell. Python Haskell.

, . , ; Haskell - . , nub ², .

; , . . , :

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

==. , , ==. , :

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

. - while True. . - . .

, ? . , closure_until_now == closure. ( if , .)

, , , :

transitiveClosure closure 
  | closure == closureUntilNow = closure

, if. , closureUntilNow! . , where. , Python, nub, :

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

while.

, . , ? while closure closureUntilNow . :

  | otherwise = transitiveClosure closureUntilNow

, where. , , :

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']

, , .

¹ , Set Haskell Monad. , . . monad- , , .

² nub - , . , OCaml dedup .

+7

, , python ( ) 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

, , Haskell.

closure = set(angel) = > closure = nub angel. nub - set.

while True: = > ! Haskell "while", - .

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


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

. , , "", .

if closure_until_now == closure:
    break


| closure_until_now == closure = closure

, . , , . python : " , " return close". Haskell , , .

closure = closure_until_now 


| otherwise                    = transitive_closure closure_until_now

, . "" , closure_until_now. , Haskell "" (.. ) closure_until_now.

Data.Set. set , . map s, set:

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

, , " ", . - Maybe.

+1

More articles:


All Articles