Applicatives compose, monads don't
Solution 1
If we compare the types
(<*>) :: Applicative a => a (s -> t) -> a s -> a t
(>>=) :: Monad m => m s -> (s -> m t) -> m t
we get a clue to what separates the two concepts. That (s -> m t)
in the type of (>>=)
shows that a value in s
can determine the behaviour of a computation in m t
. Monads allow interference between the value and computation layers. The (<*>)
operator allows no such interference: the function and argument computations don't depend on values. This really bites. Compare
miffy :: Monad m => m Bool -> m x -> m x -> m x
miffy mb mt mf = do
b <- mb
if b then mt else mf
which uses the result of some effect to decide between two computations (e.g. launching missiles and signing an armistice), whereas
iffy :: Applicative a => a Bool -> a x -> a x -> a x
iffy ab at af = pure cond <*> ab <*> at <*> af where
cond b t f = if b then t else f
which uses the value of ab
to choose between the values of two computations at
and af
, having carried out both, perhaps to tragic effect.
The monadic version relies essentially on the extra power of (>>=)
to choose a computation from a value, and that can be important. However, supporting that power makes monads hard to compose. If we try to build ‘double-bind’
(>>>>==) :: (Monad m, Monad n) => m (n s) -> (s -> m (n t)) -> m (n t)
mns >>>>== f = mns >>-{-m-} \ ns -> let nmnt = ns >>= (return . f) in ???
we get this far, but now our layers are all jumbled up. We have an n (m (n t))
, so we need to get rid of the outer n
. As Alexandre C says, we can do that if we have a suitable
swap :: n (m t) -> m (n t)
to permute the n
inwards and join
it to the other n
.
The weaker ‘double-apply’ is much easier to define
(<<**>>) :: (Applicative a, Applicative b) => a (b (s -> t)) -> a (b s) -> a (b t)
abf <<**>> abs = pure (<*>) <*> abf <*> abs
because there is no interference between the layers.
Correspondingly, it's good to recognize when you really need the extra power of Monad
s, and when you can get away with the rigid computation structure that Applicative
supports.
Note, by the way, that although composing monads is difficult, it might be more than you need. The type m (n v)
indicates computing with m
-effects, then computing with n
-effects to a v
-value, where the m
-effects finish before the n
-effects start (hence the need for swap
). If you just want to interleave m
-effects with n
-effects, then composition is perhaps too much to ask!
Solution 2
Applicatives compose, monads don't.
Monads do compose, but the result might not be a monad.
In contrast, the composition of two applicatives is necessarily an applicative.
I suspect the intention of the original statement was that "Applicativeness composes, while monadness doesn't." Rephrased, "Applicative
is closed under composition, and Monad
is not."
Solution 3
If you have applicatives A1
and A2
, then the type data A3 a = A3 (A1 (A2 a))
is also applicative (you can write such an instance in a generic way).
On the other hand, if you have monads M1
and M2
then the type data M3 a = M3 (M1 (M2 a))
is not necessarily a monad (there is no sensible generic implementation for >>=
or join
for the composition).
One example can be the type [Int -> a]
(here we compose a type constructor []
with (->) Int
, both of which are monads). You can easily write
app :: [Int -> (a -> b)] -> [Int -> a] -> [Int -> b]
app f x = (<*>) <$> f <*> x
And that generalizes to any applicative:
app :: (Applicative f, Applicative f1) => f (f1 (a -> b)) -> f (f1 a) -> f (f1 b)
But there is no sensible definition of
join :: [Int -> [Int -> a]] -> [Int -> a]
If you're unconvinced of this, consider this expression:
join [\x -> replicate x (const ())]
The length of the returned list must be set in stone before an integer is ever provided, but the correct length of it depends on the integer that's provided. Thus, no correct join
function can exist for this type.
Solution 4
Unfortunately, our real goal, composition of monads, is rather more difficult. .. In fact, we can actually prove that, in a certain sense, there is no way to construct a join function with the type above using only the operations of the two monads (see the appendix for an outline of the proof). It follows that the only way that we might hope to form a composition is if there are some additional constructions linking the two components.
Composing monads, http://web.cecs.pdx.edu/~mpj/pubs/RR-1004.pdf
Solution 5
The distributive law solution l : MN -> NM is enough
to guarantee monadicity of NM. To see this you need a unit and a mult. i'll focus on the mult (the unit is unit_N unitM)
NMNM - l -> NNMM - mult_N mult_M -> NM
This does not guarantee that MN is a monad.
The crucial observation however, comes into play when you have distributive law solutions
l1 : ML -> LM
l2 : NL -> LN
l3 : NM -> MN
thus, LM, LN and MN are monads. The question arises as to whether LMN is a monad (either by
(MN)L -> L(MN) or by N(LM) -> (LM)N
We have enough structure to make these maps. However, as Eugenia Cheng observes, we need a hexagonal condition (that amounts to a presentation of the Yang-Baxter equation) to guarantee monadicity of either construction. In fact, with the hexagonal condition, the two different monads coincide.
missingfaktor
I am no longer active on this site, but if my posts help you and/or you need further help, do let me know on Twitter at @missingfaktor. I will try my best to respond! Note: This profile description was written for StackOverflow, and was copied to all other StackExchange sites as-is.
Updated on June 15, 2022Comments
-
missingfaktor almost 2 years
Applicatives compose, monads don't.
What does the above statement mean? And when is one preferable to other?
-
andrew cooke over 12 years...so avoid monads when a function will do?
-
Alexandre C. over 12 yearsTl;dr for impatient readers: you can compose monads if(f?) you can provide a natural transformation
swap : N M a -> M N a
-
Bayquiri over 12 years@andrew, if you meant functor, then yes, functors are simpler and should be used when sufficient. Note that it's not always. For example
IO
without aMonad
would be very hard to program. :) -
C. A. McCann over 12 years@Alexandre C.: Just "if", I suspect. Not all monad transformers are described by direct functor composition. For instance,
ContT r m a
is neitherm (Cont r a)
norCont r (m a)
, andStateT s m a
is roughlyReader s (m (Writer s a))
. -
Alexandre C. over 12 years@C. A. McCann: I can't seem to get from (M monad, N monad, MN monad, NM monad) to (there exists swap : MN -> NM natural). So let's stick to "if" for now (perhaps the answer is in the paper, I must confess I looked it up quickly)
-
C. A. McCann over 12 years@Alexandre C.: Just specifying that the compositions are monads may not be enough anyway--you also need some way to relate the two parts with the whole. The existence of
swap
implies that the composition lets the two "cooperate" somehow. Also, note thatsequence
is a special case of "swap" for some monads. So isflip
, actually. -
pigworker over 12 yearsTo write
swap :: N (M x) -> M (N x)
it looks to me like you can usereturns
(suitablyfmap
ped) to insert anM
at the front and anN
at the back, going fromN (M x) -> M (N (M (N x)))
, then use thejoin
of the composite to get yourM (N x)
. -
Alexandre C. over 12 years@C. A. McCann: I get your point, but I fail to see how
flip
is a special case ofswap
.sequence
makes sense to me however. -
C. A. McCann over 12 years@Alexandre C.: Think of it as
flip :: (->) a ((->) b c) -> (->) b ((->) a c)
. In other words,swap
used on two reader monads. -
Apocalisp over 12 yearsAdditionally, any two applicatives compose in a completely mechanical way, whereas the monad formed by the composition of two monads is specific to that composition.
-
Edward Kmett over 12 yearsMoreover monads compose in other ways, the product of two monads is a monad, it is only the coproducts that need some kind of distributive law.
-
Dan Burton over 12 yearsThis is probably a great answer, but it went whoosh way over my head.
-
shj about 12 yearsFor the iffy example you state that it "uses the value of ab to choose between the values of two computations at and af, having carried out both, perhaps to tragic effect." Doesn't the lazy nature of Haskell protect you against this? If I have list = (\b t f -> if b then t else f) : [] and then execute the statement: list <*> pure True <*> pure "hello" <*> pure (error "bad")....I get "hello" and the error never occurs. This code isn't nearly as safe or controlled as a monad, but the post seems like it's suggesting that applicatives cause strict evaluation. Overall great post though! Thanks!
-
pigworker about 12 yearsYou still get the effects of both, but pure (error "bad") doesn't have any. If, on the other hand, you try iffy (pure True) (pure "hello") (error "bad"), you get an error which miffy avoids. Moreover, if you try something like iffy (pure True) (pure 0) [1,2], you'll get [0,0] instead of [0]. Applicatives have a kind of strictness about them, in that they build fixed sequences of computations, but the values resulting from those computations are still combined lazily, as you observe.
-
ron almost 12 yearsIs it true, that for any monads
m
andn
you can always write a monad transformermt
, and operate inn (m t)
usingmt n t
? So you can always compose monads, it is just more complicated, using transformers? -
pigworker almost 12 yearsSuch transformers often exist, but as far as I know, there's no canonical way of generating them. There's often a genuine choice about how to resolve interleaved effects from the different monads, the classic example being exceptions and state. Should an exception roll back state changes or not? Both choices have their place. Having said that, there's a "free monad" thing that expresses "arbitrary interleaving".
data Free f x = Ret x | Do (f (Free f x))
, thendata (:+:) f g x = Inl (f x) | Tnr (g x)
, and considerFree (m :+: n)
. That delays the choice of how to run interleavings. -
Paul Draper almost 9 yearsWith, @Apocalisp, comment included, this is the best and most concise answer.
-
ziggystar over 8 years@pigworker Concerning the lazy/strict debate. I think that with applicatives you cannot control the effect from within the computation, but the effect-layer can very well decide not to evaluate later values. For (applicative) parsers this means that if the parser fails early, subsequent parsers are not evaluated/applied to the input. For
Maybe
this means that an earlyNothing
will suppress the evaluation of thea
of a later/subsequentJust a
. Is this correct? -
pigworker over 8 years@ziggystar Yes. What can't happen is that the values from earlier computations determine the choice of later computations. How lazy or strict the execution of computations might be is entirely another matter.
-
Arek' Fu over 7 yearsI thought I understood Applicatives, but this post cured me of my folly.
-
Arek' Fu over 7 years@pigworker, how does
error "bad"
not have any effects? I'm stumped. Can you please define "effects"? -
codeshot over 6 yearsThat's because, using the term Applicative and haskell tag, this is a question about haskell but with an answer in a different notation.
-
ivan vadovič almost 6 years@Arek'Fu you've neglected the `pure'. It's pure (error "bad") that has no effects, or any pure (anything) for that matter.