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

Значение аккумулятора (и, следовательно, результат) функции 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] Это так. В качестве упражнения повышенной сложности читателю рекомендуется реализовать при помощи свёртки функции drop и dropWhile из стандартной библиотеки. – Прим. ред. . Если вам нужно обойти список для того, чтобы что-либо вычислить, скорее всего, вам нужна свёртка. Вот почему свёртки, наряду с функциями mapи filter, – одни из наиболее часто используемых функций в функциональном программировании.

Функции 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) []

Здесь мы обращаем список, пользуясь пустым списком как начальным значением аккумулятора, и, обходя затем исходный список слева, добавляем текущий элемент в начало аккумулятора.

Функция \acc x -> x : acc– почти то же, что и операция :, за исключением порядка следования параметров. Поэтому функцию reverse'можно переписать и так:

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

reverse' = foldl (flip (:)) []

Теперь реализуем функцию product:

product' :: (Num a) => [a] -> a

product' = foldl (*) 1

Чтобы вычислить произведение всех элементов списка, следует начать с аккумулятора равного 1. Затем мы выполняем свёртку функцией (*), которая перемножает каждый элемент списка на аккумулятор.

Вот реализация функции filter:

filter' :: (a -> Bool) -> [a] -> [a]

filter' p = foldr (\x acc -> if p x then x : acc else acc) []

Здесь начальное значение аккумулятора является пустым списком. Мы сворачиваем список справа налево и проверяем каждый элемент, пользуясь предикатом p. Если p xвозвращает истину, элемент xпомещается в начало аккумулятора. В противном случае аккумулятор остаётся без изменения.

Напоследок реализуем функцию last:

last' :: [a] -> a

last' = foldl1 (\ x -> x)

Для получения последнего элемента списка мы применяем foldr1. Начинаем с «головы» списка, а затем применяем бинарную функцию, которая игнорирует аккумулятор и устанавливает текущий элемент списка как новое значение аккумулятора. Как только мы достигаем конца списка, аккумулятор — то есть последний элемент – возвращается в качестве результата свёртки.

Есть ещё один способ представить работу правой и левой свёртки. Скажем, мы выполняем правую свёртку с бинарной функцией fи стартовым значением z. Если мы применяем правую свёртку к списку [3,4,5,6], то на самом деле вычисляем вот что:

f 3 (f 4 (f 5 (f 6 z)))

Функция fвызывается с последним элементом в списке и аккумулятором; получившееся значение передаётся в качестве аккумулятора при вызове функции с предыдущим значением, и т. д. Если мы примем функцию fза операцию сложения и начальное значение за нуль, наш пример преобразуется так: