I am trying to define instances for Functor,Applicative and Monad for the following type:
data BTree a=Leaf a | Node (BTree a) (BTree a) deriving (Eq,Show)
I have tried implementing the Functor instance like this:
instance Functor BTree where
fmap f (Leaf t) =Leaf (f t)
fmap f (Node a b) =Node (f a) (f b)
What did work
fmap f (Node a b)=Node (fmap f a) (fmap f b)
I understand it is not correct since being an instance of functor , the form has to be preserved f a -> f b (in our case Node).
and in my implementation you would get f a -> b.
What i don't understand:
Why is it an infinite type?
Considering Node (f a )(f b) somewhere down the hierarchy a child Node will be Leafand i will apply f to it.
You are trying to apply f to values of type a (in Leaf (f t)) and to values of type BTree a (in Node (f a) (f b)). For this to work, the type checker needs to find some way to unify a and BTree a, which is only possible if a is an infinitely nested stack of BTree types; adding one more layer of BTree on top of a wouldn't effectively change it.
Changing Node (f a) (f b) to Node (fmap f a) (fmap f b) ensures that f is only applied to values of type a.