使用Haskell从列表传递闭包 [英] Transitive closure from a list using Haskell
问题描述
到目前为止，我得到了这个：
import Data.List
qq [] = []
qq [x] = [x]
qq x = vv （排序x）
vv（x：xs）= [x] ++（成员[x] [xs]）++（qq xs）
成员x [ y] = [（x1，y2）| （x1，x2）< - x，（y1，y2）-qq（y），x2 == y1]
输出1：
* Main> qq [（1,2），（2,3），（3,4）]
[（1,2），（1,3），（1,4），（2,3），（ 2,4），（3,4）]
输出2：
*主要> qq [（1,2），（2,3），（3,1）]
[（1,2），（1,3），（1,1），（2,3），（ 2,1），（3,1）]
问题在于第二个输出。而不是在新生成的列表上检查额外的传递闭包，它只是返回结果。
要原型化haskell代码，我使用了 Python代码：
def transitive_closure（天使）：
closure = set（天使）
而真：
new_relations = set（（x，w）for x，y in closure for q，w in closure if q == y）
closure_until_now = closure | new_relations
如果closure_until_now ==闭合：
断点
封闭= closure_until_now
返回闭合
打印transitive_closure（[（1,2），（2， 3），（3,1）]）
输出： （1,2），（3,2），（1,3），（3,3），（（3），（3）， 3,1），（2,1），（2,3），（2,2），（1,1）]）
这是我在Haskell函数中需要的正确输出。
如何在我的Haskell代码中执行相同的操作？ （我需要重新创建 if Python代码中的语句添加到Haskell代码中）
我并不完全确定你想要在你的Haskell代码中做什么。相反，我们可以将你的Python代码移植到Haskell。
为简单起见，我们只需坚持列表而不是涉及集合。如果你确实需要表现，使用套装并不是那么困难;然而，如果没有一些严肃的杂技¹，我们不能在Haskell中使用集合的解释。如果我们不介意速度较慢的代码，我们可以使用 nub ²来获得与列表相同的效果。
我喜欢用类型签名开始写函数;它使我更容易思考我正在实施的内容。我们正在对配对列表进行编码，并生成另一对配对列表。这意味着类型将大致为：
[（a，b）]→[ （a，b）]
但是，我们希望能够比较左侧和右侧部分相互配对 == 。这意味着它们必须是相同类型，并且它们必须支持 == 。所以实际的类型是：
transitiveClosure∷等式⇒[（a，a）]→[（a，a）]
现在我们来看看您的实际算法。主要部分是，而True 循环。我们想要将其转换为递归。考虑递归的最好方法是将其分解为基本情况和递归情况。对于循环来说，这大致对应于停止条件和循环体。
那么基本情况是什么？在你的代码中，循环的退出条件隐藏在主体内部。当 closure_until_now == closure 时，我们停止。 （这是你在你的问题中提到的if语句，巧合的）。
在函数定义中，我们可以用 guards ，所以递归函数的第一部分看起来像这样：
transitiveClosure闭包
| closure == closureUntilNow = closure
这就像 if 语句。当然，我们还没有定义 closureUntilNow 呢！所以我们接下来做。这只是一个辅助变量，所以我们把它放在函数定义之后的其中块中。我们可以使用与Python代码相同的理解来定义它，使用 nub 来确保它保持唯一：
where closureUntilNow =
nub $ closure ++ [（a，c）| （a，b）←结束，（b'，c）←结束，b == b']
这段代码和while循环中的前两行是等价的。
最后，我们只需要递归的情况。如果我们没有完成，我们该怎么做？在您的 while 循环中，您只需将闭包设置为 closureUntilNow 并重新迭代。我们将通过递归调用完成同样的事情：
|否则= transitiveClosure closureUntilNow
由于这是模式守护的一部分，所以 em> 其中块。所以，把它们放在一起，我们得到：
transitiveClosure∷等式⇒[（a，a）]→[（a ，a）]
transitiveClosure闭包
| closure == closureUntilNow = closure
|否则= transitiveClosure closureUntilNow
where closureUntilNow =
nub $ closure ++ [（a，c）| （a，b）←结束，（b'，c）←结束，b == b']
<
¹这很困难，因为 Set 没有形成一个 Haskell Monad 。这是一个更普遍意义上的monad，但它不符合Prelude中的类。所以我们不能只使用monad理解。我们可以使用带有可重定义语法的monad comprehensions来达到目的，但它不值得。
² nub 是一个愚蠢命名的函数，用于从列表中删除重复项。我认为OCaml的 dedup 是一个更好的名字。
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)
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.
这篇关于使用Haskell从列表传递闭包的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
