[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
More information about the Beginners
mailing list