What does Traversable is to Applicative contexts mean?
In the beginning, there was foldr
:
foldr :: (a -> b -> b) -> b -> [a] -> b
and there was mapM
:
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
foldr
was generalized to data types other than [a]
by letting each type define its own definition of foldr
to describe how to reduce it to a single value.
-- old foldr :: (a -> b -> b) -> b -> [] a -> b
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
If you have a monoid, you don't have to specify a binary function, because the Monoid
instance already provides its own starting value and knows how to combine two values, which is apparent from its default definition in terms of foldr
:
-- If m is a monoid, it provides its own function of type b -> b.
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty
Traverse
does the same kind of generalization from lists to traversable types, but for mapM
:
-- old mapM :: Monad m => (a -> m b) -> [] a -> m ([] b)
traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
(When mapM
was first defined, there was no Applicative
class; if there had been, mapA :: Applicative f => (a -> f b) -> [a] -> f [b]
could have been defined instead; the Monad
constraint was stronger than was necessary.)
An Applicative
is monoidal in nature, so there was no need in Traverse
for the type of distinction that foldr
/foldMap
draws.