Why is `((,) r)` a Functor that is NOT an Applicative?

Question

From functors that are not applicatives:

A type constructor which is a Functor but not an Applicative. A simple example is a pair:

instance Functor ((,) r) where
    fmap f (x,y) = (x, f y)

But there is no way how to define its Applicative instance without imposing additional restrictions on r. In particular, there is no way how to define pure :: a -> (r, a) for an arbitrary r.

Question 1: Why is this so? Here is how pure could work with functions f of type a -> b:

(pure f) (pure x, pure y) = (pure x, pure f y)

From there, the definition of pure :: a -> (r, a) could depend on what r is. For example, if r is Integer, then you could define

pure x = (0 :: Integer, x)

in your instance declaration. So what is the issue?

Question 2: Can we say in general that if F is a functor, then <*> can always be defined, but pure might not always be defined?

Answer 1

Suppose we have

pure :: forall r a. a -> (r, a)

then, in particular, we have

magic :: forall r. r
magic = fst (pure ())

Now, we can specialise the type variable r to get

magic :: Void

where Void is the datatype with no constructors, which means

magic = undefined

but as type variables (and the types which specialise them) play no run time role, that means magic is always undefined.

We've discovered that ((,) r) can be Applicative only for inhabited r. And there's more. With any such instance, we can write

munge :: r -> r -> r
munge r0 r1 = fst ( pure (\ _ _ -> ()) <*> (r0, ()) <*> (r1, ()) )

to define a binary operator on r. The Applicative laws tell us effectively that munge must be an associative operator that absorbs magic on either side.

That's to say there is a sensible instance

instance Monoid r => Applicative ((,) r) where
  pure a              = (mempty, a)
  (r0, f) <*> (r1, s) = (mappend r0 r1, f s)

(exactly what you get when you take pure=return; (<*>)=ap from the Monad (Writer r)).

Of course, some pedants would argue that it is legal (if unhelpful) to define

instance Monoid r where
  mempty = undefined
  mappend _ _ = undefined
  -- Monoid laws clearly hold

but I would argue that any sensible type class instance should contribute nontrivially to the defined fragment of the language.

Answer 2

Answer 1:

(pure f) (pure x, pure y) = (pure x, pure f y)

I don't understand what you mean by this line. It looks like nonsense: pure f would be a pair, and you can't apply a pair as if it were a function.

From there, the definition of pure :: a -> (r, a) could depend on what r is.

That is exactly the problem. r is fully general; the instance declaration says ((,) r) is a Functor for all types r. That means you have to somehow implement a single pure :: a -> (r, a) that works with any type r that a caller might choose. This is impossible because there is no way to conjure up an arbitrary r from thin air.

Or as your quote says:

In particular, there is no way how to define pure :: a -> (r, a) for an arbitrary r.

If you try to do something like

pure x = (0 :: Integer, x)

you get an error:

Couldn't match expected type ‘r’ with actual type ‘Integer’
  ‘r’ is a rigid type variable bound by
      the instance declaration
      at ...

---

Answer 2:

What would <*> look like for pairs? It would be a function like

(<*>) :: (r, a -> b) -> (r, a) -> (r, b)
(r1, f) (r2, x) = (???, f x)

But what do you do with the ??? part? You have to put a value of r there, and fortunately you have some of those available (r1, r2). The problem is that (for arbitrary r) there is no general way to combine two values, so you have to pick one of them.

That's where you run into trouble with the laws:

pure id <*> v = v

This law says we have to pick r2 to preserve v.

u <*> pure y = pure ($ y) <*> u

Since we have to pick r2 in <*>, the right-hand side of this law says the result will contain the r part of u. But that clashes with the left-hand side, which says that we get whatever r was returned by pure y. (u is a completely arbitrary pair so there's no way a fixed value returned by pure is always going to match it.)

So we have a contradiction, meaning we can't even define <*> for ((,) r). Therefore the answer to your second question is "no".

---

That said, there is a standard Applicative instance for pairs but it requires r to be a Monoid:

instance (Monoid r) => Applicative ((,) r) where
    pure x = (mempty, x)
    (r1, f) (r2, x) = (mappend r1 r2, f x)