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

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.