Thanks guys for the clarification, this blowed my mind a bit :P<div>As far as I understood, is that my initial thought about Sum and Product was wrong; in fact, they don&#39;t even participate to the party!</div><div>This is confirmed by the Oleg&#39;s paradox about (-).</div>
<div>What really happens is that Endo (which I guess is the endofunctor, so a functor from X to X itself) act as a &quot;semantic bridge&quot;</div><div>between the operation to perform (+,* or whatever) and our foldable structure.</div>
<div>Have I got the gist?</div><div><br></div><div>Thanks a lot!</div><div>A.<br><br><div class="gmail_quote">On 24 October 2012 02:22, John Lato <span dir="ltr">&lt;<a href="mailto:jwlato@gmail.com" target="_blank">jwlato@gmail.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">&gt; From: Alfredo Di Napoli &lt;<a href="mailto:alfredo.dinapoli@gmail.com">alfredo.dinapoli@gmail.com</a>&gt;<br>

</div>&gt; Subject: [Haskell-cafe] A clarification about what happens under the<br>
&gt;         hood    with foldMap<br>
&gt;<br>
<div class="im">&gt; I&#39;m sure I&#39;m missing a point, but the &quot;minimum&quot; definition for a Foldable<br>
&gt; instance is given in terms of foldMap, so I get the cake for free, foldr<br>
&gt; included, right?<br>
&gt; In the example I have defined my treeSum as:<br>
&gt;<br>
&gt; treeSum = Data.Foldable.foldr (+) 0<br>
&gt;<br>
&gt; So the only thing Haskell knows it that I want to fold over a Foldable for<br>
&gt; which foldMap (and therefore foldr) is defined, and specifically I want to<br>
&gt; fold using (+) as function.<br>
&gt; But foldMap is defined in terms of f, which in this case is Sum, because I<br>
&gt; want to sum things. It it were (*) f would have been Product, right?<br>
&gt;<br>
&gt; So what I&#39;m missing is the relation between foldMap and foldr, aka &quot;How<br>
&gt; Haskell infer from (+) that I want f = Sum and not something different&quot;?<br>
<br>
</div>What you&#39;re missing is that this isn&#39;t how foldr is defined.  As you<br>
probably suspect, it isn&#39;t possible for Haskell to deduce &quot;f = Sum&quot;<br>
from just the function.  And in general the function parameter to<br>
foldr isn&#39;t even equivalent to mappend for any monoid, because it<br>
operates on two values with different types.  Rather, foldr is defined<br>
using the Endo monoid, which is<br>
<br>
&gt; newtype Endo a = Endo (a -&gt; a)<br>
<br>
instance Monoid (Endo a) where<br>
    mempty = id<br>
    mappend = (.)<br>
<br>
Here&#39;s the default instance of Data.Foldable.foldr<br>
<br>
&gt; foldr :: (a -&gt; b -&gt; b) -&gt; b -&gt; t a -&gt; b<br>
&gt; foldr f z t = appEndo (foldMap (Endo . f) t) z<br>
<br>
What happens is that, as the tree is traversed, Leaf constructors are<br>
replaced with &#39;id&#39; (mempty :: Endo b), and branch values are replaced<br>
with &#39;Endo . f&#39;, where f = (+) in this example.  Look at Endo . f:<br>
<br>
-- Endo :: (b -&gt; b) -&gt; Endo b<br>
-- f :: a -&gt; (b -&gt; b)<br>
-- Endo . f :: a -&gt; Endo b<br>
<br>
so at each branch (Endo . f) is applied to the value, resulting in the<br>
type &#39;Endo b&#39;<br>
<br>
foldMap just composes everything together with mappend, which, after<br>
the Endo constructor is removed, is a giant function pipeline :: b -&gt;<br>
b, which is then applied to the provided base value (0 here).<br>
<br>
John L.<br>
</blockquote></div><br></div>