Haskell函數如何使用列表理解工作計算排列？

Question

我讀西蒙·湯普森的的Haskell：函數式編程的工藝，我想知道是如何工作的：

perms [] = [[]] 
perms xs = [ x:ps | x <- xs , ps <- perms (xs\\[x]) ] 

我似乎無法把握perms(xs\\[x])應如何發揮作用。兩個元素的列表的跟蹤顯示：

perms [2,3] 
    [ x:ps | x <- [2,3] , ps <- perms ([2,3] \\ [x]) ]  exe.1 
    [ 2:ps | ps <- perms [3] ] ++ [ 3:ps | ps <- perms [2] ] exe.2 
    ... 

如何從exe.1去exe.2？

Answer 1

它基本上是說：

1. 採取任何x從列表xs（x <- xs）
2. 採取ps是列表xs\\[x]的置換（即xs與刪除x） - perms (xs\\[x])
3. 返回結果。

perms(xs\\[x])是遞歸調用，從xs刪除x。

Answer 2

那麼，它只是插入2和3分別到[2,3] \\ [x]。所以，你必須

[ 2:ps | ps <- perms ([2,3] \\ [2]) ] ++ [ 3:ps | ps <- perms ([2,3] \\ [3]) ] 

而且由於\\是差分算，即它返回其不在第二列表中的第一個列表的元素，結果分別爲[3]和[2]。