Folding without Monoid instance

Question

I have a simple tree structure:

data Tree a = Leaf | Node a (Tree a) (Tree a)

And a Foldable implementation:

import qualified Data.Foldable as F

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

And it works even though there's no implementation for Monoid and I can't use neither mappend nor mempty in my code. Then how does this Foldable implementation work?

Answer 1

If you examine the type for foldMap

class Foldable f where
  foldMap :: Monoid m => (a -> m) -> f a -> m

You'll see that it has an unbound type m. Generally when this occurs it means that m could be anything, but here it also constrains m with Monoid m. That's there the Monoid comes from.

It's worth noting that if we didn't have the Monoid instance then it's quite hard to define a function that returns a value that "could be anything". If you try it, you'll find it's almost impossible (without "cheating").

impossible :: Int -> b -- no constraints on `b` at all!
impossible i = ...?

But it's quite easy if we know a little bit about the type

veryPossible  :: Num b => Int -> b
veryPossible  i = fromIntegral i
-- or
veryPossible2 i = fromIntegral (i * i) + fromIntegral i

---

As another example, consider the type of the expression

expr m = mconcat [m <> m <> mempty, mempty <> m]

since this expression is built up based on some unknown value m and uses only the functions in the Monoid class or their derivatives, it's type reflects that. The most general type of expr is

expr :: Monoid m => m -> m

Again here, m is a free type variable constrained to be some Monoid.

---

The reason foldMap lets you use Monoid functions is because it explicitly constrains the kinds of things that the m in its type signature can be. By putting constraints there we gain more power to manipulate them.