sml - smlfoldl説明/トレース

Question

私はしばらくの間これを理解しようとしていますが、成功していません。[1,2,3]の入力引数の例をとって、次の関数（べき集合）はどのように詳細に進んでいますか？助けてくれてありがとう。

fun ps L = foldl（fn（x、tl）=> tl @ map（fn xs => x :: xs）tl）[[]] L;

Answer 1

関数を正しく使用するには、入力リストに重複がないと想定する必要があります。

関数は次のように理解できます。

• 空のセット（）のみで構成されるセットのセットであるアキュムレータから始め[[]]ます。
• 各ステップで、アキュムレータのすべてのセットを取得し、xそれらに現在の要素を追加して、これらの結果をアキュムレータに追加します。
• 最終的な結果は、すべての可能なn要素のセット、つまりべき集合です。

トレースを簡単に表現するために、補助関数を作成しましょう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 *)