haskell - Haskell 中的递归排列

Question

我正在尝试实现 Steinhaus-Johnson-Trotter algorithm用于生成排列。我的代码如下:

permutations :: [a] -> [[a]]
permutations [] = []
permutations (x:[]) = [[x]]
permutations xs = [ys ++ [xs !! i] | i <- [len,len-1..0], ys <- permutations (delete i xs)]
  where len = (length xs)
        delete i xs = take i xs ++ drop (succ i) xs

这是对 Python code 的直接翻译:

def perms(A):
    if len(A)==1:
        yield A
    for i in xrange(len(A)-1,-1,-1):
        for B in perms(A[:i]+A[i+1:]):
            yield B+A[i:i+1]

Python 代码可以工作，但 Haskell 代码进入无限递归。 permutations (delete i xs) 列表理解内应该使流程更接近基本情况。为什么会出现无限递归？

编辑: @augustss说:

Always beware when you have multiple base cases for a function over lists.

所以我改变了基本情况

permutations [] = []
permutations (x:[]) = [[x]]

更简单

permutations [] = [[]]

Answer 1

你的循环不一样。

i <- [len,len-1..0]

对比

for i in xrange(len(A)-1,-1,-1):

第一种情况，您将 i 绑定(bind)到长度，而不是长度减一。结果是 delete i xs 返回 xs，所以你得到了无限递归。

我还有一些旁注。

首先 !! 是线性时间。您最好编写一个辅助函数，将 !!、delete 和对输入的迭代组合到一个列表遍历中。类似于 select::[a] -> [(a, [a])]。您可以高效地做到这一点。

其次，++也是线性时间。使用它将单个元素附加到现有列表很慢。如果您的目标只是产生所有排列，而不是它们的特定顺序，您可能应该使用 (xs !! i) : ys 作为要返回的表达式。 (针对响应第一点所做的任何更改进行适当修改。)