使用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代码中做同样的事情？(我需要重新创建if从Python代码到Haskell代码的语句)

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理解.我们可以使用具有可重新绑定语法的monad理解来实现,但它不值得.

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