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