递归置换函数始终返回空列表

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]

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

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