Изучай Haskell во имя добра! (Липовача) - страница 58

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