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 *)