Could match expect type when applying functions to a tree structure

enter image description here

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

  • answered 2018-07-11 03:38 Dannyu NDos

    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 of Forky (a -> b) -> Forky (a -> b) -> Forky (a -> b), so f and g must have type of Forky (a -> b). So they cannot be applied to fmap.

    The correct definition of <*> can be:

    Tip f        <*> x = fmap f x
    Branch fs gs <*> x = Branch (fs <*> x) (gs <*> x)
    

  • answered 2018-07-11 03:40 chepner

    In Branch f g, f and g are not functions of type a -> b; they are subtrees of type Forky (a -> b). As such, you need to use <*>, not fmap, 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) = ?