Левая свёртка 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, мы опять-таки оставляем его неизменным.