Foldable and Trees

Question

I have the following definition of a Tree

 data Tree a = Leaf a
           | Node [Tree a] 
     deriving (Show)

And the following instance of foldable:

 instance Foldable (Tree) where
 foldMap f (Leaf t) = (f t)
 foldMap f (Node t) = (foldMap `mappend` (foldMap f) t)     

This code throws me and error

 Couldn't match type `a' with `Tree a'
  `a' is a rigid type variable bound by
      the type signature for
        foldMap :: Monoid m => (a -> m) -> Tree a -> m
      at trees.hs:8:5
 Expected type: [a]
   Actual type: [Tree a]

How do I make t in the instance declaration of type Tree a instead of a?

Answer 1

(I'll assume that you did indent the code inside the instance declaration, otherwise the compiler would have complained about that.)

The problem is in the line:

 foldMap f (Node t) = (foldMap `mappend` (foldMap f) t)

what is (foldMap `mappend` ...) supposed to do? You are treating foldMap itself as a monadic value. I think what you want to do is just foldMap (foldMap f) t.

By the way, GHC can derive the Foldable instance for you automatically (as well as Functor and Traversable). Just write

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
data Tree a = Leaf a
            | Node [Tree a]
  deriving (Show, Functor, Foldable)