Could match expect type when applying functions to a tree structure
data Forky a = Tip a  Branch (Forky a) (Forky a)
deriving (Eq, Show)
instance Functor Forky where
 fmap :: (a > b) > Forky a > Forky b
fmap f (Tip a) = Tip (f a)
fmap f (Branch left right) = Branch (fmap f left) (fmap f right)
instance Applicative Forky where
 pure :: a > Forky a
pure a = Tip a
 (<*>) :: Forky (a > b) > Forky a > Forky b
(<*>) (Branch f g) (Branch left right) =
Branch ((fmap f (Branch left right)) (fmap g (Branch left right)))
Everything looks good until the last function (<*>)
The error tells
? Couldn't match expected type ‘a > b0’
with actual type ‘Forky (a > b)’
How can I fix it? Thank you!
2 answers

data Forky a = Tip a  Branch (Forky a) (Forky a) deriving (Eq, Show) ... instance Applicative Forky where ...  (<*>) :: Forky (a > b) > Forky a > Forky b (<*>) (Branch f g) (Branch left right) = Branch ((fmap f (Branch left right)) (fmap g (Branch left right)))
Here, during the pattern matching,
Branch
has ofForky (a > b) > Forky (a > b) > Forky (a > b)
, sof
andg
must have type ofForky (a > b)
. So they cannot be applied tofmap
.The correct definition of
<*>
can be:Tip f <*> x = fmap f x Branch fs gs <*> x = Branch (fs <*> x) (gs <*> x)

In
Branch f g
,f
andg
are not functions of typea > b
; they are subtrees of typeForky (a > b)
. As such, you need to use<*>
, notfmap
, to apply them.(Branch fs gs) <*> (Branch left right) = Branch (fs <*> left) (gs <*> right)
Further, you need to consider the case where you have a function in a tip:
(Tip f) <*> (Tip a) = ?
You should also consider what you will do if the two arguments don't have the same shape:
(Tip f) <*> (Branch left right) = ? (Branch fs gs) <*> (Tip a) = ?