Class of data structures that can be traversed from left to right, performing an action on each element.

Traversable functors can be thought of as polymorphic containers that support mapping of applicative (or monadic) effects over the container (element-wise) to create a new container of the same shape, with the effects sequenced in a natural order for the container type in question.

The Functor base class means that the container cannot impose any constraints on the element type, so containers that require elements to be comparable, or hashable, etc., cannot be instances of the Traversable class.

For an Applicative functor f and a Traversable functor t, the type signatures of traverse and fmap are rather similar:

fmap     :: (a -> f b) -> t a -> t (f b)
traverse :: (a -> f b) -> t a -> f (t b)

with one crucial difference: fmap produces a container of effects, while traverse produces an aggregate container-valued effect. For example, when f is the IO monad, and t is the List functor, while fmap returns a list of pending IO actions traverse returns an IO action that evaluates to a list of the return values of the individual actions performed left-to-right.

More concretely, if nameAndLineCount counts the number of lines in a file, returning a pair with input filename and the line count, then traversal over a list of file names produces an IO action that evaluates to a list of (fileName, lineCount) pairs:

>>> nameAndLineCount :: FilePath -> IO (FilePath, Int)
>>> nameAndLineCount fn = ...
>>> traverse nameAndLineCount ["/etc/passwd","/etc/hosts"]
[("/etc/passwd",56),("/etc/hosts",32)]

The specialisation of traverse to the case when f is a monad is called mapM. The two are otherwise generally identical:

traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)
mapM     :: (Monad       m, Traversable t) => (a -> m b) -> t a -> m (t b)

The behaviour of traverse and mapM can be at first surprising when the applicative functor f is [] (i.e. the List monad). The List monad is said to be non-deterministic, by which is meant that applying a list of n functions [a -> b] to a list of k values [a] produces a list of n*k values of each function applied to each input value.

As a result, traversal with a function f :: a -> [b], over an input container t a, yields a list [t b], whose length is the product of the lengths of the lists that the function returns for each element of the input container! The individual elements a of the container are replaced by each element of f a in turn:

>>> mapM (\n -> [0..n]) $ Just 2
[Just 0, Just 1, Just 2]
>>> mapM (\n -> [0..n]) [0..2]
[[0,0,0],[0,0,1],[0,0,2],[0,1,0],[0,1,1],[0,1,2]]

If any element of the container is mapped to an empty list, then the aggregate result is empty (no value is available to fill one of the slots of the output container).

>>> traverse (const []) $ Just 0
[]

When however the traversed container is empty, the result is always a singleton of the empty container, the function is never evaluated as there are no input values for it to be applied to.

>>> traverse (const []) Nothing
[Nothing]

The result of traverse is all-or-nothing, either containers of exactly the same shape as the input or a failure (Nothing, Left, empty list, etc.). The traverse function does not perform selective filtering as with e.g. mapMaybe:

>>> let incOdd n = if odd n then Just $ n + 1 else Nothing
>>> traverse incOdd [1, 2, 3]
Nothing
>>> mapMaybe incOdd [1, 2, 3]
[2,4]

A hypothetical application of the above is to validate a structure:

>>> validate :: Int -> Either (String, Int) Int
>>> validate i = if odd i then Left ("That's odd", i) else Right i
>>> traverse validate [2,4,6,8,10]
Right [2,4,6,8,10]
>>> traverse validate [2,4,6,8,9]
Left ("That's odd",9)

>>> -- Since 'Nothing' is an empty structure, none of its elements are odd.
>>> traverse validate Nothing
Right Nothing
>>> traverse validate (Just 42)
Right (Just 42)
>>> traverse validate (Just 17)
Left ("That's odd",17)

However, this is not terribly efficient, because we pay the cost of reconstructing the entire structure as a side effect of validation. It is generally cheaper to just check all the elements and then use the original structure if it is valid. This can be done via the methods of the Foldable superclass, which perform only the side effects without generating a new structure:

>>> traverse_ validate [2,4,6,8,10]
Right ()
>>> traverse_ validate [2,4,6,8,9]
Left ("That's odd",9)

The Foldable instance should be defined in a manner that avoids construction of an unnecesary copy of the container.

The Foldable method mapM_ and its flipped version forM_ can be used to sequence IO actions over all the elements of a Traversable container (just for their side-effects, ignoring any results) . One special case is a Maybe container that optionally holds a value. Given:

action :: a -> IO ()
mvalue :: Maybe a

if you want to evaluate the action in the Just case, and do nothing otherwise, you can write the more concise and more general:

mapM_ action mvalue

rather than

maybe (return ()) action mvalue

The mapM_ form works verbatim if the type of mvalue is later refactored from Maybe a to Either e a (assuming it remains OK to silently do nothing in the error case).

There's even a generic way to handle empty values (Nothing, Left, etc.):

case traverse_ (const Nothing) mvalue of
    Nothing -> mapM_ action mvalue -- mvalue is non-empty
    Just () -> ... handle empty mvalue ...

The sequenceA and sequence methods are useful when what you have is a container of applicative or, respectively, monadic actions, and you want to evaluate them left-to-right to obtain a container of the computed values.

sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)
sequence  :: (Monad       m, Traversable t) => t (m a) -> m (t a)
sequenceA = traverse id
sequence  = mapM id

When the monad m is IO, applying sequence to a list of IO actions, performs each in turn, returning a list of the results:

sequence [putStr "Hello ", putStrLn "World!"]
    = (\a b -> [a,b]) <$> putStr "Hello " <*> putStrLn "World!"
    = do u1 <- putStr "Hello "
         u2 <- putStrLn "World!"
         return (u1, u2)

For sequenceA, the non-deterministic behaviour of List is most easily seen in the case of a list of lists (of elements of some common fixed type). The result is a cross-product of all the sublists:

>>> sequenceA [[0, 1, 2], [30, 40], [500]]
[[0,30,500],[0,40,500],[1,30,500],[1,40,500],[2,30,500],[2,40,500]]

When the monad m is Maybe or Either, the effect in question is to short-circuit the computation on encountering Nothing or Left.

>>> sequence [Just 1,Just 2,Just 3]
Just [1,2,3]
>>> sequence [Just 1,Nothing,Just 3]
Nothing
>>> sequence [Right 1,Right 2,Right 3]
Right [1,2,3]
>>> sequence [Right 1,Left "sorry",Right 3]
Left "sorry"

The result of sequence is all-or-nothing, either containers of exactly the same shape as the input or a failure (Nothing, Left, empty list, etc.). The sequence function does not perform selective filtering as with e.g. catMaybes or rights:

>>> catMaybes [Just 1,Nothing,Just 3]
[1,3]
>>> rights [Right 1,Left "sorry",Right 3]
[1,3]

Instances are similar to Functor, e.g. given a data type

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

a suitable instance would be

instance Traversable Tree where
   traverse f Empty = pure Empty
   traverse f (Leaf x) = Leaf <$> f x
   traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

This definition works for any applicative functor in the co-domain of f, as the laws for <*> imply a form of associativity.

How do Traversable functors manage to construct a new container of the same shape by sequencing effects over their elements? Well, left-to-right traversal with sequencing of effects suggests induction from a base case, so the first question is what is the base case? A Traversable container with elements of type a generally has some minimal form that is either "empty" or has just a single element (think Data.List vs. Data.List.Nonempty).

• If the base case is empty (no associated first value of a) then traversal just reproduces the empty structure with no side effects, so we have:

  traverse _ empty = pure empty

  With the List monad, "empty" is [], while with Maybe it is Nothing. With Either e a we have an empty case for each value of e.

• If the base case is a singleton a, then traverse can take that a, apply f :: a -> F b getting an F b, then fmap singleton over that, getting F (singleton b):

  traverse f (singleton a) = singleton <$> f a

Since Maybe and Either are either empty or singletons, we have

traverse _ Nothing = pure Nothing
traverse f (Just a) = Just <$> f a

traverse _ (Left e) = pure (Left e)
traverse f (Right a) = Right <$> f a

Similarly, for List, we have:

traverse f [] = pure []
traverse f [a] = fmap (:[]) (f a) = (:) <$> f a <*> pure []

What remains to be done is an inductive step beyond the empty and singleton cases. For a concrete Traversable functor T we need to be able to extend our structure incrementally by filling in holes. We can view a partially built structure t0 :: T a as a function append :: a -> T a that takes one more element a to insert into the container to the right of the existing elements to produce a larger structure. Conversely, we can view an element a as a function prepend :: T a -> T a of a partially built structure that inserts the element to the left of the existing elements.

Assuming that traverse has already been defined on the partially built structure:

f0 = traverse f t0 :: F (T b)

we aim to define traverse f (append t0 a) and/or traverse f (prepend a t0).

We can lift append and apply it to f0 to get:

append <$> f0 :: F (b -> T b)

and from the next element a we can obtain f a :: F b, and this is where we'll make use of the applicative instance of F. Adding one more element on the right is then:

traverse f (append t0 a) = append <$> traverse f t0 <*> f a

while prepending an element on the left is:

traverse f (prepend a t0) = prepend <$> f a <*> traverse f t0

The (binary) Tree instance example makes use of both, after defining the Empty base case and the singleton Leaf node case, non-empty internal nodes introduce both a prepended child node on the left and an appended child node on the right:

traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

The above definitions sequence the Applicative effects of F in the expected order while producing results of the expected shape T.

For lists we get the natural order of effects by using (prepend <$> f a) as the operator and (traverse f as) as the operand (the actual definition is written as an equivalent right fold in order to enable fusion rules):

traverse f [] = pure []
traverse f (a:as) = (:) <$> f a <*> traverse f as

The origin of the combinatorial product when F is [] should now be apparent, the non-deterministic definition of <*> for List makes multiple independent choices for each element of the structure.

A definition of traverse must satisfy the following laws:

Naturality

t . traverse f = traverse (t . f) for every applicative transformation t

Identity

traverse Identity = Identity

Composition

traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

A definition of sequenceA must satisfy the following laws:

Naturality

t . sequenceA = sequenceA . fmap t for every applicative transformation t

Identity

sequenceA . fmap Identity = Identity

Composition

sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA

where an applicative transformation is a function

t :: (Applicative f, Applicative g) => f a -> g a

preserving the Applicative operations, i.e.

t (pure x) = pure x
t (f <*> x) = t f <*> t x

and the identity functor Identity and composition functors Compose are from Data.Functor.Identity and Data.Functor.Compose.

A result of the naturality law is a purity law for traverse

traverse pure = pure

(The naturality law is implied by parametricity and thus so is the purity law [1, p15].)

The superclass instances should satisfy the following:

• In the Functor instance, fmap should be equivalent to traversal with the identity applicative functor (fmapDefault).
• In the Foldable instance, foldMap should be equivalent to traversal with a constant applicative functor (foldMapDefault).

• [1] "The Essence of the Iterator Pattern", by Jeremy Gibbons and Bruno Oliveira, in Mathematically-Structured Functional Programming, 2006, online at http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/#iterator.
• "Applicative Programming with Effects", by Conor McBride and Ross Paterson, Journal of Functional Programming 18:1 (2008) 1-13, online at http://www.soi.city.ac.uk/~ross/papers/Applicative.html.
• "An Investigation of the Laws of Traversals", by Mauro Jaskelioff and Ondrej Rypacek, in Mathematically-Structured Functional Programming, 2012, online at http://arxiv.org/pdf/1202.2919.