Traversables

Recall that the functorial map (fmap) lifts pure functions of the a -> b type to functions on collections of the t a -> t b type. The Traversable type class generalizes this to effectful functions, a -> f b, with f as an applicative functor.

First, let’s compare the two for lists (viewed as a collection, not as an effect):

fmap :: (a -> b) -> ([a] -> [b])
fmap f []     = []
fmap f (x:xs) = f x : fmap f xs
traverse :: Applicative f => (a -> f b) -> ([a] -> f [b])
traverse f []     = pure []
traverse f (x:xs) = pure (:) <*> f x <*> traverse f xs

As we can see, the structure is quite similar. The main difference is that traverse uses the application, (<*>), of applicative functors, and lifts the list constructors with pure.

The Traversable class

The type class declaration looks as follows:

Prelude
class (Functor t, Foldable t) => Traversable t where...