How arbitrary is the "ap" implementation for monads?

Question

I am currently studying the bonds between monad and applicative functors.

I see two implementation for ap:

ap m1 m2 = do { f <- m1 ; x <- m2 ; return (f x) }

and

ap m1 m2 = do { x <- m2 ; f <- m1 ; return (f x) }

The second one is different, yet, would it be a good implementation for <*> ?

I got lost in the proof of pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

I try to get an intuition of "what part of the monad is the applicative functor"...

Answer 1

There are at least three relevant aspects to this question.

1. Given a Monad m instance, what is the specification of its necessary Applicative m superclass instance? Answer: pure is return, <*> is ap, so

   mf <*> ms == do f <- mf; s <- ms; return (f s)
   

Note that this specification is not a law of the Applicative class. It's a requirement on Monads, to ensure consistent usage patterns.

2. Given that specification (by candidate implementation), is ap the only acceptable implementation. Answer: resoundingly, no. The value dependency permitted by the type of >>= can sometimes lead to inefficient execution: there are situations where <*> can be made more efficient than ap because you don't need to wait for the first computation to finish before you can tell what the second computation is. The "applicative do" notation exists exactly to exploit this possibility.

3. Do any other candidate instances for Applicative satisfy the Applicative laws, even though they disagree with the required ap instances? Answer: yes. The "backwards" instance proposed by the question is just such a thing. Indeed, as another answer observes, any applicative can be turned backwards, and the result is often a different beast.

For a further example and exercise for the reader, note that nonempty lists are monadic in the way familiar from ordinary lists.

  data Nellist x = x :& Maybe (Nellist x)

  necat :: Nellist x -> Nellist x -> Nellist x
  necat (x :& Nothing) ys = x :& Just ys
  necat (x :& Just xs) ys = x :& Just (necat xs ys)

  instance Monad Nellist where
    return x = x :& Nothing
    (x :& Nothing) >>= k = k x
    (x :& Just xs) >>= k = necat (k x) (xs >>= k)

Find at least four behaviourally distinct instances of Applicative Nellist which obey the applicative laws.

Answer 2

Let's start with the obvious fact: such a definition for <*> violates the ap-law in the sense that <*> should ap, where ap is the one defined in the Monad class, i.e. the first one you posted.

Trivialities aside, as far as I can see, the other applicative laws should hold.

More concretely, let's focus on the composition law you mentioned. Your "reversed" ap

(<**>) m1 m2 = do { x <- m2 ; f <- m1 ; return (f x) }

can also be defined as

(<**>) m1 m2 = pure (flip ($)) <*> m2 <*> m1

where <*> is the "regular" ap.

This means that, for instance,

u <**> (v <**> w) =
  { def. <**> }
pure (flip ($)) <*> (v <**> w) <*> u =
  { def. <**> }
pure (flip ($)) <*> (pure (flip ($)) <*> w <*> v) <*> u =
  { composition law }
pure (.) <*> pure (flip ($)) <*> (pure (flip ($)) <*> w) <*> v <*> u =
  { homomorphism law }
pure ((.) (flip ($))) <*> (pure (flip ($)) <*> w) <*> v <*> u =
  { composition law }
pure (.) <*> pure ((.) (flip ($))) <*> pure (flip ($)) <*> w <*> v <*> u =
  { homomorphism law (x2)}
pure ((.) ((.) (flip ($))) (flip ($))) <*> w <*> v <*> u =
  { beta reduction (several) }
pure (\x f g -> g (f x)) <*> w <*> v <*> u

(I hope I got everything OK)

Try doing something similar to the left hand side.

pure (.) <**> u <**> v <**> w = ...