[Haskell-beginners] Functor on Tree data constructor

[Frerich Raabe]

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