Archive:
Subtopics:
Comments disabled |
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.
Now suppose we
have
or equivalently:
And in fact there is at least one other way to define it is just as good:
( I had run into this previously
and written a blog post about it.
At that time I had wanted the second The issue came up again in August because, as an exercise, I was trying to
implement the 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
This runs Or one could just as well run the two state-changing computations in the opposite order:
which lets I had been unsure of whether I wanted to run 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 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
Suppose My proposed implementation of (Of course we can't rescue this by yielding Stack Overflow discussionI 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:
That first thread contains this enlightening comment:
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 Another answer there sketches a proof that if the applicative
”interchange” law holds for some applicative functor [Other articles in category /prog/haskell] permanent link |