Haskell foldable instance for data tree

Question

Trying to make a foldable instance for a data tree with the following code:

data Rose a = a :> [Rose a]
    deriving (Eq, Show)

instance Foldable Rose where
    fold (a:>b) =  a <> (map fold b)

However this code is not working, the error it produces:

Could not deduce <m ~ [m]>
from the context <Monoid m>
  bount by the type signature for fold :: Monoid m => Rose m -> m
...
In the return type of a call of 'map'
...

Does anyone know why/how to make it work?

Answer 1

When you write fold b, you're using the Foldable instance for lists. So the fold folds a list of monoidal values to a single value. The type of this monoidal value happens to be Rose a (that's what your list consists of). But that's probably not what you want.

Try to use foldMap fold instead of fold there. This way you first fold every individual Rose a in the list, and then fold the results together.