Правая свёртка foldr

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