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

[oleg at okmij.org]

> I was playing with the classic example of a Foldable structure: Trees.
> So the code you can find both on Haskell Wiki and LYAH is the following:
>
> data Tree a = Empty | Node (Tree a) a (Tree a) deriving (Show, Eq)
>
> instance Foldable Tree where
>     foldMap f Empty = mempty
>     foldMap f (Node l p r) = foldMap f l `mappend` f p `mappend` foldMap f r
>
> treeSum :: Tree Int -> Int
> treeSum = Data.Foldable.foldr (+) 0
>
>
> What this code does is straighforward. I was struck from the following
> sentences in LYAH:
>
> Notice that we didn't have to provide the function that takes a value and
> > returns a monoid value.
> > We receive that function as a parameter to foldMap and all we have to
> > decide is where to apply
> > that function and how to join up the resulting monoids from it.
>
> This is obvious, so in case of (+) f = Sum, so f 3 = Sum 3 which is a
> Monoid.
> What I was wondering about is how Haskell knows that it has to pass, for
> example, Sum in case of (+) and Product in case of (*)?

Hopefully the following paradox helps:

> treeDiff :: Tree Int -> Int
> treeDiff = Data.Foldable.foldr (-) 0
>
> t1 = treeDiff (Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty))

This works just as well. You might be surprised: after all, there is
no Diff monoid that corresponds to (-). In fact, there cannot be since
(-) is not associative. And yet treeDiff type checks and even produces
some integer when applied to a tree. What gives?