How to write <*> when writing an applicative instance for Reader r

Question

I am stuck in Haskell Book exercise, "Chapter 22. Reader". The exercise says, “Implement a reading application,” and it gives the following:

 {-# LANGUAGE InstanceSigs #-} newtype Reader ra = Reader { runReader :: r -> a } instance Applicative (Reader r) where pure :: a -> Reader ra pure a = Reader $ ??? (<*>) :: Reader r (a -> b) -> Reader ra -> Reader rb (Reader rab) <*> (Reader ra) = Reader $ \r -> ??? 

I was able to write pure after writing the Functor instance (I wrote the Functor instance because otherwise the GHC complained "There is no instance for (Functor (Reader r)) … arising from the superclasses of the instance declaration In the instance declaration for 'Applicative (Reader r)' "):

 {-# LANGUAGE InstanceSigs #-} newtype Reader ra = Reader { runReader :: r -> a } instance Functor (Reader r) where fmap f (Reader x) = Reader (f . x) instance Applicative (Reader r) where pure :: a -> Reader ra pure a = Reader $ \_ -> a (<*>) :: Reader r (a -> b) -> Reader ra -> Reader rb (Reader rab) <*> (Reader ra) = Reader $ \r -> ??? 

But am I stuck with part ??? .

The book gives the following clue:

We got a definition of the function of the application launched for you, to describe well what you need to do, and write code. If you unzip the type of readers above, you get the following.

 <*> :: (r -> a -> b) -> (r -> a) -> (r -> b) -- contrast this with the type of fmap fmap :: (a -> b) -> (r -> a) -> (r -> b) 

So what is the difference? The difference is that apply , unlike fmap , also takes an argument of type r .

Do it like that.

Yes, but how to do it? Using typed holes, the compiler tells me what type ??? must be b . But I still can't figure out how I can build a lambda expression that takes r and returns something like b given by rab and ra .

Answer 1

Looking at the parts that you have,

 rab :: r -> (a -> b) ra :: r -> a r :: r 

and target type b , you can see that the only way to get output b is to apply rab to two arguments.

 Reader rab <*> Reader ra = Reader $ \r -> rab _ _ 

Now the first hole is of type r , and you have only one r in the region.

 Reader rab <*> Reader ra = Reader $ \r -> rab r _ 

The remaining hole is of type a . The only a that you have in scope is the return value of ra ,

 Reader rab <*> Reader ra = Reader $ \r -> rab r (ra _) 

Argument

and ra should be r , for which again you have only one choice.

 Reader rab <*> Reader ra = Reader $ \r -> rab r (ra r) 

Note that rab and ra both take r as an argument. All stages of compiled Reader computing have access to the same environment.

By the way, this definition makes <*> equivalent to the famous S combinator (and pure is K ).