Foldable and Traversable

Folding is one of the most important integral characteristics in many areas of applied mathematics: sum, mean, maximum, norm — all of these fold a collection of data into a single number. In Haskell a fold can be pulled off on any type that has an instance of $\mathtt{Foldable}$, which rests on a single method:

class Foldable t where
  foldMap :: Monoid w => (a -> w) -> t a -> w
  -- (the class has other methods too, but foldMap is enough)

-- a container t implements 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

-- fold the tree 1,2,3 with the Sum monoid:
t = Node (Leaf 1) 2 (Leaf 3)
foldMap Sum t   -- Sum 6   (the tree's shape collapsed into a single number)

In fact, $\mathtt{foldMap}$ alone is enough to derive $\mathtt{sum}$, $\mathtt{length}$, $\mathtt{maximum}$, $\mathtt{elem}$, $\mathtt{toList}$… But $\mathtt{foldMap}$ reduces the whole structure to a single value. What if at every element we need to run a computation — one that can fail, hit a config, accumulate a log — and still collect the results without losing the shape of the structure? That is what $\mathtt{Traversable}$ does.

Note the classes $\mathtt{Functor}$ and $\mathtt{Foldable}$ in the declaration below: $\mathtt{traverse}$ is so general that $\mathtt{fmap}$ and $\mathtt{foldMap}$ are its special cases. Substitute the effect-free wrapper $\mathtt{Identity}$ for the context $f$ — and $\mathtt{traverse}$ degenerates into $\mathtt{fmap}$, so the container must be a $\mathtt{Functor}$. Substitute $\mathtt{Const}\;w$ (an applicative whenever $w$ is a monoid) — and $\mathtt{traverse}$ degenerates into $\mathtt{foldMap}$, which means every $\mathtt{Traversable}$ is also a $\mathtt{Foldable}$. That is why both classes end up as superclasses:

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 and sequenceA are interdefinable

-- f = Identity (an effect-free wrapper):
(a -> Identity b) -> t a -> Identity (t b)  ≅  (a -> b) -> t a -> t b   -- fmap

-- f = Const w (an Applicative whenever w is a monoid):
(a -> Const w b)  -> t a -> Const w (t b)   ≅  (a -> w) -> t a -> w     -- foldMap

-- half of an even number, failure otherwise:
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

Clearly, $\mathtt{fmap\;half}$ yields a list of boxes $[\mathtt{Maybe}\;\mathtt{Int}]$, and $\mathtt{sequenceA}$ turns it inside out into a box with a list, $\mathtt{Maybe}\;[\mathtt{Int}]$; and as soon as a single element returns $\mathtt{Nothing}$, the whole result is $\mathtt{Nothing}$.

It remains to see why the signature of $\mathtt{traverse}$ demands precisely $\mathtt{Applicative}$. In the example above $\mathtt{sequenceA}$ glued together the contexts of neighbouring elements: $\mathtt{Just}$ with $\mathtt{Just}$, while any $\mathtt{Nothing}$ wiped out the result. Such gluing takes exactly two skills: $\mathtt{pure}$ — to start the traversal with an “empty” effect — and $\mathbin{\mathtt{<*>}}$ — to attach the effect of the next element to what has already been accumulated. That is precisely the $\mathtt{Applicative}$ interface: $\mathtt{Functor}$ is too weak here ($\mathtt{fmap}$ cannot merge two contexts into one), while $\mathtt{Monad}$ is overkill ($\mathbin{\mathtt{>>=}}$ lets the next step depend on the result of the previous one, but the route of the traversal is rigidly fixed by the shape of the structure anyway).

$\mathtt{traverse}$ comes with laws, too. The most graphic one is identity: $\mathtt{traverse\;Identity = Identity}$ — an effect-free traversal changes neither the shape nor the values. The other two are composition (two consecutive traversals can be fused into one) and naturality (a traversal is consistent with swapping one applicative for another). Together they guarantee that $\mathtt{traverse}$ visits every element exactly once and preserves the shape of the structure.

And so the six classes close the loop: $\mathtt{Monoid}$ combines values, $\mathtt{Functor}$ / $\mathtt{Applicative}$ / $\mathtt{Monad}$ apply functions in ever more powerful contexts, $\mathtt{Foldable}$ / $\mathtt{Traversable}$ traverse structures — and practically all the data-processing boilerplate boils down to these six.