Поскольку существует так много структур данных, которые хорошо работают со свёртками, был введён класс типов >Foldable. Подобно тому как класс >Functor предназначен для сущностей, которые можно отображать, класс >Foldable предназначен для вещей, которые могут быть свёрнуты! Его можно найти в модуле >Data.Foldable; и, поскольку он экспортирует функции, имена которых конфликтуют с именами функций из модуля >Prelude, его лучше импортировать, квалифицируя (и подавать с базиликом!):
>import qualified Data.Foldable as F
Чтобы сэкономить драгоценные нажатия клавиш, мы импортировали его, квалифицируя как >F.
Так какие из некоторых функций определяет этот класс типов? Среди них есть функции >foldr, >foldl, >foldr1 и >foldl1. Ну и?.. Мы уже давно знакомы с ними! Что ж в этом нового? Давайте сравним типы функции >foldr из модуля >Foldable и одноимённой функции из модуля >Prelude, чтобы узнать, чем они отличаются:
>ghci> :t foldr
>foldr :: (a –> b –> b) –> b –> [a] –> b
>ghci> :t F.foldr
>F.foldr :: (F.Foldable t) => (a –> b –> b) –> b –> t a –> b
А-а-а! Значит, в то время как функция >foldr принимает список и сворачивает его, функция >foldr из модуля >Data.Foldable принимает любой тип, который можно свернуть, – не только списки! Как и ожидалось, обе функции >foldr делают со списками одно и то же:
>ghci> foldr (*) 1 [1,2,3]
>6
>ghci> F.foldr (*) 1 [1,2,3]
>6
Другой структурой данных, поддерживающей свёртку, является >Maybe, которую мы все знаем и любим!
>ghci> F.foldl (+) 2 (Just 9)
>11
>ghci> F.foldr (||) False (Just True)
>True
Но сворачивание значения >Maybe не очень-то интересно. Оно действует просто как список с одним элементом, если это значение >Just, и как пустой список, если это значение >Nothing. Давайте рассмотрим чуть более сложную структуру данных.
Помните древовидную структуру данных из главы 7? Мы определили её так:
>data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
Вы узнали, что дерево – это либо пустое дерево, которое не содержит никаких значений, либо узел, который содержит одно значение, а также два других дерева. После того как мы его определили, мы сделали для него экземпляр класса >Functor, и это дало нам возможность отображать его с помощью функций, используя функцию >fmap. Теперь мы определим для него экземпляр класса >Foldable, чтобы у нас появилась возможность производить его свёртку.
Один из способов сделать для конструктора типа экземпляр класса >Foldable состоит в том, чтобы просто напрямую реализовать для него функцию >foldr. Но другой, часто более простой способ состоит в том, чтобы реализовать функцию