Traversable

(Not updated very recently)

A Foldable container t a can be “crunched down” to a b via foldr.

foldr :: (a -> b -> b) -> b -> t a -> b

The entire structure of t a is torn down and thrown away by foldr. A particular instantiation of b could choose to maintain the structure. For example, functions of type

[Maybe a] -> Maybe [a]

and

Tree (Maybe a) -> Maybe (Tree a)

and

[Tree a] -> Tree [a]

might “walk over” the input lists (in the first and third cases) and trees (in the second case) and, when considering what to do with the Maybe values inside, the entire list or tree structure is rebuilt.

Each function type above has the form

T_outer (T_inner a) -> T_inner (T_outer a)

where — rather than describing the crunched value as some type b unrelated to the input T_outer ... — we observe that the outer and inner structures have been “swapped.”

The Traversable class captures this notion, describing types can be “traversed” from left-to-right while preserving the structure. There are two members:

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

We will build up to the library version of Traversable in three steps.

Version 1: No Superclass Constraints

First version:

class Traversable_v1 t where
    sequenceA :: Applicative f => t (f a) -> f (t a)
    traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)

Defining instances follows a pretty boilerplate pattern.

instance Traversable_v1 [] where
 -- sequenceA :: Applicative f => [f a] -> f [a]
    sequenceA []     = pure []
    sequenceA (x:xs) = pure (:) <*> x <*> sequenceA xs

 -- traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
    traverse func []     = pure []
    traverse func (a:as) = pure (:) <*> func a <*> traverse func as

The implementation of sequenceA recursively sequenceAs the subexpressions, and then rebuilds the outer structure inside the Applicative idiom. This might be thought of as “effectful data re-construction.”

The implementation of traverse recursively traverses the subexpressions, maps the values, and then rebuilds the values through the Applicative idiom. This might be thought of as “effectful fmap.”

See how this approach plays out on another example:

instance Traversable_v1 Tree where
 -- sequenceA :: Applicative f => Tree (f a) -> f (Tree a)
    sequenceA Empty        = pure Empty
    sequenceA (Node l a r) = pure Node <*> sequenceA l <*> a <*> sequenceA r

 -- traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
    traverse func Empty        = pure Empty
    traverse func (Node l a r) =
      pure Node <*> traverse func l <*> func a <*> traverse func r

Version 2: Default Definitions and Functor Constraint

The two methods are inter-derivable. The default definition of traverse relies on fmap, so Functor becomes a superclass:

class Functor t => Traversable_v2 t where
    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id

    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse func = sequenceA . fmap func

It’s worth thinking about how the default definition of sequenceA typechecks:

\tfa ->
  let returnValue = traverse id tfa in
  returnValue

We have the following expressions to work with

tfa :: t (f a)
  where Functor t, Traversable_v2 t, and Applicative f

id :: {- forall x. -}
  x -> x

traverse :: {- forall f', a', b'. -}
  Applicative f' => (a' -> f' b') -> t a' -> f' (t b')

and the goal is

returnVal :: f (t a)

Writing explicit type applications reveals a subtlety: that a' type variable of traverse is instantiated with f a:

\tfa ->
  let traverse_ = traverse {- f':=f, a':=(f a), b':=a -} in
  let id_ = id {- x:=a -} in
  let returnValue = traverse_ id_ tfa in
  returnValue

Version 3: Free Instances of Functor and Foldable

Traversable is a generalization of Functor and Foldable. Specifically, traverse can be used to define free instances of Functor and Foldable as follows:

fmapDefault :: Traversable_ t => (a -> b) -> t a -> t b
fmapDefault f ta =
  runIdentity $ traverse (Identity . f) ta

foldMapDefault :: (Traversable_ t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f ta =
  getConst $ traverse (Const . f) ta

The latter uses an Applicative type Const that deals with the Monoid in a suitable way; dig around the library if you’re curious.

To make the relationship between Traversable and Foldable explicit, Foldable is also added as a superclass constraint in the Data.Traversable library.

class (Functor t, Foldable t) => Traversable_ t where
    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id

    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse func = sequenceA . fmap func

Data.Traversable defines fmapDefault and foldMapDefault albeit in somewhat different terms than our versions.

Historical Vestiges

In versions of Haskell before Applicative and Traversable, there were:

sequence :: Monad m => t (m a) -> m (t a)
sequence = ...

mapM :: Monad m => (a -> m b) -> t a -> m (t b)
mapM = ...

With Traversable, these became obsolete but kept around for backwards compatibility:

sequence = sequenceA

mapM = traverse        -- "effectful fmap"

Source Files