haskell - 递归置换函数总是返回空列表

Question

我正在学习 Haskell，我的一个练习函数是一个简单的递归 permute .我改编了the solution described here最初得到了这个:

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]

但是，我仍然对 感到困惑。为什么原始版本总是返回一个空列表 .

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]

列表中只有一个元素，所以我们可以忽略 <-直接理解绑定(bind)和替换:

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被绑定(bind)到具有单个元素的东西上，我们再次可以直接替换:

permute [x] = (x:[])

这只是说 permute [x] = [x] .