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)
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.