Foldable и Traversable: обход с эффектом

Замок блока абстракций. Два класса, которые соединяют всё пройденное. Foldable обобщает свёртки с списков на любой контейнер через foldMap, опираясь на моноиды. Traversable добавляет к обходу эффект через traverse, опираясь на аппликативы. В этом уроке: foldMap, fold, toList и почему sum и length работают на чём угодно, traverse и sequenceA, главный приём (перевернуть слои структуры), зачем это в ежедневном коде и инстансы для собственного дерева.

Идея

В уроке про свёртки foldr работал только со списками. Но обходить и схлопывать в одно значение хочется не только списки: дерево, Map, Set, даже Maybe (ноль или один элемент). Класс, который выносит свёртку за пределы списка, это Foldable:

class Foldable t where
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr   :: (a -> b -> b) -> b -> t a -> b
  -- минимальное определение: foldMap или foldr

Узнаёшь foldMap? Это ровно та затравка из урока про моноиды: преврати каждый элемент в моноид, потом склей всё через <>. Тогда он работал на списках, теперь на любом Foldable. И как только тип это Foldable, он бесплатно получает целый набор функций, выраженных через foldMap:

sum, product       :: (Foldable t, Num a) => t a -> a
length             :: Foldable t => t a -> Int
null               :: Foldable t => t a -> Bool
elem               :: (Foldable t, Eq a) => a -> t a -> Bool
maximum, minimum   :: (Foldable t, Ord a) => t a -> a
toList             :: Foldable t => t a -> [a]
and, or, any, all  :: Foldable t => ...

Все они это foldMap с правильным моноидом из урока 09: sum это foldMap Sum, length это foldMap (const (Sum 1)), any это foldMap (Any . p), toList это foldMap (:[]). Один класс, и весь этот словарь заработал для каждого контейнера разом:

ghci> sum (Just 5)
5
ghci> length (Just 5)
1
ghci> length Nothing
0
ghci> sum [1, 2, 3]
6
ghci> maximum (Right 9 :: Either String Int)
9
ghci> toList (Just 'a')
"a"

Maybe это контейнер на ноль или один элемент, и sum, length, toList относятся к нему именно так. Вот зачем это в повседневном коде: length, null, elem, toList не привязаны к спискам, они работают на Map, Set, Seq из стандартных библиотек, на твоих собственных деревьях. Foldable это право свернуть структуру, и оно дано многим типам.