sml foldl解釋/跟蹤

Question

我試圖弄清楚一段時間，但我沒有成功。 下面的函數（powerset）如何進行詳細的說明，以[1,2,3]爲例輸入參數？ 非常感謝您的幫助。 （fn xs => x :: xs）tl）[[]] L;其中，

Answer 1

要正確使用此功能，您必須假定輸入列表中不存在重複。

• 我們先從一個累加器，其是一組的組僅包括空集（[[]]）的：

  該函數可以如下理解。

• 在每個步驟中，我們將累加器中的每個集合都添加到當前元素x中，並將這些結果添加到累加器中。
• 最終結果是一組所有可能的n元素，即powerset。

容易被明示的痕跡，讓我們創建一個輔助功能f

fun f (x, tl) = tl @ map (fn xs => x::xs) tl 

現在我們有了一絲[1, 2, 3]：

ps [1, 2, 3] 

~> foldl f [[]] [1, 2, 3] (* Step 1 *) 
~> foldl f (f (1, [[]])) [2, 3] 
~> foldl f ([[]] @ map (fn xs => 1::xs) [[]]) [2, 3] 

~> foldl f [[], [1]] [2, 3] (* Step 2 *) 
~> foldl f (f (2, [[], [1]])) [3] 
~> foldl f ([[], [1]] @ map (fn xs => 2::xs) [[], [1]]) [3] 

~> foldl f [[], [1], [2], [2, 1]] [3] (* Step 3 *) 
~> foldl f (f (3, [[], [1], [2], [2, 1]])) [] 
~> foldl f ([[], [1], [2], [2, 1]] @ map (fn xs => 3::xs) [[], [1], [2], [2, 1]]) [] 

~> foldl f [[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1]] [] (* Step 4 *) 

~> [[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1]] (* Final result *)