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 за операцию сложения и начальное значение за нуль, наш пример преобразуется так:
3 + (4 + (5 + (6 + 0)))
Или, если записать оператор + как префиксную функцию, получится:
(+) 3 ((+) 4 ((+) 5 ((+) 6 0)))
Аналогичным образом левая свёртка с бинарной функцией g и аккумулятором z является эквивалентом выражения
g (g (g (g z 3) 4) 5) 6
Если заменить бинарную функцию на flip (:) и использовать [] как аккумулятор (выполняем обращение списка), подобная запись эквивалентна следующей:
flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6
Если вычислить это выражение, мы получим [6,5,4,3].
Свёртка бесконечных списков
Взгляд на свёртки как на последовательное применение функции к элементам списка помогает понять, почему правая свёртка иногда отлично работает с бесконечными списками. Давайте реализуем функцию and с помощью foldr, а потом выпишем последовательность применений, как мы это делали в предыдущих примерах. Тогда мы увидим, как ленивость языка Haskell позволяет правой свёртке обрабатывать бесконечные списки.
Функция and принимает список значений типа Bool и возвращает False, если хотя бы один из элементов равен False; в противном случае она возвращает True. Мы будем обходить список справа, используя True как начальное значение. В качестве бинарной функции будем использовать операцию &&, потому что должны вернуть True только в том случае, когда все элементы списка истинны. Функция && возвращает False, если хотя бы один из параметров равен False, поэтому если мы встретим в списке False, то аккумулятор будет установлен в значение False и окончательный результат также будет False, даже если среди оставшихся элементов списка обнаружатся истинные значения.
and' :: [Bool] -> Bool
and' xs = foldr (&&) True xs
Зная, как работает foldr, мы видим, что выражение and' [True,False,True] будет вычисляться следующим образом:
True && (False && (True && True))
Последнее True здесь – это начальное значение аккумулятора, тогда как первые три логических значения взяты из списка [True,False,True]. Если мы попробуем вычислить результат этого выражения, получится False.