Functor on Tree data constructor

Nishant

2 Apr 2014 2 Apr '14

10:53 a.m.

Hi, Can some explain me the error and a possibly a fix : data Tree a = NULL | Node (Tree a) a (Tree a) deriving Show 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) ghci gives: Prelude> :load programs\tree.hs [1 of 1] Compiling Main ( programs\tree.hs, interpreted ) programs\tree.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 programs\tree.hs:31:7 `b' is a rigid type variable bound by the type signature for fmap :: (a -> b) -> Tree a -> Tree b at programs\tree.hs:31:7 Expected type: Tree b Actual type: Tree a In the first argument of `Node', namely `left' In the expression: Node left (f x) right In an equation for `fmap': 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) Failed, modules loaded: none. Regards. Nishant

Attachments:

attachment.html (text/html — 1.9 KB)

Show replies by date

Frerich Raabe

2 Apr 2 Apr

11:07 a.m.

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@froglogic.com www.froglogic.com - Multi-Platform GUI Testing

Gesh

11:37 a.m.

...

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) Note that you can simplify your instance declaration to: instance Functor Tree where fmap f NULL = NULL fmap f (Node left x right) = Node (f' left) (f x) (f' right) where f' x = if x == NULL then NULL else fmap f x Also note that the NULL in the then clause differs from x. Let f :: a -> b, then x :: Tree a and the NULL in that clause :: Tree b. These values are as distinct as 2 :: Int and 2.0 :: Double. HTH, Gesh

Tony Morris

11:42 a.m.

On 03/04/14 00:37, Gesh wrote:

...

...
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) Note that you can simplify your instance declaration to: instance Functor Tree where fmap f NULL = NULL fmap f (Node left x right) = Node (f' left) (f x) (f' right) where f' x = if x == NULL then NULL else fmap f x Also note that the NULL in the then clause differs from x. Let f :: a -> b, then x :: Tree a and the NULL in that clause :: Tree b. These values are as distinct as 2 :: Int and 2.0 :: Double. HTH, Gesh

Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

instance Functor Tree where fmap f NULL = NULL fmap f (Node left x right) = Node (f' left) (f x) (f' right) where f' = fmap f -- Tony Morris http://tmorris.net/

Gesh

12:19 p.m.

On April 2, 2014 2:42:39 PM GMT+03:00, Tony Morris wrote:

...

On 03/04/14 00:37, Gesh wrote:

...
...
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) Note that you can simplify your instance declaration to: instance Functor Tree where fmap f NULL = NULL fmap f (Node left x right) = Node (f' left) (f x) (f' right) where f' x = if x == NULL then NULL else fmap f x Also note that the NULL in the then clause differs from x. Let f :: a -> b, then x :: Tree a and the NULL in that clause :: Tree b. These values are as distinct as 2 :: Int and 2.0 :: Double. HTH, Gesh

Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

instance Functor Tree where fmap f NULL = NULL fmap f (Node left x right) = Node (f' left) (f x) (f' right) where f' = fmap f

Oops. I should have noticed my case analysis was unnecessary. Still, the comments accompanying it are correct. NULL :: Tree a and NULL :: Tree b are distinct values of distinct types, and therefore using one where the other is expected will make GHC disappointed in you. Gesh

Daniel Trstenjak

11:12 a.m.

Hi Nishant,

...

fmap f (Node left x right) | (left == NULL) && (right == NULL) = > Node left (f x) right

The function 'f' maps from 'a -> b' and 'left' and 'right' have the type 'Tree a', by not mapping 'left' and 'right' with 'f', you're telling the compiler that the types 'a' and 'b' are equal, but the compiler doesn't consider these types to be equal. You also have to map 'left' and 'right': instance Functor Tree where fmap f NULL = NULL fmap f (Node left a right) = Node (fmap f left) (f a) (fmap f right) Greetings, Daniel

Vlatko Basic

1:54 p.m.

Nishant

3 Apr 3 Apr

8:50 a.m.

Thanks Vlatko ... That analogy helped ..... I created my own functor typeclass where i defined fmap :: MyFucntor f => (a->a) -> f a ->f a and that worked ... On Wed, Apr 2, 2014 at 7:24 PM, Vlatko Basic wrote:

...

Try to visualize with concrete types

data Tree a = NULL | Node (Tree a) a (Tree a) deriving Show

Tree Int = Node (Tree Int) Int (Node Int) -- OK Tree String = Node (Tree String) String (Node String) -- OK

f :: Int -> String f i = show i

and see what you get:

instance Functor Tree where fmap f NULL = NULL fmap f (Node left x right) -- Node (Tree Int) Int (Node Int) | (left == NULL) && (right == NULL) = Node left (f x) right -- Node (Tree Int) String (Node Int) === Not OK | (left /= NULL) = Node (fmap f left) x right -- Node (Tree String) Int (Node Int) === Not OK | (right /= NULL) = Node left x (fmap f right) -- Node (Tree Int) Int (Node String) === Not OK

-------- Original Message -------- Subject: [Haskell-beginners] Functor on Tree data constructor From: Nishant To: beginners@haskell.org Date: 02.04.2014 12:53

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)

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Nishant

4110

Age (days ago)

4111

Last active (days ago)

List overview

Download

7 comments

6 participants

participants (6)

Daniel Trstenjak
Frerich Raabe
Gesh
Nishant
Tony Morris
Vlatko Basic

Functor on Tree data constructor

tags

participants (6)