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?