I am reading the book Programming in Haskell by Graham Hutton.
I have a question regarding Exercise 12.7. The task is to show how to make the type
data Expr a = Var a | Val Int | Add (Expr a) (Expr a)
into an instance of the Functor and Applicative classes.
Making it into an instance of Functor is straightforward:
instance Functor Expr where
--fmap :: (a -> b) -> Expr a -> Expr b
fmap f (Var x) = Var $ f x
fmap f (Val i) = Val i
fmap f (Add e e') = Add (fmap f e) (fmap f e')
However, I am not sure how to implement the <*>operator, in particular it is not clear to me how to define it when one or both of its inputs have the constructor Val:
instance Applicative Expr where
--pure :: a -> Expr a
pure x = Var x
--(<*>) :: Expr (a -> b) -> Expr a -> Expr b
(Var f) <*> (Var x) = Var (f x)
(Var f) <*> (Add e1 e2) = Add (fmap f e1) (fmap f e2)
(Add fe1 fe2) <*> e = Add (fe1 <*> e) (fe2 <*> e)
_ <*> _ = ???
My question is: How can I finish my implementation of <*> such that the applicative laws hold?
I will only give you a hint.
To define t1 <*> t2, scan the expression tree t1 and find the places where there are variables, i.e. Var f for some function f. Replace each variable in t1 with the new expression tree fmap f t2. Leave non-variables in t1 as they are.
You don't need to scan t2 in your <*> (except implicitly, through fmap).
Note that this respects types. We have t1 :: Expr (a -> b), hence f :: a -> b. Moreover, t2 :: Expr a, hence fmap f t2 :: Expr b as wanted.
Informal example:
(f + (4 + g)) <*> ((1+x)+y) = ( ((1+f x)+f y) + (4 + ((1+g x)+g y)) )
Once you complete your definition, you can then try proving the applicative laws.
As a final remark, this is a case where, in my opinion, it is easier to think of Expr as a monad first. This is because I find join :: Expr (Expr a) -> Expr a very natural to define, much more than <*>. And once you understand join it's relatively easier to obtain <*>, at least to me.