Fri, 21 Oct 2022
More notes on deriving Applicative from Monad
A year or two ago I wrote about what you do if you already have a Monad and you need to define an Applicative instance for it. This comes up in converting old code that predates the incorporation of Applicative into the language: it has these monad instance declarations, and newer compilers will refuse to compile them because you are no longer allowed to define a Monad instance for something that is not an Applicative. I complained that the compiler should be able to infer this automatically, but it does not.
My current job involves Haskell programming and I ran into this issue again in August, because I understood monads but at that point I was still shaky about applicatives. This is a rough edit of the notes I made at the time about how to define the Applicative instance if you already understand the Monad instance.
pure is easy: it is identical to return.
Now suppose we
have >>=: how can we get <*>? As I eventually figured out last
time this came up, there is a simple solution:
fc <*> vc = do
f <- fc
v <- vc
return $ f v
or equivalently:
fc <*> vc = fc >>= \f -> vc >>= \v -> return $ f v
And in fact there is at least one other way to define it is just as good:
fc <*> vc = do
v <- vc
f <- fc
return $ f v
(Control.Applicative.Backwards
provides a Backwards constructor that reverses the order of the
effects in <*>.)
I had run into this previously
and written a blog post about it.
At that time I had wanted the second <*>, not the first.
The issue came up again in August because, as an exercise, I was trying to
implement the StateT state transformer monad constructor from scratch. (I found
this very educational. I had written State before, but StateT was
an order of magnitude harder.)
I had written this weird piece of code:
instance Applicative f => Applicative (StateT s f) where
pure a = StateT $ \s -> pure (s, a)
stf <*> stv = StateT $
\s -> let apf = run stf s
apv = run stv s
in liftA2 comb apf apv where
comb = \(s1, f) (s2, v) -> (s1, f v) -- s1? s2?
It may not be obvious why this is weird. Normally the definition of
<*> would look something like this:
stf <*> stv = StateT $
\s0 -> let (s1, f) = run stf s0
let (s2, v) = run stv s1
in (s2, f v)
This runs stf on the initial state, yielding f and a new state
s1, then runs stv on the new state, yielding v and a final state
s2. The end result is f v and the final state s2.
Or one could just as well run the two state-changing computations in the opposite order:
stf <*> stv = StateT $
\s0 -> let (s1, v) = run stv s0
let (s2, f) = run stf s1
in (s2, f v)
which lets stv mutate the state first and gives stf the result
from that.
I had been unsure of whether I wanted to run stf or stv first. I
was familiar with monads, in which the question does not come up. In
v >>= f you must run v first because you will pass its value
to the function f. In an Applicative there is no such dependency, so I
wasn't sure what I neeeded to do. I tried to avoid the question by
running the two computations ⸢simultaneously⸣ on the initial state
s0:
stf <*> stv = StateT $
\s0 -> let (sf, f) = run stf s0
let (sv, v) = run stv s0
in (sf, f v)
Trying to sneak around the problem, I was caught immediately, like a
small child hoping to exit a room unseen but only getting to the
doorway. I could run the computations ⸢simultaneously⸣ but on the
very next line I still had to say what the final state was in the end:
the one resulting from computation stf or the one resulting from
computation stv. And whichever I chose, I would be discarding the
effect of the other computation.
My co-worker Brandon Chinn
opined that this must
violate one of the
applicative functor laws.
I wasn't sure, but he was correct.
This implementation of <*> violates the applicative ”interchange”
law that requires:
f <*> pure x == pure ($ x) <*> f
Suppose f updates the state from !!s_0!! to !!s_f!!. pure x and
pure ($ x), being pure, leave it unchanged.
My proposed implementation of <*> above runs the two
computations and then updates the state to whatever was the result of
the left-hand operand, sf discarding any updates performed by the right-hand
one. In the case of f <*> pure x the update from f is accepted
and the final state is !!s_f!!.
But in the case of pure ($ x) <*> f the left-hand operand doesn't do
an update, and the update from f is discarded, so the final state is
!!s_0!!, not !!s_f!!. The interchange law is violated by this implementation.
(Of course we can't rescue this by yielding (sv, f v) in place of
(sf, f v); the problem is the same. The final state is now the
state resulting from the right-hand operand alone, !!s_0!! on the
left side of the law and !!s_f!! on the right-hand side.)
Stack Overflow discussion
I worked for a while to compose a question about this for Stack Overflow, but it has been discussed there at length, so I didn't need to post anything:
<**>is a variant of<*>with the arguments reversed. What does "reversed" mean?- How arbitrary is the "ap" implementation for monads?
- To what extent are Applicative/Monad instances uniquely determined?
That first thread contains this enlightening comment:
Functors are generalized loops
[ f x | x <- xs];Applicatives are generalized nested loops
[ (x,y) | x <- xs, y <- ys];Monads are generalized dynamically created nested loops
[ (x,y) | x <- xs, y <- k x].
That middle dictum provides another way to understand why my idea of running the effects ⸢simultaneously⸣ was doomed: one of the loops has to be innermost.
The second thread above (“How arbitrary is the ap implementation for
monads?”) is close to what I was aiming for in my question, and
includes a wonderful answer by Conor McBride (one of the inventors of
Applicative). Among other things, McBride points out that there are at least
four reasonable Applicative instances consistent with the monad
definition for nonempty lists.
(There is a hint in his answer here.)
Another answer there sketches a proof that if the applicative
”interchange” law holds for some applicative functor f, it holds for
the corresponding functor which is the same except that its <*>
sequences effects in the reverse order.
[Other articles in category /prog/haskell] permanent link