Haskell: понимание функции foldl

Question

Я узнаю о фолдах из «Изучу тебя на гаскелле за великое благо!» Миран Липовача.

Для следующего примера, в котором используется foldl:

sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs 

ghci> sum' [3,5,2,1]
11

Я понимаю, что acc - это аккумулятор, а x - это начальное значение (первое значение из списка xs). Я не совсем понимаю, как 0 и xs передаются в лямбда-функцию в качестве параметров - как функция узнает, что значение acc равно 0, а значение x равно 3? Любые идеи приветствуются.

Answer 1

Вспомните определение foldl:

foldl f acc []     = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

Теперь, лучший способ понять сгибы - это пройти оценку.Итак, начнем с:

sum [3,5,2,1]
== foldl (\acc x -> acc + x) 0 [3,5,2,1]

Вторая строка определения функции foldl означает, что это эквивалентно следующему:

== foldl (\acc x -> acc + x) ((\acc x -> acc + x) 0 3) [5,2,1]

Теперь, когда применяется лямбда-выражениек параметрам 0 и 3 передаются как acc и x:

== foldl (\acc x -> acc + x) (0+3) [5,2,1]

И процесс повторяется:

== foldl (\acc x -> acc + x) ((\acc x -> acc + x) (0+3) 5) [2,1]
== foldl (\acc x -> acc + x) ((0+3)+5) [2,1]
== foldl (\acc x -> acc + x) ((\acc x -> acc + x) ((0+3)+5) 2) [1]
== foldl (\acc x -> acc + x) (((0+3)+5)+2) [1]
== foldl (\acc x -> acc + x) ((\acc x -> acc + x) (((0+3)+5)+2) 1) []
== foldl (\acc x -> acc + x) ((((0+3)+5)+2)+1) []

На этом этапе оценкипродолжается в соответствии с первой строкой определения foldl:

== ((((0+3)+5)+2)+1)

Итак, чтобы ответить на ваш вопрос напрямую: функция знает значения acc и x просто потому, что определение foldlпередает свои значения в функцию в качестве параметров.

Answer 2

Было бы полезно посмотреть, как определяется функция foldl:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f a []     = a
foldl f a (x:xs) = foldl f (f a x) xs

Итак, если список ввода пуст, мы просто возвращаем значение аккумулятора a.Однако, если он не пустой, мы зациклимся.Внутри цикла мы обновляем значение аккумулятора на f a x (т.е. применяем лямбда-функцию f к текущему значению аккумулятора и текущему элементу списка).Результатом является новое значение аккумулятора.

Мы также обновляем значение списка в цикле, удаляя его первый элемент (потому что мы только что обработали первый элемент).Мы продолжаем обрабатывать оставшиеся элементы списка до тех пор, пока не останется никаких элементов, после чего мы возвращаем значение аккумулятора.

Функция foldl эквивалентна циклу for в императивных языках.Например, вот как мы могли бы реализовать foldl в JavaScript:

const result = foldl((acc, x) => acc + x, 0, [3,5,2,1]);

console.log(result);

function foldl(f, a, xs) {
    for (const x of xs) a = f(a, x);
    return a;
}

Надеюсь, что разъяснит функцию foldl.