Version 5 (modified by simonpj, 12 months ago) (diff) |
---|

# Applicative do-notation

This is a proposal to add support to GHC for desugaring do-notation into Applicative expressions where possible.

## Related proposals

## Motivation

- Some Monads have the property that Applicative bind is more
efficient than Monad bind. Sometimes this is
*really important*, such as when the Applicative bind is concurrent whereas the Monad bind is sequential (c.f. Haxl). For these monads we would like the do-notation to desugar to Applicative bind where possible, to take advantage of the improved behaviour but without forcing the user to explicitly choose.

- Applicative syntax can be a bit obscure and hard to write.
Do-notation is more natural, so we would like to be able to write
Applicative composition in do-notation where possible. For example:
(\x y z -> x*y + y*z + z*x) <$> expr1 <*> expr2 <*> expr3

vs.do x <- expr1; y <- expr2; z <- expr3; return $ x*y + y*z + z*x

- Do-notation can't be desugared into Applicative in general, but a certain subset of it can be. For Applicatives that aren't also Monads, we would still like to be able to use the do-notation, albeit with some restrictions, and have an Applicative constraint inferred rather than Monad.

Clearly we need Applicative to be a superclass of Monad for this to work, hence this can only happen after the AMP changes have landed.

Since in general Applicative composition might behave differently from monadic bind, any automatic desugaring to Applicative operations would be an opt-in extension:

{-# LANGUAGE ApplicativeDo #-}

## Stage 1

This section describes a transformation that could be performed during desugaring. It covers use case (1), but not (2). I'm describing this first because it is easy to understand by itself, and extends to a solution for (2). We might consider implementing this first.

### Examples

do x <- A y <- B -- B does not refer to x return (f x y)

desugars to

do (x,y) <- (,) <$> A <*> B return (f x y)

Note that the tuples introduces like this will probably be optimised away when the Monad type is known and its bind can be inlined, but for overloaded Monad code they will not be. In Stage 2 (below) we'll get rid of the tuples in some cases.

In general we might have

do .. stmts1 .. x <- A y <- B z <- E[y] .. stmts2 ..

which we desugar to

do .. stmts1 .. (x,y) <- (,) <$> A <*> B z <- E[y] .. stmts2 ..

this is the best we can do: the rest of the do expression might refer to x or y.

So in general we want to take the largest consecutive sequence of statements where none of the rhs's refer to any of the bound variables, and lift them into an Applicative expression.

A non-binding statement can be considered to be a binding statement with a wildcard pattern.

do x <- A y <- B -- B does not refer to x C -- C does not refer to x or y return (f x y)

desugars to

do (x,y,_) <- (,,) <$> A <*> B <*> C return (f x y)

or we can be slightly more clever:

do (x,y) <- (,) <$> A <*> (B <* C) return (f x y)

What if there are more than 63(?) statements, and we don't have a tuple big enough? We have to desugar to nested tuples in this case. Not a huge problem, this is exactly what we do for pattern bindings.

### No unique grouping

There isn't a guaranteed unique way of doing the grouping. Eg

do { x <- A ; y <- B -- no x ; z <- C x }

could be grouped with the first two in an applicative, or the second two, but not all three. Which one "wins"?

## Stage 2

This covers a more comprehensive transformation that would also enable us to drop a Monad constraint to an Applicative constraint in the typing of do expressions for a certain well-defined subset of the do syntax.

Back to our first example:

do x <- A y <- B -- B does not refer to x return (f x y)

we can go further in desugaring this:

(\x y -> f x y) <$> A <*> B

(obviously the lambda expression can be eta-reduced in this example, but that's not the case in general).

For this to work we have to recognise "return". Or perhaps "pure".

There are two advantages here:

- This code could be typed with an Applicative constraint rather than Monad.

- It leads to more efficient code when the Monad type is not known, because we have eliminated the intermediate pair.

What if the final expression is not a "return"?

do x <- A y <- B -- B does not refer to x f x y

this is

join ((\x y -> f x y) <$> A <*> B)

Note: *not* an Applicative, because "join" is a Monad operation. However we have eliminated the pair.

Problems:

- desugaring comes after typechecking, so the type checker would need its own version of the desugaring rules to be able to tell when a do expression can be fully desugared to Applicative syntax.