Can one partially apply functor

Question

I am trying to implement fmap for the following type:

data Tree a = Leaf a | Node a (Tree a) (Tree a) | Empty deriving (Eq,Show)

instance Functor Tree where
        fmap _ Empty=Empty
        fmap f (Leaf x)=Leaf (f x)
        fmap f (Node t left right)=Node (f t) left right

I keep getting type mismatch error:

Error

* Couldn't match type `a' with `b'
      `a' is a rigid type variable bound by
        the type signature for:
          fmap :: forall a b. (a -> b) -> Tree a -> Tree b
        at Monad.hs:8:9-12
      `b' is a rigid type variable bound by
        the type signature for:
          fmap :: forall a b. (a -> b) -> Tree a -> Tree b
        at Monad.hs:8:9-12
      Expected type: Tree b
        Actual type: Tree a

Why do i get this error but when i am also applying fmap to the child nodes it compiles without problem:

fmap f (Node t left right) = Node (f t) (fmap f left) (fmap f right)

Does it mean that all a-s within the Tree must somehow become b-s ? and i am only dealing with the non-functor one in the first case ? ^

Answer 1

Does it mean that all a-s within the Tree must somehow become b-s ? and i am only dealing with the non-functor one in the first case ? ^

Yes, that’s right. You’re trying to implement fmap :: (a -> b) -> Tree a -> Tree b, but when you write:

fmap f (Node t left right) = Node (f t) left right

You’re attempting to call Node :: b -> Tree b -> Tree b -> Tree b with arguments f t :: b, left :: Tree a, and right :: Tree a. The only way you have of turning a Tree a into a Tree b is via fmap f :: Tree a -> Tree b, which is why this:

fmap f (Node t left right) = Node (f t) (fmap f left) (fmap f right)

Works as expected.