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.
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 sequenceA
s 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 traverse
s 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
Functor
ConstraintThe 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
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.
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"