What does Traversable is to Applicative contexts mean?

Question

I am trying to understand Traversable with the help of https://namc.in/2018-02-05-foldables-traversals.

Somewhere the author mentioned the following sentence:

Traversable is to Applicative contexts what Foldable is to Monoid values.

What did he try to clarify?

I do not get the connection between Foldable to Monoid.

Please provide an example.

Answer 1

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.