### -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
= do
showAnInt action <- action
n return $ show n
```

But did you know that we can also write `do`

blocks for `Functor`

s?

```
-- Note the 'Functor' constraint rather than 'Applicative'.
showAnIntFunctor :: Functor f => f Int -> f String
= do
showAnIntFunctor action <- action
n 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:

```
= do
applyToPackage box action <- box
x action x
```

The above doesn’t work for `Applicative`

s, because it implements exactly the `(>>=)`

operator that distinguishes `Monad`

s from `Applicative`

s. 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
= do
justDoIt action 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`

:

`= return pure1 `

```
= do
pure2 x return x
```

```
= do
pure3 x <- pure x
y return x
```

```
= do
pure4 x <- return x
y 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`

.

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

# Pattern matching

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

```
= do
unpackAndApply1 gM xyF <- xyF
(i, _) <- gM
g 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 <*> (fst <$> xyF)
gM 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:

```
= do
unpackAndApply3 gM xyF ~(i, _) <- xyF
<- gM
g 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:

```
= do
unpackAndApply4 gM xyF <- xyF
x'y <- gM
g 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`

)

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

```
= do
variant2 xM xM' f f' <- xM
x <- xM' -- note this line being executed earlier,
x' <- f x -- ... before the call to 'f'
y <- f' x'
y' 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.

## Comments

## Post a Comment