-XFunctorialDo

tl;dr: ApplicativeDo is useful also for functors. However, use laziness when pattern matching. The GHC manual remains a fantastic resource for learning about language extensions.

By default, do blocks are associated with Monad constraints. You might know that by enabling the ApplicativeDo language extension, we can write do blocks for unary type constructors that are not monads, but only applicatives. (Recall that Monad is a subclass of Applicative since GHC 7.10.1.)

{-# LANGUAGE ApplicativeDo #-}

showAnInt :: Applicative f => f Int -> f String
showAnInt action = do
  n <- action
  return $ show n

But did you know that we can also write do blocks for Functors?

-- Note the 'Functor' constraint rather than 'Applicative'.
showAnIntFunctor :: Functor f => f Int -> f String
showAnIntFunctor action = do
  n <- action
  return $ show n

I encountered this accidentally while writing code for Hasura: I wrote a do block for something that I suspected might have an Applicative instance. It compiled, and everything was fine, but at a later stage I could not track down where that instance was defined.

Origins

At first, I suspected that the GHC rewriting mechanism was kicking in just in time to compile (the equivalent of) showAnIntFunctor down to something like (show <$>). In retrospect, this was a bad suspicion: it would be terribly confusing if the rewriting mechanism would arbitrarily change the type of things. Put differently, the motto should be: terms that are well-typed with rewriting should also be well-typed without rewriting.

So why does it work?

Certainly, ApplicativeDo does not simply relax the Monad constraint on do blocks to Applicative, since some do blocks cannot be desugared to code in terms of the Applicative methods. A very simple example of that is:

applyToPackage box action = do
  x <- box
  action x

The above doesn’t work for Applicatives, because it implements exactly the (>>=) operator that distinguishes Monads from Applicatives. Hence:

-- Note the 'Monad' constraint despite us having switched on 'ApplicativeDo'
applyToPackage :: Monad f => f a -> (a -> f b) -> f b

So how does the appropriate constraint on a given do block arise? The constraint is not generated directly by GHC. Rather, normally, a do block is desugared into applications of (>>=), and it is through these operators that a Monad constraint normally arises. In fact, already without ApplicativeDo, the following compiles:

-- NB: No constraints on 'f' are required.
justDoIt :: f Int -> f Int
justDoIt action = do
  action

The logic that ApplicativeDo adds is that it does a syntactic analysis of the code inside the do block, in order to make use of (<$>) and (<*>) rather than (>>=) where possible.

This syntactic analysis works out to a single application of (<$>) for the above example of showAnIntFunctor. But this analysis is imperfect and does not always produce the expected result. For instance, all of the following four methods can be “desugared” to pure :: Applicative f => a -> f a:

pure1 = return

pure2 x = do
  return x

pure3 x = do
  y <- pure x
  return x

pure4 x = do
  y <- return x
  return x

However, only the third item is considered to be Applicative by the ApplicativeDo extension.

pure1 :: Monad f => a -> f a
pure2 :: Monad f => a -> f a
pure3 :: Applicative f => a -> f a
pure4 :: Monad f => a -> f a

Perhaps, if return becomes an alias for pure, i.e. after the monad of no return GHC proposal is implemented, all four can be generalized to Applicative.

Similarly, one can write convoluted do blocks that can be implemented by id :: f a -> f a, which requires no constraints on f, but regardless ApplicativeDo desugars those do blocks to code that has constraints on f.

constrainedId xM = do
  x <- xM
  pure x
constrainedId :: Functor f => f a -> f a

Pattern matching

One further oddity arises when pattern matching. Perhaps surprisingly, the code

unpackAndApply1 gM xyF = do
  (i, _) <- xyF
  g <- gM
  return $ g i
unpackAndApply1 :: Monad f => f (Int -> a) -> f (Int, String) -> f a

gets a Monad constraint, despite the code seemingly only requiring Applicative: just capture the result of the monadic action and unpack it with fst, avoiding (>>=).

unpackAndApply2 gM xyF =
  gM <*> (fst <$> xyF)
unpackAndApply2 :: Applicative f => f (Int -> a) -> f (Int, String) -> f a

So why the Monad constraint? Again I originally started with an incorrect suspicion, namely that this was because the pattern match might fail (think of a Left pattern match on an Either value), and was hence injecting a call to fail. But, in retrospect, that doesn’t make sense, since the constraint is Monad f, not MonadFail f. Born in the wrong generation, I guess…

The answer is that there’s a semantic difference between

• unpackAndApply1 (const 'a') (pure undefined) (which is undefined) and
• unpackAndApply2 (const 'a') (pure undefined) (which is pure 'a').

Hence, ApplicativeDo does not desuger unpackAndApply1 into unpackAndApply2 since it would change the strictness of the do block.

We can convince ApplicativeDo otherwise by flagging the pattern match as being lazy:

unpackAndApply3 gM xyF = do
  ~(i, _) <- xyF
  g <- gM
  return $ g i
unpackAndApply3 :: Applicative f => f (Int -> a) -> f (Int, String) -> f a

This moves the goalpost by allowing the tuple to be unpacked on an as-needed basis.

Another way to resolve it is by manually moving the pattern match to a point where it doesn’t interfere with an applicative desugaring of the do block:

unpackAndApply4 gM xyF = do
  x'y <- xyF
  g <- gM
  return $ g (fst x'y) -- now the unpacking happens here
unpackAndApply4 :: Applicative f => f (Int -> a) -> f (Int, String) -> f a

unpackAndApply2, unpackAndApply3 and unpackAndApply4 should be semantically equal.

Parallelism

The original motivation for ApplicativeDo was to speed up certain code written in do blocks, even when a Monad instance is in scope. The idea was that (<$>) and (<*>) allowed for more efficient implementations than the default ones arising from (>>=) and return. The final desugaring of a do block might be a mixture of all of (<$>), (<*>) and (>>=), where parts of the applicative-based may be executed “in parallel”, and parts which are necessarily monadic are executed “sequentially”, whatever those two terms mean in the domain of the code.

In order to make optimal use of this, it is important to organize do blocks in such a way that the functorial and applicative operators can kick in. For instance, the first block can be optimized better than the second block: (this example comes straight from the paper linked above) (both require a Monad)

variant1 xM xM' f f' = do
  x <- xM
  y <- f x
  x' <- xM'
  y' <- f' x'
  return (y, y')

variant2 xM xM' f f' = do
  x <- xM
  x' <- xM' -- note this line being executed earlier,
  y <- f x  -- ... before the call to 'f'
  y' <- f' x'
  return (y, y')

The problem is that the call to xM' in the second variant prevents f from starting execution, whereas in the first version the computation of y and y' are fully independent. Algebraically, we can say that ApplicativeDo only applies those transformations that follow the laws of functors/applicatives/monads, and reordering monadic actions is not allowed in general (and in fact, not well-typed in general).

So when writing monadic code that can potentially be desugared into more efficient code using applicative combinators (even partially), the motto to keep in mind is “related things go together”.

This is somewhat opposed to low-level machine code, where one tries to maximize the number of instructions between, for instance, fetching data from memory and using that data, so that high-performance processor architectures such as pipelining and out-of-order-execution work optimally.

GHC User’s Guide

I haven’t said anything fundamentally new in this blog post. Most of this content can also be found in the GHC User’s Guide, and indeed that was my main source. I found the documentation there very readable, and it answered exactly the questions that I found myself asking.