Foldable and Traversable: Two More Members of the Family
Functor, Applicative, and Monad each earned a full chapter. Foldable and Traversable are the two typeclasses quietly completing that family — one generalizing sum, length, and toList to any structure at all, the other generalizing what it means to run an effectful function over every element and get the effects back in the right shape.
Foldable: reducing a structure to one value
sum, length, maximum, elem, toList — every one of these has been used on lists throughout this book as if they were list-specific functions. They aren’t. They’re Foldable’s functions, and Foldable has nothing to do with lists specifically:
class Foldable t where
foldr :: (a -> b -> b) -> b -> t a -> b
-- sum, length, maximum, elem, toList all have default
-- implementations in terms of foldr alone
Give Foldable one function — foldr, exactly the fold Chapter 3 already built by hand — and sum, length, toList, and the rest come along for free, derived automatically from that single method. Common Algorithms’ binary search tree can be Foldable too, with no list involved anywhere in its own definition:
data BST a = Leaf | Node (BST a) a (BST a)
instance Foldable BST where
foldr f z Leaf = z
foldr f z (Node l x r) = foldr f (f x (foldr f z r)) l
ghci> toList myTree
[3,5,8]
ghci> sum myTree
16
ghci> length myTree
3
toList walks the tree in-order (left, node, right) purely as a consequence of this one foldr definition — and sum, length, maximum, and every other Foldable method work correctly on BST immediately, without a single extra line of instance code. Maybe is Foldable too, holding zero or one element (sum Nothing == 0, sum (Just 5) == 5) — the exact same interface, scaled down to the smallest possible container.
Foldable’s toList throws away structure on purpose — a BST’s shape, an Either’s left-vs-right distinction, all of it collapses into “here are the elements, in some order.” That’s precisely the right tool when only the elements matter; it’s the wrong one the moment the shape itself carries meaning worth preserving, which is exactly what Traversable, below, is for.
Traversable: mapping with effects, without losing the shape
fmap (Chapter 9) applies an ordinary function inside a structure, preserving its shape. What happens when the function you want to apply is effectful — returns a Maybe, an IO, an Either — and you want the effects combined too, not just the values mapped over?
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
validateAge :: Int -> Either String Int
validateAge n
| n < 0 || n > 150 = Left ("invalid age: " ++ show n)
| otherwise = Right n
ghci> traverse validateAge [25, 30, 45]
Right [25,30,45]
ghci> traverse validateAge [25, -5, 45]
Left "invalid age: -5"
traverse validateAge applies validateAge to every element — producing an Either String Int for each one — and then, rather than leaving a [Either String Int] behind, combines all those Eithers into one Either String [Int], using exactly Either’s own Applicative instance (Chapter 10) to do the combining. The moment any single element fails, Either’s short-circuiting <*> means traverse stops right there, with a Left, never even examining the remaining elements — -5 fails, 45 is never checked.
sequenceA :: Applicative f => t (f a) -> f (t a) is traverse id — the special case where the elements are already wrapped, and all that’s needed is turning “a list of wrapped things” into “one wrapped list”:
ghci> sequenceA [Just 1, Just 2, Just 3]
Just [1,2,3]
ghci> sequenceA [Just 1, Nothing, Just 3]
Nothing
Traversable’s superclass constraint — (Functor t, Foldable t) => Traversable t — isn’t decorative. traverse genuinely needs both capabilities simultaneously: the mapping half (visiting and transforming every element, Functor’s job) and the shape-preserving reconstruction half (rebuilding the same container afterward, which needs to know the container’s own structure the way Foldable does). Neither Functor nor Foldable alone is enough to define traverse.
Figure: Every typeclass this book has built, in one map — an arrow means “requires,” and Traversable needs both a Functor and a Foldable at once.
Seven typeclasses, three families, one underlying shape each time: Semigroup/Monoid combine values; Functor/Applicative/Monad map, combine, and sequence effects; Foldable/Traversable reduce and walk structures. None of them were invented in isolation — each one is either a direct generalization of something Chapter 3’s foldr or Chapter 9’s fmap already did for lists specifically, lifted to work over any structure with the right shape.
Category theory’s own name for a Traversable functor is exactly that: a traversable functor, and the laws traverse must satisfy — preserving identity (traverse Identity = Identity) and composing predictably with other traversals — are precisely the conditions that guarantee traverse genuinely “commutes” the two layers of structure (the container, the effect) without silently reordering or dropping anything. This is the same law-abiding-interface story Chapter 9 opened with, one level further generalized.
traverse and sequenceA show up constantly the moment a program needs to run several independent, possibly-failing operations and collect every result — validating a form’s several fields at once (each field’s validator returning Either), fetching a list of URLs where any single request might fail, or reading several config files and only proceeding if every one parses. mapM, an older, Monad-specific name for the same idea, still appears throughout real Haskell code; traverse is the modern, more general name for exactly the same operation.
Foldable and Traversable were never separate ideas bolted onto this book’s story — they’re foldr and fmap, generalized exactly as far as Functor, Applicative, and Monad already were, closing the last gap in a family this book has been building, one chapter at a time, since Chapter 9.