Миран Липовача - Изучай Haskell во имя добра!

Диаграмма на предыдущей странице иллюстрирует работу свёртки шаг за шагом, день за днём. Цифры слева от знака + представляют собой значения аккумулятора. Как вы можете видеть, аккумулятор будто бы «поедает» список, начиная с левой стороны. Ням-ням-ням! Если мы примем во внимание, что функции каррированы, то можем записать определение функции ещё более лаконично:

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, работает аналогично левой, только аккумулятор поглощает значения, начиная справа. Бинарная функция левой свёртки принимает аккумулятор как первый параметр, а текущее значение – как второй (\acc x –>… ); бинарная функция правой свёртки принимает текущее значение как первый параметр и аккумулятор – как второй (\x acc –>… ). То, что аккумулятор находится с правой стороны, в некотором смысле логично, поскольку он поглощает значения из списка справа.

Значение аккумулятора (и, следовательно, результат) функции foldrмогут быть любого типа. Это может быть число, булевское значение или даже список. Мы реализуем функцию mapс помощью правой свёртки. Аккумулятор будет списком; будем накапливать пересчитанные элементы один за другим. Очевидно, что начальным элементом является пустой список:

map' :: (a –> b) –> [a] –> [b]

map' f xs = foldr (\x acc –> f x : acc) [] xs

Если мы применяем функцию (+3)к списку [1,2,3], то обрабатываем список справа. Мы берём последний элемент, тройку, применяем к нему функцию, и результат оказывается равен 6. Затем добавляем это число к аккумулятору, который был равен []. 6:[]– то же, что и [6]; это новое значение аккумулятора. Мы применяем функцию (+3)к значению 2, получаем 5и при помощи конструктора списка :добавляем его к аккумулятору, который становится равен [5,6]. Применяем функцию (+3)к значению 1, добавляем результат к аккумулятору и получаем финальное значение [4,5,6].

Конечно, можно было бы реализовать эту функцию и при помощи левой свёртки:

map' :: (a -> b) -> [a] -> [b]

map' f xs = foldl (\acc x –> acc ++ [f x]) [] xs

Но операция конкатенации ++значительно дороже, чем конструктор списка :, так что мы обычно используем правую свёртку, когда строим списки из списков.

Если вы обратите список задом наперёд, то сможете выполнять правую свёртку с тем же результатом, что даёт левая свёртка, и наоборот. В некоторых случаях обращать список не требуется. Функцию sumможно реализовать как с помощью левой, так и с помощью правой свёртки. Единственное серьёзное отличие: правые свёртки работают на бесконечных списках, а левые – нет! Оно и понятно: если вы берёте бесконечный список в некоторой точке и затем сворачиваете его справа, рано или поздно вы достигаете начала списка. Если же вы берёте бесконечный список в некоторой точке и пытаетесь свернуть его слева, вы никогда не достигнете конца!