Thanks guys for the clarification, this blowed my mind a bit :P As far as I understood, is that my initial thought about Sum and Product was wrong; in fact, they don't even participate to the party! This is confirmed by the Oleg's paradox about (-). What really happens is that Endo (which I guess is the endofunctor, so a functor from X to X itself) act as a "semantic bridge" between the operation to perform (+,* or whatever) and our foldable structure. Have I got the gist? Thanks a lot! A. On 24 October 2012 02:22, John Lato wrote:

...

From: Alfredo Di Napoli 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.