[Haskell-cafe] A clarification about what happens under the hood with foldMap
chaddai.fouche at gmail.com
Tue Oct 23 15:26:35 CEST 2012
On Tue, Oct 23, 2012 at 10:36 AM, Alfredo Di Napoli
<alfredo.dinapoli at gmail.com> 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-18.104.22.168/src/Data-Foldable.html
) then investigate the endomorphism monoid.
More information about the Haskell-Cafe