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.

Viperish

I can't write a proper answer right now (will do it later if no one else covers it first). In the meantime, I wonder if you'll find the explanation in the beginning of the Wikibook chapter (upon which this article was based on) any clearer. – Amoretto

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.

Amaya

I think you have an extra slash in your first foldr signature. – Xenophobia

Answer 2

The article (and the corresponding passage of the Wikibook) is talking about how the effects (or, to use the language seen there, the contexts) of applicative values can be combined monoidally. The connection with Foldable is that list-like folding ultimately amounts to combining values monoidally (see chepner's answer, and also Foldr/Foldl for free when Tree is implementing Foldable foldmap?). As for the applicative contexts part, there are a few ways to look at that. One of them is noting that, for any Applicative f and Monoid m, f m is a monoid, with pure mempty as mempty and liftA2 mappend as mappend (the Ap type from Data.Monoid witnesses that). For a concrete example, let's pick f ~ Maybe and m ~ (). That leaves us with four possible combinations:

liftA2 mappend (Just ()) (Just ()) = Just ()
liftA2 mappend (Just ()) Nothing   = Nothing
liftA2 mappend Nothing   (Just ()) = Nothing
liftA2 mappend Nothing   Nothing   = Nothing

Now contrast with All, the Bool monoid with (&&) as mappend:

mappend (All True)  (All True)  = All True
mappend (All True)  (All False) = All False
mappend (All False) (All True)  = All False
mappend (All False) (All False) = All False

They match perfectly: Just () corresponds to True, Nothing to False, and liftA2 mappend to (&&).

Now let's have another look at the Wikibook example:

deleteIfNegative :: (Num a, Ord a) => a -> Maybe a
deleteIfNegative x = if x < 0 then Nothing else Just x

rejectWithNegatives :: (Num a, Ord a, Traversable t) => t a -> Maybe (t a)
rejectWithNegatives = traverse deleteIfNegative

ghci> rejectWithNegatives [2,4,8]
Just [2,4,8]
ghci> rejectWithNegatives [2,-4,8]
Nothing

The Maybe values generated by applying deleteIfNegative to the values in the lists are combined monoidally in the way shown above, so that we get a Nothing unless all the Maybe values are Just.

This matter can also be approached in the opposite direction. Through the Applicative instance for Const...

-- I have suppressed a few implementation details from the instance used by GHC.
instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty
    Const x <*> Const y = Const (x `mappend` y)

... we can get an Applicative out of any Monoid, such that (<*>) combines the monoidal values monoidally. That makes it possible to define foldMap and friends in terms of traverse.

On a final note, the category theoretical description of Applicative as a class for monoidal functors involves something rather different from what I have covered here. For further discussion of this issue, and of other fine print, see Monoidal Functor is Applicative but where is the Monoid typeclass in the definition of Applicative? (if you want to dig deeper, it is well worth it to read all of the answers there).

Amoretto