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"...
There are at least three relevant aspects to this question.
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 Monad
s, to ensure consistent usage patterns.
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.
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.
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 = ...
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With