wiki:ApplicativeComprehensions

Applicative Comprehensions

This is a proposal to add support to GHC for desugaring certain instances of comprehensions into Applicative expression where possible. This feature is related to both ApplicativeDo and MonadComprehensions.

Summary

The ApplicativeComprehensions language extension would cause GHC to attempt to desugar comprehensions using a similar approach to MonadComprehensions, but in a way that only results in code with an Applicative constraint.

Any comprehension that includes only generator expressions where the bindings defined by a generator expression are not used in any subsequent generator expression can be desugared using only operations from the Applicative typeclass, so an expression like

[ expr_0 | pat_1 <- expr_1
         , pat_2 <- expr_2
         , ...
         , pat_n <- expr_n
         ]

can be desugared to

(\ pat_1 pat_2 ... pat_n ->
     pure expr_0) <$> expr_1
                  <*> expr_2
                  <*> ...
                  <*> expr_n

Motivation

As explained in the Motivation section for ApplicativeDo, some kinds of Applicative code can be obscure or difficult to read. The example given there is

(\x y z -> x*y + y*z + z*x) <$> expr1 <*> expr2 <*> expr3

This code, when translated into an equivalent Applicative comprehension, becomes

[ x*y + y*z + z*x | x <- expr1, y <- expr2, z <- expr3 ]

which has fewer operators and clearer structure, but still bears a strong resemblance to the desugared code, especially when compared with the equivalent ApplicativeDo expression.

In addition to being terse and clear in their own right, ApplicativeComprehensions have some small advantages over the ApplicativeDo extension: the ApplicativeDo transformation as implemented in GHC 8 is an exclusively syntactic translation, which can lead to some unexpected corner cases. For example, the following example code typechecks in GHC 8 with LANGUAGE ApplicativeDo:

-- this typechecks with ApplicativeDo
incrA :: Applicative f => f Int -> f Int
incrA nA = do
  n <- nA
  return (n + 1)

However, the eta-expanded version of the same code _does not_ typecheck, because the ApplicativeDo transformation only happens if the do-notation block ends with a literal invocation of return or pure:

-- this does NOT typecheck with ApplicativeDo
incrA' :: Applicative f => f Int -> f Int
incrA' nA = do
  n <- nA
  (\ x -> return x) (n + 1)

The corresponding problem is impossible to express with ApplicativeComprehensions, because a call to pure or return is always implicitly applied to the return value of the comprehension. The comprehension-based equivalent to incrA is:

incrA'' :: Applicative f => f Int -> f Int
incrA'' nA = [ n + 1 | n <- nA ]

Some Standing Questions

It's possible to desugar ApplicativeComprehensions-compatible expressions that contain guards into expressions with an Alternative constraint, e.g. by translating

[ expr_0 | pat_1 <- expr_1
         , pat_2 <- expr_2
         , guard_expr
         ]

into

(\ pat_1 pat_2 () -> expr_0) <$> expr_1
                             <*> expr_2
                             <*> guard guard_expr

but this would be subject to the same restrictions as before: the guard expression would not be able to reference the variables from any of the other pattern bindings. This doesn't seem as useful as ApplicativeComprehensions in general, but it might be worthwhile to include.

If a given instance of do-notation doesn't satisfy the criteria for ApplicativeDo, then it implicitly is given a Monad constraint instead of an Applicative constraint. Fallback for ApplicativeComprehensions is not as clear, in part because it might be determined by whether a given source file also has MonadComprehensions enabled or not, or whether MonadComprehensions implies ApplicativeComprehensions or vice versa.

Last modified 16 months ago Last modified on Jul 29, 2016 12:38:18 AM