Difference between Monad and Applicative in Haskell
I just read the following from typeclassopedia about the difference between Monad and Applicative . I can understand that there is no join in Applicative . But the following description looks vague to me and I couldn't figure out what exactly is meant by "the result" of a monadic computation/action. So, if I put a value into Maybe , which makes a monad, what is the result of this "computation"?
Let's look more closely at the type of (>>=). The basic intuition is that it combines two computations into one larger computation. The first argument, ma, is the first computation. However, it would be boring if the second argument were just an mb; then there would be no way for the computations to interact with one another (actually, this is exactly the situation with Applicative). So, the second argument to (>>=) has type a -> mb: a function of this type, given a result of the first computation, can produce a second computation to be run. ... Intuitively, it is this ability to use the output from previous computations to decide what computations to run next that makes Monad more powerful than Applicative. The structure of an Applicative computation is fixed, whereas the structure of a Monad computation can change based on intermediate results.
Is there a concrete example illustrating "ability to use the output from previous computations to decide what computations to run next", which Applicative does not have?
My favorite example is the "purely applicative Either". We'll start by analyzing the base Monad instance for Either
instance Monad (Either e) where
return = Right
Left e >>= _ = Left e
Right a >>= f = f a
This instance embeds a very natural short-circuiting notion: we proceed from left to right and once a single computation "fails" into the Left then all the rest do as well. There's also the natural Applicative instance that any Monad has
instance Applicative (Either e) where
pure = return
(<*>) = ap
where ap is nothing more than left-to-right sequencing before a return :
ap :: Monad m => m (a -> b) -> m a -> m b
ap mf ma = do
f <- mf
a <- ma
return (f a)
Now the trouble with this Either instance comes to light when you'd like to collect error messages which occur anywhere in a computation and somehow produce a summary of errors. This flies in the face of short-circuiting. It also flies in the face of the type of (>>=)
(>>=) :: m a -> (a -> m b) -> m b
If we think of ma as "the past" and mb as "the future" then (>>=) produces the future from the past so long as it can run the "stepper" (a -> mb) . This "stepper" demands that the value of a really exists in the future... and this is impossible for Either . Therefore (>>=) demands short-circuiting.
So instead we'll implement an Applicative instance which cannot have a corresponding Monad .
instance Monoid e => Applicative (Either e) where
pure = Right
Now the implementation of (<*>) is the special part worth considering carefully. It performs some amount of "short-circuiting" in its first 3 cases, but does something interesting in the fourth.
Right f <*> Right a = Right (f a) -- neutral
Left e <*> Right _ = Left e -- short-circuit
Right _ <*> Left e = Left e -- short-circuit
Left e1 <*> Left e2 = Left (e1 <> e2) -- combine!
Notice again that if we think of the left argument as "the past" and the right argument as "the future" then (<*>) is special compared to (>>=) as it's allowed to "open up" the future and the past in parallel instead of necessarily needing results from "the past" in order to compute "the future".
This means, directly, that we can use our purely Applicative Either to collect errors, ignoring Right s if any Left s exist in the chain
> Right (+1) <*> Left [1] <*> Left [2]
> Left [1,2]
So let's flip this intuition on its head. What can we not do with a purely applicative Either ? Well, since its operation depends upon examining the future prior to running the past, we must be able to determine the structure of the future without depending upon values in the past. In other words, we cannot write
ifA :: Applicative f => f Bool -> f a -> f a -> f a
which satisfies the following equations
ifA (pure True) t e == t
ifA (pure False) t e == e
while we can write ifM
ifM :: Monad m => m Bool -> m a -> m a -> m a
ifM mbool th el = do
bool <- mbool
if bool then th else el
such that
ifM (return True) t e == t
ifM (return False) t e == e
This impossibility arises because ifA embodies exactly the idea of the result computation depending upon the values embedded in the argument computations.
Just 1 describes a "computation", whose "result" is 1. Nothing describes a computation which produces no results.
The difference between a Monad and an Applicative is that in the Monad there's a choice. The key distinction of Monads is the ability to choose between different paths in computation (not just break out early). Depending on a value produced by a previous step in computation, the rest of computation structure can change.
Here's what this means. In the monadic chain
return 42 >>= (x ->
if x == 1
then
return (x+1)
else
return (x-1) >>= (y ->
return (1/y) ))
the if chooses what computation to construct.
In case of Applicative, in
pure (1/) <*> ( pure (+(-1)) <*> pure 1 )
all the functions work "inside" computations, there's no chance to break up a chain. Each function just transforms a value it's fed. The "shape" of the computation structure is entirely "on the outside" from the functions' point of view.
A function could return a special value to indicate failure, but it can't cause next steps in the computation to be skipped. They all will have to process the special value in a special way too. The shape of the computation can not be changed according to received value.
With monads, the functions themselves construct computations to their choosing.
Here is my take on @J. Abrahamson's example as to why ifA cannot use the value inside eg (pure True) . In essence, it still boils down to the absence of the join function from Monad in Applicative , which unifies the two different perspectives given in typeclassopedia to explain the difference between Monad and Applicative .
So using @J. Abrahamson's example of purely applicative Either :
instance Monoid e => Applicative (Either e) where
pure = Right
Right f <*> Right a = Right (f a) -- neutral
Left e <*> Right _ = Left e -- short-circuit
Right _ <*> Left e = Left e -- short-circuit
Left e1 <*> Left e2 = Left (e1 <> e2) -- combine!
(which has similar short-circuiting effect to the Either Monad ), and the ifA function
ifA :: Applicative f => f Bool -> f a -> f a -> f a
What if we try to achieve the mentioned equations:
ifA (pure True) t e == t
ifA (pure False) t e == e
?
Well, as already pointed out, ultimately, the content of (pure True) , cannot be used by a later computation. But technically speaking, this isn't right. We can use the content of (pure True) since a Monad is also a Functor with fmap . We can do:
ifA' b t e = fmap b (x -> if x then t else e)
The problem is with the return type of ifA' , which is f (fa) . In Applicative , there is no way of collapsing two nested Applicative S into one. But this collapsing function is precisely what join in Monad performs. So,
ifA = join . ifA'
will satisfy the equations for ifA , if we can implement join appropriately. What Applicative is missing here is exactly the join function. In other words, we can somehow use the result from the previous result in Applicative . But doing so in an Applicative framework will involve augmenting the type of the return value to a nested applicative value, which we have no means to bring back to a single-level applicative value. This will be a serious problem because, eg, we cannot compose functions using Applicative S appropriately. Using join fixes the issue, but the very introduction of join promotes the Applicative to a Monad .
上一篇: Haskell：（也许）monad构建