и >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. Затем мы выполняем свёртку функцией >(*), которая перемножает каждый элемент списка на аккумулятор.