CODEWITHSUNDEEP
haskellfunctional-programmingmonoids
Paul K
Paul K

Reputation: 77

Foldable and Trees

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?

Upvotes: 0

Views: 434

Answers (1)

Twan van Laarhoven
Twan van Laarhoven

Reputation: 2602

(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)

Upvotes: 7

Related Questions