遞歸排列函數總是返回空列表

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