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

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] 

没有在列表中只有一个元素的，所以我们可以忽略<-理解结合和替代直接：

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