How to write the <*> when writing the Applicative instance for Reader r

Question

I'm stuck with an exercise in Haskell Book, "Chapter 22. Reader". The exercise says "Implement the Applicative for Reader" and it gives the following:

{-# LANGUAGE InstanceSigs #-}

newtype Reader r a =
  Reader { runReader :: r -> a }

instance Applicative (Reader r) where 
  pure :: a -> Reader r a
  pure a = Reader $ ???

  (<*>) :: Reader r (a -> b) -> Reader r a -> Reader r b
  (Reader rab) <*> (Reader ra) = Reader $ \r -> ???

I was able to write the pure after also writing a Functor instance (I wrote the Functor instance, because otherwise GHC was complaining "No instance for (Functor (Reader r)) … arising from the superclasses of an instance declaration In the instance declaration for ‘Applicative (Reader r)’"):

{-# LANGUAGE InstanceSigs #-}

newtype Reader r a =
  Reader { runReader :: r -> a }

instance Functor (Reader r) where
  fmap f (Reader x) = Reader (f . x)

instance Applicative (Reader r) where
  pure :: a -> Reader r a
  pure a = Reader $ \_ -> a

  (<*>) :: Reader r (a -> b) -> Reader r a -> Reader r b
  (Reader rab) <*> (Reader ra) = Reader $ \r -> ???

But I'm stuck with the ??? part.

The book gives the following hint:

We got the definition of the apply function started for you, we’ll describe what you need to do and you write the code. If you unpack the type of Reader’s apply 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’s the difference? The difference is that apply, unlike fmap, also takes an argument of type r.

Make it so.

Yes, but how to make it so? Using typed holes, the compiler tells me that the type of ??? must be b. But I still can't see how I can construct a lambda expression that takes an r and returns something of type b, given rab and ra.

Can you also provide the definition of the Reader data type, for those of us who are not going to buy that book? — user824425
@Rhymoid This is a little harsh. What Reader is is common knowledge, after all. — duplode
Sorry for the missing Reader type, I've added it to the question above. — Emre Sevinç

Benjamin Hodgson Benjamin Hodgson · Accepted Answer · 2016-10-15T14:32:26

Let's play type tennis. Looking at the pieces you have in scope,

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

and the goal type of b, you can see that the only way you can get a b out is by applying rab to two arguments.

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

Now, the first hole has a type of r, and you only have one r in scope.

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

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

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

and ra's argument must be an r, for which once again you have only one choice.

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

Notice that rab and ra both receive r as an argument. All the steps in a composed Reader computation have access to the same environment.

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

How to write the <*> when writing the Applicative instance for Reader r

1 Answers