foldMap taking the wrong type of parameter?

Question

Here is some examples from Learn You a Haskell:

import qualified Data.Foldable as F

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)  

instance F.Foldable Tree where  
    foldMap f Empty = mempty  
    foldMap f (Node x l r) = F.foldMap f l `mappend`  
                             f x           `mappend`  
                             F.foldMap f r  

testTree = Node 5  
            (Node 3  
                (Node 1 Empty Empty)  
                (Node 6 Empty Empty)  
            )  
            (Node 9  
                (Node 8 Empty Empty)  
                (Node 10 Empty Empty)  
            )  

Testing it:

> let z = F.foldMap (+) testTree
> :t F.foldMap
F.foldMap :: (Monoid m, F.Foldable t) => (a -> m) -> t a -> m
> :t (+)
(+) :: Num a => a -> a -> a
> :t z
z :: (Monoid a, Num a) => a -> a

First param of F.foldable is a function that returns a Monoid, but Num is not a subclass of Monoid, so (+) is surely not qualified here? But from the tests it seems to fit just fine.

And z is kind of mysterious here, it's supposed to be a Monoid, but what is it, concretely?

Answer 1

So let's be clear about what's happening here. We have these two types that we are supposed to unify:

Num a => a -> a -> a
Monoid m => b -> m

This can be done by setting b ~ a and m ~ a -> a, resulting in

(Num a, Monoid (a -> a)) => a -> a -> a

Moreover, there is a monoid instance for functions:

instance Monoid b => Monoid (a -> b) where
    mempty = \_ -> mempty
    mappend f g = \x -> f x `mappend` g x

(Let's set aside why this instance is useful for a moment.) This means that, in fact, to satisfy the Monoid (a -> a) constraint, we need only ensure that the return type -- a -- is a monoid, hence we now arrive at this type for (+):

(Num a, Monoid a) => a -> a -> a

and this type for foldMap (+):

(Monoid a, F.Foldable t) => t a -> a -> a

The behavior of this is to walk over the tree, (partially) applying (+) to each element of the tree, then use mappend to combine all the results. Thus, the small example tree Node 3 (Node 1 Empty Empty) (Node 6 Empty Empty) would result in something like this:

(mempty `mappend` (+) 1 `mappend` mempty) `mappend`
(+) 3                                     `mappend`
(mempty `mappend` (+) 6 `mappend` mempty)

For compactness, let's write this as mconcat [(1+), (3+), (6+)], even though that's fudging things a little bit. Running foldMap (+) on your larger example tree would be mconcat [(1+), (3+), (6+), (5+), (8+), (9+), (10+)].

Now, working out what the monoid instance on functions says, we find that mconcat [f,g,h] = \x -> mconcat [f x, g x, h x], and so on with more functions. So foldMap (+) testTree comes out to

\n -> mconcat [1+n, 3+n, 6+n, 5+n, 8+n, 9+n, 10+n]

Probably you were expecting foldMap (+) testTree to come out to something like 1+3+6+5+8+9+10; hopefully you can see the actual outcome dramatically differs from your expectation (and why).

If what we want to do is add up all the elements of a tree, we can actually make this work by accident. We can specifically choose the Sum monoid and pick n to be 0: so, for example

getSum $ foldMap (+) testTree 0
= { by our computations above }
getSum $ (\n -> mconcat [1+n, 3+n, 6+n, 5+n, 8+n, 9+n, 10+n]) 0
= { beta reduction }
getSum $ mconcat [1+0, 3+0, 6+0, 5+0, 8+0, 9+0, 10+0]
= { n+0 = n }
getSum $ mconcat [1, 3, 6, 5, 8, 9, 10]
= { definition of mconcat for Sum }
getSum $ sum [1, 3, 6, 5, 8, 9, 10]
= { playing fast and loose with polymorphic literals }
sum [1, 3, 6, 5, 8, 9, 10]

That's an awfully convoluted way to get the sum of the elements in a tree. But hopefully this explains why what you wrote is not simply a type error; what the meaning of z is; and why it's not important that Num is neither subclass nor superclass of Monoid.

Answer 2

"Num a =>" is a typeclass constraint, which indicates that the parameters and results for (+) must be at least members of the typeclass "Num", but they can be perfectly members of any other typeclass too (in this case, Monoid).

With respect to z, there are a couple of standard types that would satisfy those constraints (being part of Num and Monoid at the same time). These are Sum and Product, defined in Data.Monoid.

To answer your question, a Tree of Sum or Product would pass the type check and work, and so would do any other type that you define as being part of the typeclasses Num and Monoid.