Defining a functor instance for this datatype

Question

I'm attempting to define a functor instance for datatype Terms, which looks like:

data Terms a = Var a | App (Terms a) (Terms a) | Abs (Terms (Maybe a)) 
                     | Const Integer | Add (Terms a) (Terms a) 
                     | IfZero (Terms a) (Terms a) (Terms a) | Y
deriving (Show,Eq)

However, I'm having trouble with the case for Abs.

My definition currently looks like this:

instance Functor Terms where
    fmap f (Var x) = Var (f x)
    fmap f (App t1 t2) = App (fmap f t1) (fmap f t2)
    fmap f (Abs t) = Abs (fmap f t)
    fmap f (Const n) = Const n
    fmap f (Add t1 t2) = Add (fmap f t1) (fmap f t2)
    fmap f (IfZero t1 t2 t3) = IfZero (fmap f t1) (fmap f t2) (fmap f t3)
    fmap f Y = Y

I've tried several different things to get around the Maybe in order to apply the function to the term, but there's just something I'm not quite getting. I know the Maybe type is a functor on its own which means that fmap should work on it automatically, I'm just not sure how to work around the fact that it can't return as a Maybe.

Answer 1

The error comes from this line:

fmap f (Abs t) = Abs (fmap f t)

Abs contains a Maybe (Term a), and you want to get a Maybe (Term b), but f is of type a -> b. So, when you try to fmap it, you're passing a Term a to a function that takes in a. Clearly this doesn't work. Instead, make a Term a -> Term b with fmap f, then fmap that (creating a double fmap):

fmap f (Abs t) = Abs (fmap (fmap f) t)