Why should Applicative be a superclass of Monad?

问题:

Given:

Applicative m, Monad m => mf :: m (a -> b), ma :: m a

it seems to be considered a law that:

mf <*> ma === do { f <- mf; a <- ma; return (f a) }

or more concisely:

(<*>) === ap

The documentation for Control.Applicative says that <*> is "sequential application," and that suggests that (<*>) = ap. This means that <*> must evaluate effects sequentially from left to right, for consistency with >>=... But that feels wrong. McBride and Paterson's original paper seems to imply that the left-to-right sequencing is arbitrary:

The IO monad, and indeed any Monad, can be made Applicative by taking pure = return and <*> = ap. We could alternatively use the variant of ap that performs the computations in the opposite order, but we shall keep to the left-to-right order in this paper.

So there are two lawful, non-trivial derivations for <*> that follow from >>= and return, with distinct behavior. And in some cases, neither of these two derivations are desirable.

For example, the (<*>) === ap law forces Data.Validation to define two distinct data types: Validation and AccValidation. The former has a Monad instance similar to ExceptT, and a consistent Applicative instance which is of limited utility, since it stops after the first error. The latter, on the other hand, doesn't define a Monad instance, and is therefore free to implement an Applicative that, much more usefully, accumulates errors.

There's been some discussion about this previously on StackOverflow, but I don't think it really got to the meat of the question:

Why should this be a law?

The other laws for functors, applicatives and monads—such as identity, associativity, etc.—express some fundamental, mathematical properties of those structures. We can implement various optimizations using these laws and prove things about our own code using them. In contrast, it feels to me like the (<*>) === ap law imposes an arbitrary constraint with no corresponding benefit.

For what it's worth, I'd prefer to ditch the law in favor of something like this:

newtype LeftA m a = LeftA (m a)
instance Monad m => Applicative (LeftA m) where
  pure = return
  mf <*> ma = do { f <- mf; a <- ma; return (f a) }

newtype RightA m a = RightA (m a)
instance Monad m => Applicative (RightA m) where
  pure = return
  mf <*> ma = do { a <- ma; f <- mf; return (f a) }

I think that correctly captures the relationship between the two, without unduly constraining either.

So, a few angles to approach the question from:

• Are there any other laws relating Monad and Applicative?
• Is there any inherent mathematical reason for effects to sequence for Applicative in the same way that they do for Monad?
• Does GHC or any other tool perform code transformations that assume/require this law to be true?
• Why is the Functor-Applicative-Monad proposal considered such an overwhelmingly good thing? (Citations would be much appreciated here).

And one bonus question:

• How do Alternative and MonadPlus fit in to all this?

---

Note: major edit to clarify the meat of the question. Answer posted by @duplode quotes an earlier version.

回答1:

Well, I'm not terribly satisfied with the answers given so far, but I think the comments attached to them are a bit more compelling. So I'll summarize here:

---

I think there's only one sensible Functor instance that follows from Applicative:

fmap f fa = pure f <*> fa

Assuming that's unique, it makes sense that Functor should be a superclass of Applicative, with that law. Likewise, I think there's only one sensible Functor instance that follows from Monad:

fmap f fa = fa >>= return . f

So again, it makes sense that Functor should be a superclass of Monad. The objection I had (and, really, still have) is that there are two sensible Applicative instances that follow from Monad and, in some specific instances, even more that are lawful; so why mandate one?

pigworker (first author on the original Applicative paper) writes:

"Of course it doesn't follow. It's a choice."

(on twitter): "do-notation is unjust punishment for working in a monad; we deserve applicative notation"

duplode similarly writes:

"... it is fair to say that pure === return and (<*>) === ap aren't laws in the strong sense that e.g. the monad laws are so ..."

"On the LeftA/RightA idea: there are comparable cases elsewhere in the standard libraries (e.g. Sum and Product in Data.Monoid). The problem of doing the same with Applicative is that the power-to-weight relation is too low to justify the extra precision/flexibility. The newtypes would make applicative style a lot less pleasant to use."

So, I'm happy to see that choice stated explicitly, justified by the simple reasoning that it makes the most common cases easier.

回答2:

Among other things, you ask why is the Functor-Applicative-Monad proposal a good thing. One reason is because the lack of unity means there is a lot of duplication of API. Consider the standard Control.Monad module. The following are the functions in that module that essentially use the Monad (there are none for MonadPlus) constraint:

(>>=) fail (=<<) (>=>) (<=<) join foldM foldM_

The following are the functions in that module where a Monad/MonadPlus constraint could as far as I can tell easily be relaxed to Applicative/Alternative:

(>>) return mzero mplus mapM mapM_ forM forM_ sequence sequence_ forever
msum filterM mapAndUnzipM zipWithM zipWithM_ replicateM replicateM_ guard
when unless liftM liftM2 liftM3 liftM4 liftM5 ap

Many of the latter group do have Applicative or Alternative versions, in either Control.Applicative, Data.Foldable or Data.Traversable – but why need to learn all that duplication in the first place?

回答3:

and in my own (perhaps mistaken) intuition, given pure f <*> ma <*> mb, there needn't be any predetermined sequencing since none of the values depend on each other.

The values don't, but the effects do. (<*>) :: t (a -> b) -> t a -> t b means that you have to somehow combine the effects of the arguments in order to get the overall effects. Whether the combination will be commutative or not depends on how the instance is defined. For example, the instance for Maybe is commutative, while the default, "cross join" instance for lists isn't. Therefore, there are cases in which you can't avoid imposing some order.

What are the laws, if any, relating Monad and Applicative?

While it is fair to say that pure === return and (<*>) === ap (quoting Control.Applicative) aren't laws in the strong sense that e.g. the monad laws are so, they help keeping the instances unsurprising. Given that every Monad gives rise to an instance of Applicative (actually two instances, as you point out), it is natural that the actual instance of Applicative matches what Monad gives us. As for the left-to-right convention, following the order of ap and liftM2 (which already existed back when Applicative was introduced, and which mirror the order imposed by (>>=)) was a sensible decision. (Note that, if we ignored for a moment how much (>>=) matters in practice, the opposite choice would be defensible as well, as it would make (<*>) and (=<<), which have analogous types, sequence effects in the same order.)

Does GHC or any other tool perform code transformations that assume/require this law to be true?

That sounds very unlikely given that Applicative isn't even a superclass of Monad(yet). These "laws", however, allow readers of the code to make the transformations, which matters just as much.

N.B.: If you need to reverse the sequencing of effects in an Applicative instance, there is Control.Applicative.Backwards, as Gabriel Gonzalez has pointed out. Also, (<**>) flips the arguments but still sequences effects from left to right, so it can also be used to reverse sequencing. Similarly, (<*) is not flip (*>), as both sequence effects from left to right.

回答4:

Just for the record, the answer to the question in the title is: consider

sequenceA :: Applicative f, Traversable t => t (f a) -> f (t a)
join :: Monad m => m (m a) -> m a

What is the type of join . sequenceA?

1. ATP: Monad m, Traversable m => m (m a) -> m a
2. Current situation: Applicative m, Monad m, Traversable m => m (m a) -> m a

Granted, join . sequenceA is a contrived situation, but there are certainly cases where you need a monad, but you'd also like to use the Applicative operations <*>, *>, <*, <**>, etc. Then:

• Having two separate constraints to capture both operations is annoying.
• The Applicative names is (IMHO) nicer than those of the traditional monad operations.
• Having two different names, e.g. ap, >>, <<, etc., is annoying ("oh, you can't use <*> there, that's a Monad not an Applicative"; "oh, you have to use <*> there, that's an Applicative not a Monad").
• In real monads, the order is really, really important, which means that if >> and *> do different things, then you can't actually use the Applicative syntax, because it'll do something you don't expect.

So, pragmatically, having an Applicative for every Monad which is compatible with it (in the (<*>) = ap sense) is a really, really good idea.