嗯,显然这两个非常相似,那么为什么不详细看一下它们的不同之处呢?递归部分在两者中完全相同,所以我们首先可以说,这两个版本在非空列表上都做了 相同的事情。这听起来很奇怪,因为它们给出了不同的结果,但实际上是真的,因为它们 对递归调用的结果执行相同的操作。
正确版本的基本情况是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]
。
permute
的原始版本不能返回包含[]
作为元素的列表,因为元素总是形如y:ps
。 - Tsuyoshi Ito