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

I implemented it as follows:

{-# LANGUAGE InstanceSigs #-}

instance Functor Expr where
  fmap :: (a -> b) -> Expr a -> Expr b
  fmap _ (Val k) = Val k
  fmap g (Var x) = Var (g x)
  fmap g (Add expr1 expr2) = Add (fmap g expr1) (fmap g expr2)

instance Applicative Expr where
  pure :: a -> Expr a
  pure = Var
  (<*>) :: Expr (a -> b) -> Expr a -> Expr b
  _ <*> Val k = Val k
  eg <*> Var x = fmap (\g -> g x) eg
  eg <*> Add e1 e2 = Add (eg <*> e1) (eg <*> e2)

instance Monad Expr where
  (>>=) :: Expr a -> (a -> Expr b) -> Expr b
  Val k >>= _ = Val k
  Var x >>= g = g x
  Add e1 e2 >>= g = Add (e1 >>= g) (e2 >>= g)

However, I'm not sure how to answer the last part of the question. I suspect there's something missing in the Monad equations. For example, if I define the following function

simplify :: Num a => Expr a -> Expr a
simplify (Val k) = Val k
simplify (Var x) = Var x
simplify (Add expr1 expr2) = do
  x <- simplify expr1
  y <- simplify expr2
  return (x + y)

And try to do the following, for example,

simplify (Add (Add (Var 5) (Val 12)) (Add (Val 10) (Var 8)))

I only get Val 12, which doesn't seem to make sense.

---

Added 2023-06-04:

I wrote Prof. Hutton and he sent me the official solution of this exercise:

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  e = fmap g e
  Val n  e = Val n
  (Add l r)  e = Add (l  e) (r  e)

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)

The >>= operator implements the concept of variable substitution, in which variables are replaced by other expressions. For example:

let e = Add (Val 1) (Var ’x’)  
:type e  
e :: Expr Char  
let g ’x’ = Val 2  
:type g  
g :: Char -> Expr a  
e >>= g  
Add (Val 1) (Val 2)  

Answer 2

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

Answer 3

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 4

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.