How to make instance of Applicative a certain data type

Question

I'm reading Graham Hutton book on Haskell, and don't no how to proceed in one part of an excercise. The excercise says as follows:

Given the following type expressions

data Expr a = Var a | Val Int | Add (Expr a) (Expr a) deriving Show

that contain variables of some type a, show how to make this type into instances of Functor, Applicative and Monad classes. With the aid of an example, explain what the >>= operator for this type does.

---

I have had problems defining the <*> operator of Applicative. The type of <*> is:

(<*>) :: Expr (a -> b) -> Expr a -> Expr b

I don't understand how (Val n) <*> mx might work, because theoretically I need to provide a Expr b, but all I have is a Expr a and no function to convert (a -> b).

I also don't understand what to do in the (Add l r) <*> mx case.

---

This is my implementation.

instance Functor Expr where
    --fmap :: (a -> b) -> Expr a -> Expr b
    fmap g (Var x) = Var (g x)
    fmap g (Val n) = Val n
    fmap g (Add l r) = Add (fmap g l) (fmap g r)


instance Applicative Expr where
    --pure :: a -> Expr a
    pure = Var

    -- <*> :: Expr (a -> b) -> Expr a -> Expr b
    (Var g) <*> mx = fmap g mx
    --(Val n) <*> mx = ???
    --(Add l r) <*> mx = ???

instance Monad Expr where
    -- (>>=) :: Expr a -> (a -> Expr b) -> Expr b
    (Var x) >>= g = g x
    (Val n) >>= g = Val n
    (Add l r) >>= g = Add (l >>= g) (r >>= g)


expr = Add (Add (Var 'a') (Val 4)) (Var 'b')

Finally, I have a doubt with respect to the >>= in the monad. The idea of this operator is to do things like substituting variables? Like:

expr >>= (\x -> if x == 'a' then Val 6 else Var x) >>= (\x -> if x == 'b' then Val 7 else Var x)

Answer 1

As you correctly note, in the case:

(Val n) <*> mx = ???

you have:

Val n :: Expr (a -> b)
mx :: Expr a

and you need to produce an Expr b. Do you recall the case:

fmap g (Val n) = ???

when you had:

g :: a -> b
Val n :: Expr a

and you needed to produce an Expr b? You found a solution there.

For the case:

(Add l r) <*> mx

you have:

l :: Expr (a -> b)
r :: Expr (a -> b)
mx :: Expr a

and you need to produce an Expr b. If only you had some function that could take l and mx and create an Expr b. Such a function, if it existed, would probably have signature:

someFunc :: Expr (a -> b) -> Expr a -> Expr b

Of course, with someFunc l mx and someFunc r mx, both of type Expr b, it would be a shame to only use one. If there was some way of constructing an Expr b from two Expr b parts, that would really be the bees' knees.

Answer 2

When you have defined pure and (>>=), one possible definition of (<*>) is

(<*>) = Control.Monad.ap

where ap is defined in the standard library as

ap :: Monad m => m (a -> b) -> m a -> m b
ap mf mx = do
  f <- mf
  x <- mx
  pure (f x)

In fact any definition of (<*>) must be equivalent to that if there is a Monad instance.

Answer 3

You've slightly mis-stated what types you have available in the Val n case. You don't have an Expr a, but rather an Expr (a -> b), and no a or b at all (nor even a function from a -> b, because Val contains only an Int). In fact, this case is easy precisely because you have no useful values around: the only reasonable thing you could possibly do is produce an output using the constructor Val, because you have no way to fabricate a b from thin air. The type of Val can specialize to Val :: Int -> Expr b, and happily, you have an Int lying around, so you can write:

(Val n) <*> mx = Val n