使用Haskell从列表中获取传递闭包

Question

我需要使用Haskell在列表上生成传递闭包。

目前为止，我已经得到了这个：

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]

输出1：

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

输出 2：

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

问题出在第二个输出上。它没有检查新产生的列表中是否存在其他的可传递闭包，只是返回了结果。

为了原型化Haskell代码，我使用了这段Python代码:

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

输出：

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

这是我在Haskell函数中需要的正确输出。

如何在我的Haskell代码中实现相同的功能？（我需要将Python代码中的if语句重新创建到Haskell代码中）

- Alex

---

为什么在Python中使用描述性名称而在Haskell中使用神秘的缩写？类型签名也是一个好主意，无论多么琐碎。 - leftaroundabout

@leftaroundabout，我知道这是不好的做法，但在我弄清楚之后，我会更改变量/函数名称和类型签名。希望这段代码不难阅读。 - Alex

Answer 1

我不太确定您在Haskell代码中想要做什么。相反，我们可以将您的Python代码移植到Haskell中。

为了简单起见，让我们只使用列表而不涉及集合。如果您真的需要性能，则使用集合并不困难；但是，在Haskell中，如果没有一些严格的技巧，我们无法使用集合推导式。如果我们不介意较慢的代码，我们可以使用nub来使用列表获得相同的效果。

我喜欢从类型签名开始编写函数；这使得我更容易思考我正在实现什么。我们正在接受一对列表并生成另一对列表。这意味着类型将大致为：

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

然而，我们希望能够使用==比较成对的左右部分。这意味着它们必须是相同的类型，并且支持==操作。因此，实际类型为：

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

现在让我们来看看你实际的算法。主要部分是while True循环。我们想将其转换为递归。思考递归的最佳方法是将其分解为基本情况和递归情况。对于循环，这大致对应于停止条件和循环体。

那么什么是基本情况呢？在你的代码中，循环的退出条件隐藏在循环体内。当 closure_until_now == closure时，我们会停止循环。(巧合的是，这是你在问题中提到的if语句。)

在函数定义中，我们可以使用guards指定这样的逻辑，因此我们递归函数的第一部分如下所示：

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，但它不符合Prelude中的类。所以我们不能只使用monad comprehensions。我们可以使用可重新绑定语法的monad comprehensions来实现，但这并不值得。

² nub是一个愚蠢的命名函数，它可以从列表中删除重复项。我认为OCaml的dedup是一个更好的名称。

- Tikhon Jelvis

Answer 2

我不知道你的Haskell代码应该做什么，所以我直接将你的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

让我们一起学习Python并分析哪一行对应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

我假设你已经熟悉了guards。如果没有，之前有很多人做得比我更好地解释了。Python代码的语义是“如果条件为真，则退出循环并转到'return closure'”。由于Haskell中没有循环，当你遇到退出条件时，只需返回一个值而不是递归。

closure = closure_until_now 

变成

| otherwise                    = transitive_closure closure_until_now

如果您通过了退出条件，Python 将继续执行循环。下一次循环迭代将使用“closure”作为其输入，我们将其设置为closure_until_now。因此，在 Haskell 版本中，“loop”的下一个“iteration”（即递归函数）将以closure_until_now作为输入。

为了更加健壮，您应该使用Data.Set。唯一的问题是您不能与Set一起使用列表推导式。但是，您可以轻松地用存在于Set中的map替换列表推导式：

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

这有点像一个hack，我只是使用列表来“返回空值”，如果条件不为真。在这种情况下，最好使用类似于 Maybe 的东西。

- user2407038