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

Alfredo Di Napoli alfredo.dinapoli at gmail.com
Wed Oct 24 08:19:23 CEST 2012


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 <jwlato at gmail.com> wrote:

> > 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20121024/df6a6076/attachment.htm>


More information about the Haskell-Cafe mailing list