哈斯克爾 - 幫助理解函數

Question

我有我無法理解這個謎底功能：

mystery :: [a] -> [[a]] 
mystery [] = [[]] 
mystery (x:xs) = sets ++ (map (x:) sets) 
       where sets = mystery xs 

這裏有一些輸入，結果：

mystery [1,2] returns [[],[2],[1],[1,2]] 
mystery [1,2,3] returns [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]] 

通過看結果，我可以看到它計算列表中所有可能的數字組合，但不是所有可能的permuations ...我想。

我遇到的麻煩實際上是通過遞歸和理解函數如何獲得這些結果。

我想我得到了它的開始 - >映射（1 :)到[2]上，產生[1,2]，但是在這一點上，我很困惑遞歸如何工作，以及我是否仍然映射（1 :)或現在（2 :)，然後到什麼。

如果任何人都可以通過逐步解釋（使用提供的示例之一）來幫助我解決這個函數如何工作（使用地圖並設置遞歸），這將不勝感激！

謝謝！

Answer 1

您的神祕功能是計算其輸入的power set。

Answer 2

Haskell將執行所謂的懶惰評估，這意味着它只會處理事情，因爲它需要從左到右（通常）。所以，把你的mystery [1, 2]例如，哈斯克爾將執行以下操作：

sets ++ (map (x:) sets) 

計算結果爲：

mystery (2:[]) ++ (map (1:) sets) 

在這一點上，我們稱之爲mystery (2:[])

mystery ([]) ++ (map (2:) sets) ++ (map (1:) sets) 

mystery ([])將返回空列表清單

[[]] ++ (map (2:) sets) ++ (map (1:) sets) 
[[]] ++ (map (2:) mystery []) ++ (map (1:) sets) 

所以現在哈斯克爾將嘗試應用功能(2:)含一個空列表

[[]] ++ (2:[[]]) ++ (map (1:) sets) 
[[]] ++ [[2]] ++ (map (1:) sets) 
[[], [2]] ++ (map (1:) sets) 

這就是事情變得有點更加混亂名單上。

[[], [2]] ++ (map (1:) mystery (2:[])) 

這最後sets將評估mystery (2:[])

[[], [2]] ++ (map (1:) (sets ++ (map (2:) sets))) 
[[], [2]] ++ (map (1:) (mystery [] ++ (map (2:) sets)) 
[[], [2]] ++ (map (1:) ([[]] ++ (map (2:) mystery [])) 
[[], [2]] ++ (map (1:) ([[]] ++ (2:[[]])) 
[[], [2]] ++ (map (1:) ([[]] ++ [[2]]) 

現在(1:)將被應用到其中包含一個空列表列表，包含2列表：

[[], [2]] ++ (map (1:) ++ [[], [2]]) 
[[], [2]] ++ [[1], [1, 2]] 
[[], [2], [1], [1, 2]] 

實手術的肉在最後兩節中。 Haskell創建一個列表，如[[], [2]]，然後在每個列表的頭部添加一個表格以形成[[1], [1, 2]]。