# [Haskell-beginners] Functor on Tree data constructor

Frerich Raabe raabe at froglogic.com
Wed Apr 2 11:07:34 UTC 2014

```On 2014-04-02 12:53, Nishant wrote:
> Can some explain me the error and a possibly  a fix :
>
> data Tree a = NULL | Node (Tree a ) a (Tree a)
>
> instance Functor Tree where
>     fmap f NULL = NULL
>     fmap f (Node left x right) | (left  == NULL) && (right == NULL) =
> Node left (f x) right
>                                | (left  /= NULL) = Node (fmap f left)
> x right
>                                | (right /= NULL) = Node left x (fmap
> f right)

[..]

> programstree.hs:32:78:
> Couldn't match type `a' with `b'
>       `a' is a rigid type variable bound by
>           the type signature for fmap :: (a -> b) -> Tree a -> Tree b
>           at programstree.hs:31:7
>       `b' is a rigid type variable bound by
>           the type signature for fmap :: (a -> b) -> Tree a -> Tree b
>           at programstree.hs:31:7
>     Expected type: Tree b
>       Actual type: Tree a
>     In the first argument of `Node', namely `left'

The issue is that in 'fmap f (Node left x right)', 'left' has type
'Tree a'. Your 'fmap' function should yield a 'Tree b'though, i.e. the
'Node' constructor should take a 'Tree b' as well - and 'left' doesn't
fit.

You can fix this by using 'NULL' directly, e.g.

instance Functor Tree where
fmap f NULL = NULL
fmap f (Node left x right) | (left  == NULL) && (right == NULL) =
Node NULL (f x) NULL
| (left  /= NULL) = Node (fmap f left)
(f x) NULL
| (right /= NULL) = Node NULL (f x)
(fmap f right)

...note that instead of 'x' you also have to use 'f x' (which is also
the whole point of a Functor instance).

--
Frerich Raabe - raabe at froglogic.com
www.froglogic.com - Multi-Platform GUI Testing
```