递归排列函数总是返回空列表。

Question

我正在学习Haskell，我的一个练习函数是一个简单的递归permute。我改编了这里描述的解决方案，最初得到了以下结果：

selections [] = []
selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ]

permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys]

(是的，这段代码可以更短，但我追求的是明确和清晰。)

然而，这个版本的permute总是返回一个空列表！经过一番努力，我通过将permute更改为以下内容使其正常工作：

permute [] = [[]]
permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys]

然而，我仍然困惑于为什么原始版本总是返回一个空列表。

- JSBձոգչ

---

从你的程序中至少应该清楚地表明，permute的原始版本不能返回包含[]作为元素的列表，因为元素总是形如y:ps。 - Tsuyoshi Ito

Answer 1

嗯，显然这两个非常相似，那么为什么不详细看一下它们的不同之处呢？递归部分在两者中完全相同，所以我们首先可以说，这两个版本在非空列表上都做了 相同的事情。这听起来很奇怪，因为它们给出了不同的结果，但实际上是真的，因为它们 对递归调用的结果执行相同的操作。

正确版本的基本情况是permute [] = [[]]，这是不言自明的。然而，第一个版本的基本情况隐含在列表理解中。鉴于定义：

permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys]

我们可以用[]来代替xs，看看会发生什么：

permute [] = [y:ps | (y,ys) <- selections [], ps <- permute ys]

假设有定义 selections [] = []，我们可以简化为：

permute [] = [y:ps | (y,ys) <- [], ps <- permute ys]

从中可以明显看出没有生成任何结果，因此整个列表推导式是空的，简化后只剩：

permute [] = []

现在考虑基础情况之前的最后一个递归步骤，将 [x] 替换为参数:

permute [x] = [y:ps | (y,ys) <- selections [x], ps <- permute ys]

selections 的定义是 selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ]，将 [x] 代入得到 selections [x] = (x, []) : [ (y, x:ys) | (y,ys) <- selections [] ]。由于 selections [] 计算结果为 []，整个列表推导式也会被简化为 []，从而得到 selections [x] = [(x, [])] 或者等价的 selections [x] = (x, []) : []。

将其代入上面提到的 permute 函数中：

permute [x] = [y:ps | (y,ys) <- [(x, [])], ps <- permute ys]

列表中只有一个元素，因此我们可以忽略 <- 推导绑定并直接进行替换：

permute [x] = [y:ps | (y,ys) = (x, []), ps <- permute ys]

permute [x] = [ x:ps | ps <- permute []]

既然已经确定 permute [] 的结果是 []，我们也可以将其替换进去，然后再次发现列表推导式会简化为[]:

permute [x] = []

...它可以轻松地推广到对任何输入返回[]。然而，正在工作的版本使用以下定义：

permute [] = [[]]

在最终递归步骤的最终缩小中，这将更改替换为以下内容：

permute [x] = [ x:ps | ps <- permute []]

permute [x] = [ x:ps | ps <- [[]] ]

由于ps绑定到只含一个元素的内容，我们可以直接进行替换：

permute [x] = (x:[])

这就是在说permute [x] = [x]。

- C. A. McCann