On Tue, Oct 23, 2012 at 10:36 AM, Alfredo Di Napoli wrote:

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"?

I hope to have been clearer, don't know if I'm missing something crucial, though :)

Sorry I misunderstood your first post. The answer is that Haskell doesn't have oracular powers so it doesn't know to choose Sum if you pass (+) and Product if you pass (*), it especially doesn't have one kind of monoid for each possible operation you can pass to foldr... So it proceeds otherwise. It's pretty obvious that foldr can be implemented with foldMap, if only by using the list monoid then using the list foldr but the actual default implementation does it more efficiently and more directly instead, you should probably look at the source ( http://www.haskell.org/ghc/docs/latest/html/libraries/base-4.6.0.0/src/Data-... ) then investigate the endomorphism monoid. -- Jedaï