sml foldl описание/след

Question

Я пытаюсь понять это в течение некоторого времени, но я не увенчался успехом. Как работает следующая функция (powerset), принимая пример входного аргумента [1,2,3]? Большое спасибо за помощь.

fun ps L = foldl (fn (x, tl) => tl @ map (fn xs => x :: xs) tl) [[]] L;

Answer 1

Чтобы использовать эту функцию правильно, вы должны предположить, что в списках ввода нет дублирования.

Эту функцию можно понимать следующим образом:

• Начнем с аккумулятором, который представляет собой набор множеств только состоящих из пустого множества ([[]]).
• На каждом шаге мы берем каждый набор в аккумуляторе, добавляем к ним текущий элемент x и добавляем эти результаты в аккумулятор.
• Конечным результатом является набор всех возможных наборов элементов n, т.е. poweret.

Чтобы легко выражать следы, давайте создадим вспомогательную функцию 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 *)