Foldable и Traversable

Свёртка — одна из самых важных интегральных характеристик во многих областях прикладной математики: сумма, среднее, максимум, норма — всё это свёртки коллекции данных в одно число. В Haskell свёртку можно провернуть на любом типе, обладающем экземпляром $\mathtt{Foldable}$, который держится на одном методе:

class Foldable t where
  foldMap :: Monoid w => (a -> w) -> t a -> w
  -- (в классе есть и другие методы, но foldMap достаточно)

-- контейнер t реализует Foldable
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
instance Semigroup (Tree a) where
  Empty      <> s     = s
  l          <> Empty = l
  Leaf x     <> s     = Node Empty x s
  Node l x r <> s     = Node l x (r <> s)
instance Monoid (Tree a) where mempty = Empty
instance Foldable Tree where
  foldMap _ Empty        = mempty
  foldMap f (Leaf x)     = f x
  foldMap f (Node l x r) = foldMap f l <> f x <> foldMap f r

newtype Sum a = Sum a
instance Num a => Semigroup (Sum a) where Sum x <> Sum y = Sum (x + y)
instance Num a => Monoid    (Sum a) where mempty = Sum 0

-- свернём дерево 1,2,3 моноидом Sum:
t = Node (Leaf 1) 2 (Leaf 3)
foldMap Sum t   -- Sum 6   (форма дерева схлопнулась в одно число)

На самом деле одного $\mathtt{foldMap}$ достаточно для вывода: $\mathtt{sum}$, $\mathtt{length}$, $\mathtt{maximum}$, $\mathtt{elem}$, $\mathtt{toList}$… Но $\mathtt{foldMap}$ сводит всю структуру к одному значению. А если на каждом элементе нужно выполнить вычисление — которое может провалиться, сходить в конфиг, накопить лог — и при этом собрать результаты, не потеряв форму структуры? Это умеет $\mathtt{Traversable}$.

Обратите внимание на классы $\mathtt{Functor}$ и $\mathtt{Foldable}$ в объявлении ниже: $\mathtt{traverse}$ настолько общий, что $\mathtt{fmap}$ и $\mathtt{foldMap}$ — его частные случаи. Подставьте вместо контекста $f$ обёртку без эффекта $\mathtt{Identity}$ — и $\mathtt{traverse}$ вырождается в $\mathtt{fmap}$, так что контейнер обязан быть $\mathtt{Functor}$. Подставьте $\mathtt{Const}\;w$ (аппликатив, когда $w$ — моноид) — и $\mathtt{traverse}$ вырождается в $\mathtt{foldMap}$, значит, всякий $\mathtt{Traversable}$ заодно и $\mathtt{Foldable}$. Оттого оба класса и вынесены в суперклассы:

class (Functor t, Foldable t) => Traversable t where
  traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
  sequenceA :: Applicative f => t (f a) -> f (t a)
  traverse g = sequenceA . fmap g   -- traverse и sequenceA взаимовыразимы

-- f = Identity (обёртка без эффекта):
(a -> Identity b) -> t a -> Identity (t b)  ≅  (a -> b) -> t a -> t b   -- fmap

-- f = Const w (Applicative, когда w — моноид):
(a -> Const w b)  -> t a -> Const w (t b)   ≅  (a -> w) -> t a -> w     -- foldMap

-- половинка чётного, иначе провал:
half :: Int -> Maybe Int
half x = if even x then Just (x `div` 2) else Nothing

traverse half [2, 4, 6]   -- Just [1,2,3]
traverse half [2, 3]      -- Nothing

Понятно, что $\mathtt{fmap\;half}$ даёт список коробок $[\mathtt{Maybe}\;\mathtt{Int}]$, а $\mathtt{sequenceA}$ выворачивает его в коробку списка $\mathtt{Maybe}\;[\mathtt{Int}]$; и стоит одному элементу вернуть $\mathtt{Nothing}$, как весь результат — $\mathtt{Nothing}$.

Осталось понять, откуда в сигнатуре $\mathtt{traverse}$ взялся именно $\mathtt{Applicative}$. В примере выше $\mathtt{sequenceA}$ склеивала контексты соседних элементов: $\mathtt{Just}$ с $\mathtt{Just}$, а любой $\mathtt{Nothing}$ обнулял результат. Для такой склейки нужны ровно два умения: $\mathtt{pure}$ — начать обход с «пустого» эффекта — и $\mathbin{\mathtt{<*>}}$ — присоединить эффект очередного элемента к уже накопленному. Это в точности интерфейс $\mathtt{Applicative}$: $\mathtt{Functor}$ здесь слаб ($\mathtt{fmap}$ не умеет сливать два контекста в один), а $\mathtt{Monad}$ избыточен ($\mathbin{\mathtt{>>=}}$ разрешает следующему шагу зависеть от результата предыдущего, но маршрут обхода и так жёстко задан формой структуры).

У $\mathtt{traverse}$ есть и законы. Самый наглядный — тождество: $\mathtt{traverse\;Identity = Identity}$, обход без эффекта не меняет ни форму, ни значения. Остальные два — композиция (два обхода подряд можно слить в один) и натуральность (обход согласован с заменой одного аппликатива на другой). Вместе они гарантируют, что $\mathtt{traverse}$ обходит каждый элемент ровно один раз и сохраняет форму структуры.

Так шестёрка классов и замыкается: $\mathtt{Monoid}$ комбинирует значения, $\mathtt{Functor}$ / $\mathtt{Applicative}$ / $\mathtt{Monad}$ применяют функции во всё более сильных контекстах, $\mathtt{Foldable}$ / $\mathtt{Traversable}$ обходят структуры — и практически весь «бойлерплейт» обработки данных сводится к ним.