Tree as instance of functor and foldable

Question

I am writing a little code for a hw problem which asks us to make a definition of tree an instance of functor and foldable. When I write the code below:

 import Data.Foldable
 import Data.Monoid

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

 instance Functor (Tree) where
    fmap f (Leaf a) = Leaf (f a) 
    fmap f (Node [Tree a]) = fmap f [Tree a]

 instance Foldable (Tree) where
    foldMap f (Leaf a) = f a
    foldMap f (Node [Tree a]) = foldMap f `mappend` [Tree a]

the following error appears:

hw.hs:10:19:
Not in scope: data constructor `Tree'
Perhaps you meant `True' (imported from Prelude)

hw.hs:10:38:
Not in scope: data constructor `Tree'
Perhaps you meant `True' (imported from Prelude)

hw.hs:14:22:
Not in scope: data constructor `Tree'
Perhaps you meant `True' (imported from Prelude)

hw.hs:14:54:
Not in scope: data constructor `Tree'
Perhaps you meant `True' (imported from Prelude)
Failed, modules loaded: none.

Where am I going wrong?

Thanks!

[[Update]]

I have made changes to the code as per the suggestion made in the answer below. Here is a link to the code with the error. It would be great if anyone would take a look at it and tell me where I am wrong.

http://snipt.org/Bahjg5

Thanks again!

Peter Hall Peter Hall · Accepted Answer · 2013-11-14T22:32:28

You can't write this:

fmap f (Node [Tree a]) = ...

because Tree is a data type not a data constructor. In a pattern-match you can only use data constructors, which would be Leaf or Node in this case. Here, you don't even need to match each constructor for the child trees, because you are passing the entire list straight through anyway:

fmap f (Node t) = fmap f t

But actually there is also another error there. The result of fmap still needs to be a Tree so you need to put the result back inside a Node:

fmap f (Node t) = Node (fmap f t)

just like you are already doing with the Leaf case.

You can think of fmap as something that modifies values inside the structure, but without changing the shape of the structure at all. ie. mapping over a list will produce a list of the same length, and mapping over a tree should produce an identical tree, with all the same branches, but with different values in the leaf nodes.

You can think of a fold as something that completely removes the structure, and then finds a way to combine all the values from leaf nodes into a single value. The Type of foldMap helps:

 foldMap :: (Foldable t, Monoid m) => 
         (a -> m) -- mapping function from `a` to the monoid result
      -> t a      -- A tree node containing values of type `a`
      -> m        -- a monoid

The result of foldMap should not be a Tree! It's just the values, transformed with the mapping function and combined using their Monoid instance.

Tree as instance of functor and foldable

1 Answers