Интуиция⌗

Класс Data.Foldable представляет собой абстракцию над такими (часто контейнерными) типами данных, которые допускают свёртку (fold). Для этих типов осмыслена и определена операция коллапса, то есть разрушения и схлопывания всей структуры в одно единственное итоговое значение (дайджест, резюме).

> foldr (+) 100 $ Node 2 [Node 1 [], Node 3 []]
106

> let f = foldr (.) id [(+1), (*2), (+10)]
> :t f
f :: Num b => b -> b
> f 1
23

Если некоторый тип t реализует интерфейс тайпкласса Data.Foldable, то это означает, что для данного типа t указана механика осуществления его свёртки.

Механику коллапса структуры данных можно выразить одной из двух функций:

-- Независимое описание процесса свёртки вручную
foldr :: (a -> b -> b) -> b -> t a -> b

-- Упрощённое описание: установление связи каждого элемента структуры
--   с некоторым моноидом (свёртка происходит уже внутри моноида)
foldMap :: Monoid m => (a -> m) -> t a -> m

Создадим реализацию Data.Foldable для следующего рекурсивного типа:

-- Тип для нашего списка
data List a = Cons a (List a) | Nil

-- Пример списка
li = Cons 1 (Cons 2 (Cons 3 (Cons 4 (Cons 5 Nil))))

Реализация Foldable при помощи некоторого моноида⌗

В самом простом случае мы можем описать механику ассоциирования элементов List с данным (на вход) моноидом, написав функцию foldMap.

Чтобы отобразить все элементы List в моноид m необходимо:

• отобразить в m голову списка
• рекурсивно выполнится для оставшегося хвоста списка (отобразить голову хвоста списка и т.д.)
• при этом склеивать между собой все элементы внутри моноида
• конец нашего списка (конструктор Nil) соответствует нейтральному элементу моноида

instance Foldable List where
  -- foldMap :: Monoid m => a -> m -> List a -> m
  foldMap f (Cons x xs) = f x <> foldMap f xs
  foldMap _ Nil = mempty

Моноид recap⌗

Напомним, что фундаментальное свойство любого моноида – наличие бинарной операции mappend (синоним: <>) для склеивания двух элементов моноида в один, а также наличие нейтрального элемента mempty, не меняющего результат склейки. Например, вот как происходит склейка внутри моноида по сложению Sum:

> Sum 10 <> mempty <> Sum 6 <> Sum 4
Sum {getSum = 20}

Реализации foldMap достаточно, чтобы для нашего типа List a стал доступен весь арсенал интерфейса Foldable (используем список li, определённый выше):

> foldMap Sum li
Sum {getSum = 15}
> maximum li
5
> minimum li
1
> mapM_ (\x -> putStrLn ("Element " ++ show x)) li
Element 1
Element 2
Element 3
Element 4
Element 5
> find (\x -> x == 3) li
Just 3
> find (\x -> x == 6) li
Nothing

И мы получили это всё нахаляву, написав лишь одну функцию foldMap!

Реализация Foldable при помощи описания процесса свёртки⌗

Более сложный, но независимый путь, не требующий готовых моноидов, – это создание механики разрушения структуры посредством foldr:

foldr  :: (a -> b -> b) -> b -> t a -> b

Функция foldr имеет сложную сигнатуру, которую можно разложить на три компонента (справа-налево):

• t a – собственно наша структура данных, которую мы сворачиваем
• b – начальное значение аккумулятора
• (a -> b -> b) – функция от одного элемента нашей структуры и от текущего значения аккумулятора, возвращающая новое значение аккумулятора

Аккумулятор нужен, как не трудно догадаться, для “протаскивания” (и, возможно, попутной модификации) дайджеста-аккумулятора через всю структуру: мы схлопываем t a в финальное значение аккумулятора b.

Правоассоциативная операция foldr последовательно разрушает (редуцирует) структуру справа-налево:

-- Ассоциативность справа, т.е. выражение ветвится вправо: f x1 (f x2 (f xn z))
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

Идея нашей реализации проста: отсекаем голову списка и производим свёртку хвоста (рекурсивно). При этом начальное значение аккумулятора start окажется в самой глубине выражения, а при редукции каждый последующий foldr будет возвращать новое значение аккумулятора, вплоть до сокращения всего выражения:

instance Foldable List where
-- foldr  :: (a -> b -> b) -> b -> t a -> b
  foldr f start (Cons x xs) = (x `f` (foldr f start xs))
  foldr _ acc Nil = acc

Теперь мы можем осуществлять свёртку без помощи сторонних моноидов. Написание foldr достаточно для включения нашего List в тайпкласс Data.Foldable!

-- разрушение происходит справа (сначала 5, потом 4, ...)
> foldr (\e (s, log) -> (s + e, log ++ " added " ++ show e)) (0, "") li
(15," added 5 added 4 added 3 added 2 added 1")

-- разрушение происходит слева (сначала 1, потом 2, ...)
> foldl (\(s, log) e -> (s + e, log ++ " added " ++ show e)) (0, "") li
(15," added 1 added 2 added 3 added 4 added 5")

Кстати, при помощи foldr можно написать foldl, но не наоборот (для бесконечных структур)!