Изучай Haskell во имя добра!

Правая свёртка, 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 можно реализовать как с помощью левой, так и с помощью правой свёртки. Единственное серьёзное отличие: правые свёртки работают на бесконечных списках, а левые – нет! Оно и понятно: если вы берёте бесконечный список в некоторой точке и затем сворачиваете его справа, рано или поздно вы достигаете начала списка. Если же вы берёте бесконечный список в некоторой точке и пытаетесь свернуть его слева, вы никогда не достигнете конца!

Свёртки могут быть использованы для реализации любой функции, где вы вычисляете что-либо за один обход списка[8]. Если вам нужно обойти список для того, чтобы что-либо вычислить, скорее всего, вам нужна свёртка. Вот почему свёртки, наряду с функциями map и filter, – одни из наиболее часто используемых функций в функциональном программировании.

Функции foldl1 и foldr1

Функции foldl1 и foldr1 работают примерно так же, как и функции foldl и foldr, только нет необходимости явно задавать стартовое значение. Они предполагают, что первый (или последний) элемент списка является стартовым элементом, и затем начинают свёртку со следующим элементом. Принимая это во внимание, функцию maximum можно реализовать следующим образом:

maximum' :: (Ord a) => [a] -> a

maximum' = foldl1 max

Мы реализовали функцию maximum, используя foldl1. Вместо использования начального значения функция foldl1 предполагает, что таковым является первый элемент списка, после чего перемещается к следующему. Поэтому всё, что ей необходимо, – это бинарная функция и сворачиваемый лист! Мы начинаем с «головы» списка и сравниваем каждый элемент с аккумулятором. Если элемент больше аккумулятора, мы сохраняем его в качестве нового значения аккумулятора; в противном случае сохраняем старое. Мы передаём функцию max в качестве параметра foldl1, поскольку она ровно это и делает: берёт два значения и возвращает большее. К моменту завершения свёртки останется самый большой элемент.

По скольку эти функции требуют, чтобы сворачиваемые списки имели хотя бы один элемент, то, если вызвать их с пустым списком, произойдёт ошибка времени выполнения.

С другой стороны, функции foldl и foldr хорошо работают с пустыми списками. Подумайте, имеет ли смысл свёртка для пустых списков в вашем контексте. Если функция не имеет смысла для пустого списка, то, возможно, вы захотите использовать функции foldl1 или foldr1 для её реализации.

Примеры свёрток

Для того чтобы показать, насколько мощны свёртки, мы собираемся реализовать с их помощью несколько стандартных библиотечных функций. Во-первых, реализуем свою версию функции reverse:

reverse' :: [a] -> [a]

reverse' = foldl (\acc x -> x : acc) []