Функция свёртки принимает бинарную функцию, начальное значение (мне нравится называть его «аккумулятором») и список. Бинарная функция принимает два параметра. Она вызывается с аккумулятором и первым (или последним) элементом из списка и вычисляет новое значение аккумулятора. Затем функция вызывается снова, с новым значением аккумулятора и следующим элементом из списка, и т. д. То, что остаётся в качестве значения аккумулятора после прохода по всему списку, и есть результат свёртки.
Левая свёртка foldl
Для начала рассмотрим функцию foldl – свёртка слева. Она сворачивает список, начиная с левой стороны. Бинарная функция применяется для начального значения и первого элемента списка, затем для вновь вычисленного аккумулятора и второго элемента списка и т. д.
Снова реализуем функцию sum, но на этот раз будем пользоваться свёрткой вместо явной рекурсии.
sum' :: (Num a) => [a] –> a
sum' xs = foldl (\acc x –> acc + x) 0 xs
Проверка – раз, два, три!
ghci> sum' [3,5,2,1]
11
Давайте посмотрим более внимательно, как работает функция foldl. Бинарная функция – это лямбда-выражение (\acc x –> acc + x), нуль – стартовое значение, и xs – список. В самом начале нуль используется как значение аккумулятора, а 3 – как значение образца x (текущий элемент). Выражение (0+3) в результате даёт 3; это становится новым значением аккумулятора. Далее, 3 используется как значение аккумулятора и 5 – как текущий элемент; новым значением аккумулятора становится 8. На следующем шаге 8 – значение аккумулятора, 2 – текущий элемент, новое значение аккумулятора становится равным 10. На последнем шаге 10 из аккумулятора и 1 как текущий элемент дают 11. Поздравляю – вы только что выполнили свёртку списка!
Диаграмма на предыдущей странице иллюстрирует работу свёртки шаг за шагом, день за днём. Цифры слева от знака + представляют собой значения аккумулятора. Как вы можете видеть, аккумулятор будто бы «поедает» список, начиная с левой стороны. Ням-ням-ням! Если мы примем во внимание, что функции каррированы, то можем записать определение функции ещё более лаконично:
sum' :: (Num a) => [a] –> a
sum' = foldl (+) 0
Анонимная функция (\acc x –> acc + x) – это то же самое, что и оператор (+). Мы можем пропустить xs в параметрах, потому что вызов foldl (+) 0 вернёт функцию, которая принимает список. В общем, если у вас есть функция вида foo a = bar b a, вы всегда можете переписать её как foo = bar b, так как происходит каррирование.
Ну что ж, давайте реализуем ещё одну функцию с левой свёрткой перед тем, как перейти к правой. Уверен, все вы знаете, что функция elem проверяет, является ли некоторое значение частью списка, так что я не буду этого повторять (тьфу ты – не хотел, а повторил!). Итак:
elem' :: (Eq a) => a –> [a] –> Bool
elem' y ys = foldl (\acc x –> if x == y then True else acc) False ys
Что мы имеем? Стартовое значение и аккумулятор – булевские значения. Тип аккумулятора и стартового значения в свёртках всегда совпадают. Запомните это правило: оно может подсказать вам, что следует использовать в качестве стартового значения, если вы затрудняетесь. В данном случае мы начинаем со значения False. В этом есть смысл: предполагается, что в списке нет искомого элемента. Если мы вызовем функцию свёртки с пустым списком, то результатом будет стартовое значение. Затем мы проверяем текущий элемент на равенство искомому. Если это он – устанавливаем в True. Если нет – не изменяем аккумулятор. Если он прежде был равен значению False, то остаётся равным False, так как текущий элемент – не искомый. Если же был равен True, мы опять-таки оставляем его неизменным.
Правая свёртка foldr
Правая свёртка, foldr, работает аналогично левой, только аккумулятор поглощает значения, начиная справа. Бинарная функция левой свёртки принимает аккумулятор как первый параметр, а текущее значение – как второй (\acc x –> …); бинарная функция правой свёртки принимает текущее значение как первый параметр и аккумулятор – как второй (\x acc –> …). То, что аккумулятор находится с правой стороны, в некотором смысле логично, поскольку он поглощает значения из списка справа.