[Haskell-cafe] A clarification about what happens under the hood with foldMap

[John Lato]

> From: Alfredo Di Napoli <alfredo.dinapoli at gmail.com>
> Subject: [Haskell-cafe] A clarification about what happens under the
>         hood    with foldMap
>
> I'm sure I'm missing a point, but the "minimum" definition for a Foldable
> instance is given in terms of foldMap, so I get the cake for free, foldr
> included, right?
> In the example I have defined my treeSum as:
>
> treeSum = Data.Foldable.foldr (+) 0
>
> So the only thing Haskell knows it that I want to fold over a Foldable for
> which foldMap (and therefore foldr) is defined, and specifically I want to
> fold using (+) as function.
> But foldMap is defined in terms of f, which in this case is Sum, because I
> want to sum things. It it were (*) f would have been Product, right?
>
> So what I'm missing is the relation between foldMap and foldr, aka "How
> Haskell infer from (+) that I want f = Sum and not something different"?

What you're missing is that this isn't how foldr is defined.  As you
probably suspect, it isn't possible for Haskell to deduce "f = Sum"
from just the function.  And in general the function parameter to
foldr isn't even equivalent to mappend for any monoid, because it
operates on two values with different types.  Rather, foldr is defined
using the Endo monoid, which is

> newtype Endo a = Endo (a -> a)

instance Monoid (Endo a) where
    mempty = id
    mappend = (.)

Here's the default instance of Data.Foldable.foldr

> foldr :: (a -> b -> b) -> b -> t a -> b
> foldr f z t = appEndo (foldMap (Endo . f) t) z

What happens is that, as the tree is traversed, Leaf constructors are
replaced with 'id' (mempty :: Endo b), and branch values are replaced
with 'Endo . f', where f = (+) in this example.  Look at Endo . f:

-- Endo :: (b -> b) -> Endo b
-- f :: a -> (b -> b)
-- Endo . f :: a -> Endo b

so at each branch (Endo . f) is applied to the value, resulting in the
type 'Endo b'

foldMap just composes everything together with mappend, which, after
the Endo constructor is removed, is a giant function pipeline :: b ->
b, which is then applied to the provided base value (0 here).

John L.