Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 57 ยท Functors, applicatives and monads

Foldable and Traversable

Learn Haskell's Foldable and Traversable classes: fold any container, then use traverse, sequenceA and mapM to run effects such as validation over a list.

Folds are not only for lists. You can sum the values in a Maybe, count the nodes of a tree, or find the largest value in a Map. Haskell gives all of these one vocabulary through the Foldable class. Its partner Traversable goes one step further: it lets you walk a container and run an effect at each element, for example "validate every field, and fail if any fails".

This lesson pulls together functors, applicatives, monads and monoids, so it is a good moment to re-read any of them that felt shaky.

Real Haskell is not installed here, so Haskell blocks are read-only. The runnable examples are JavaScript stand-ins.

Foldable: one fold, many containers

Foldable abstracts "something you can reduce to a single value". Its core is either foldr or foldMap; you get dozens of functions for free:

HASKELL
foldr   :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

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

You may recall that the Prelude's sum and length look as if they work only on lists (see Higher-Order Functions). In current GHC they are Foldable methods, so these all work:

HASKELL
sum (Just 5)             -- 5
sum Nothing              -- 0
length (Right 'x')       -- 1
length (Left "error")    -- 0
maximum (3, 9)           -- 9  (a pair folds over its second component)

A Maybe is a container with zero or one element; an Either e with Left is empty. Data.Map folds over its values.

Fold or traverse?

Foldable Reduce to one value.
Traversable Visit each, keep the shape.

Traverse runs an effect at every element.

1 / 2

Folding your own type

A tree becomes Foldable by describing how to combine its parts:

HASKELL
data Tree a = Leaf | Node (Tree a) a (Tree a)

instance Foldable Tree where
  foldMap _ Leaf = mempty
  foldMap f (Node l x r) = foldMap f l <> f x <> foldMap f r

That single definition unlocks sum, length, elem, maximum, toList and more for trees. The order of l, x, r here gives an in-order walk. You can also write deriving Foldable with the DeriveFoldable extension.

Stand-in: folds across containers

In JavaScript we model the idea with a tiny toList per container and build the folds on top. This is a stand-in; real Haskell dispatches on the type through the class.

JS One toList, many folds

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Traversable: effects at every element

Suppose parseAge :: String -> Maybe Int and you have a list of strings. map parseAge gives [Maybe Int], a list of possible results. Usually you want the opposite: one Maybe [Int] that is Just only if every element parsed. Turning the layers inside out is what Traversable does:

HASKELL
class (Functor t, Foldable t) => Traversable t where
  traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
sequenceA = traverse id

Examples with Maybe:

HASKELL
traverse readAge ["30", "41", "25"]    -- Just [30,41,25]
traverse readAge ["30", "oops", "25"]  -- Nothing

sequenceA [Just 1, Just 2]             -- Just [1,2]
sequenceA [Just 1, Nothing]            -- Nothing

(readAge could be readMaybe from Text.Read.) The type of traverse shows the rule: you give a function that returns a wrapped value for each element, and you get the whole container wrapped once. The effect of the applicative decides how the pieces combine: Maybe fails if any element fails, Either e reports the first Left, and IO runs every action in order.

mapM and friends

mapM is traverse with a monad constraint. In modern Haskell they behave the same, and traverse is preferred because it needs only an applicative:

HASKELL
mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
forM = flip mapM

-- IO example:
-- names <- mapM (\n -> readFile n) ["a.txt", "b.txt"]

mapM_ and traverse_ throw the results away, which is what you want when you only care about the effect, such as mapM_ print [1, 2, 3].

Validating a list

Recall the Either validation from Applicative Functors. traverse scales it to any number of items:

HASKELL
checkAge :: Int -> Either String Int
checkAge a
  | a < 0     = Left ("negative age: " ++ show a)
  | otherwise = Right a

traverse checkAge [30, 41, 25]    -- Right [30,41,25]
traverse checkAge [30, -2, -9]    -- Left "negative age: -2"

You get the list of valid values on success, or the first error otherwise. The pattern appears everywhere: parse every line of a file, look up every key in a map, validate every row of a form.

JS traverse for Maybe and Either

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Laws and a warning

Traversable has laws too (identity, composition, naturality), but they boil down to: traversing must not change the container's shape or lose elements. That is why you can derive instances (DeriveTraversable) for ordinary containers and trust the result.

foldr, sum and friends work on infinite structures only if the combining function is lazy enough, and traverse on an infinite list in Maybe or Either can run forever if every element succeeds. Also note that length on a pair is 1, not 2: a pair is a container of its second component. These quirks are legal, but they surprise newcomers, so write list-specific signatures when you mean lists.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the result of sum (Just 5)?

    Maybe is Foldable with zero or one element. Summing a Just 5 gives plain 5, and Nothing would give 0.
  2. 2. What does traverse do with a function a -> Maybe b over a list?

    traverse flips the layers: you get one Maybe wrapped around the list, which is Nothing as soon as any step fails.
  3. 3. What is sequenceA [Just 1, Just 2]?

    sequenceA turns a list of Maybes into a Maybe of a list, succeeding only if all are Just.
  4. 4. Which function is the best fit when you only care about effects and discard results?

    mapM_ and traverse_ run the effects and ignore the produced values.
  5. 5. What must you define to make a type Foldable (minimal)?

    Either foldMap or foldr is enough; GHC derives sum, length, elem, maximum and the rest.

Summary

  • Foldable gives foldr, foldMap, sum, length, elem, toList for lists, Maybe, trees, maps and more.
  • Define foldMap (or foldr) once and the rest comes free.
  • Traversable adds traverse, which runs a -> f b over a container and returns f (t b).
  • sequenceA flips t (f a) into f (t a); mapM is traverse for monads.
  • With Maybe or Either, traverse validates a whole list and fails on the first bad element.

Next: State, Reader, Writer and Monad Transformers.