haskell / 9 / users_guide / exts / applicative_do.html

6.2.4. Applicative do-notation

ApplicativeDo
Since: 8.0.1

Allow use of Applicative do notation.

The language option ApplicativeDo enables an alternative translation for the do-notation, which uses the operators <$>, <*>, along with join as far as possible. There are two main reasons for wanting to do this:

  • We can use do-notation with types that are an instance of Applicative and Functor, but not Monad
  • In some monads, using the applicative operators is more efficient than monadic bind. For example, it may enable more parallelism.

Applicative do-notation desugaring preserves the original semantics, provided that the Applicative instance satisfies <*> = ap and pure = return (these are true of all the common monadic types). Thus, you can normally turn on ApplicativeDo without fear of breaking your program. There is one pitfall to watch out for; see Things to watch out for.

There are no syntactic changes with ApplicativeDo. The only way it shows up at the source level is that you can have a do expression that doesn’t require a Monad constraint. For example, in GHCi:

Prelude> :set -XApplicativeDo
Prelude> :t \m -> do { x <- m; return (not x) }
\m -> do { x <- m; return (not x) }
  :: Functor f => f Bool -> f Bool

This example only requires Functor, because it is translated into (\x -> not x) <$> m. A more complex example requires Applicative,

Prelude> :t \m -> do { x <- m 'a'; y <- m 'b'; return (x || y) }
\m -> do { x <- m 'a'; y <- m 'b'; return (x || y) }
  :: Applicative f => (Char -> f Bool) -> f Bool

Here GHC has translated the expression into

(\x y -> x || y) <$> m 'a' <*> m 'b'

It is possible to see the actual translation by using -ddump-ds, but be warned, the output is quite verbose.

Note that if the expression can’t be translated into uses of <$>, <*> only, then it will incur a Monad constraint as usual. This happens when there is a dependency on a value produced by an earlier statement in the do-block:

Prelude> :t \m -> do { x <- m True; y <- m x; return (x || y) }
\m -> do { x <- m True; y <- m x; return (x || y) }
  :: Monad m => (Bool -> m Bool) -> m Bool

Here, m x depends on the value of x produced by the first statement, so the expression cannot be translated using <*>.

In general, the rule for when a do statement incurs a Monad constraint is as follows. If the do-expression has the following form:

do p1 <- E1; ...; pn <- En; return E

where none of the variables defined by p1...pn are mentioned in E1...En, and p1...pn are all variables or lazy patterns, then the expression will only require Applicative. Otherwise, the expression will require Monad. The block may return a pure expression E depending upon the results p1...pn with either return or pure.

Note: the final statement must match one of these patterns exactly:

  • return E
  • return $ E
  • pure E
  • pure $ E

otherwise GHC cannot recognise it as a return statement, and the transformation to use <$> that we saw above does not apply. In particular, slight variations such as return . Just $ x or let x = e in return x would not be recognised.

If the final statement is not of one of these forms, GHC falls back to standard do desugaring, and the expression will require a Monad constraint.

When the statements of a do expression have dependencies between them, and ApplicativeDo cannot infer an Applicative type, it uses a heuristic algorithm to try to use <*> as much as possible. This algorithm usually finds the best solution, but in rare complex cases it might miss an opportunity. There is an algorithm that finds the optimal solution, provided as an option:

-foptimal-applicative-do
Since: 8.0.1

Enables an alternative algorithm for choosing where to use <*> in conjunction with the ApplicativeDo language extension. This algorithm always finds the optimal solution, but it is expensive: O(n^3), so this option can lead to long compile times when there are very large do expressions (over 100 statements). The default ApplicativeDo algorithm is O(n^2).

6.2.4.1. Strict patterns

A strict pattern match in a bind statement prevents ApplicativeDo from transforming that statement to use Applicative. This is because the transformation would change the semantics by making the expression lazier.

For example, this code will require a Monad constraint:

> :t \m -> do { (x:xs) <- m; return x }
\m -> do { (x:xs) <- m; return x } :: Monad m => m [b] -> m b

but making the pattern match lazy allows it to have a Functor constraint:

> :t \m -> do { ~(x:xs) <- m; return x }
\m -> do { ~(x:xs) <- m; return x } :: Functor f => f [b] -> f b

A “strict pattern match” is any pattern match that can fail. For example, (), (x:xs), !z, and C x are strict patterns, but x and ~(1,2) are not. For the purposes of ApplicativeDo, a pattern match against a newtype constructor is considered strict.

When there’s a strict pattern match in a sequence of statements, ApplicativeDo places a >>= between that statement and the one that follows it. The sequence may be transformed to use <*> elsewhere, but the strict pattern match and the following statement will always be connected with >>=, to retain the same strictness semantics as the standard do-notation. If you don’t want this, simply put a ~ on the pattern match to make it lazy.

6.2.4.2. Things to watch out for

Your code should just work as before when ApplicativeDo is enabled, provided you use conventional Applicative instances. However, if you define a Functor or Applicative instance using do-notation, then it will likely get turned into an infinite loop by GHC. For example, if you do this:

instance Functor MyType where
    fmap f m = do x <- m; return (f x)

Then applicative desugaring will turn it into

instance Functor MyType where
    fmap f m = fmap (\x -> f x) m

And the program will loop at runtime. Similarly, an Applicative instance like this

instance Applicative MyType where
    pure = return
    x <*> y = do f <- x; a <- y; return (f a)

will result in an infinite loop when <*> is called.

Just as you wouldn’t define a Monad instance using the do-notation, you shouldn’t define Functor or Applicative instance using do-notation (when using ApplicativeDo) either. The correct way to define these instances in terms of Monad is to use the Monad operations directly, e.g.

instance Functor MyType where
    fmap f m = m >>= return . f

instance Applicative MyType where
    pure = return
    (<*>) = ap

© 2002–2007 The University Court of the University of Glasgow. All rights reserved.
Licensed under the Glasgow Haskell Compiler License.
https://downloads.haskell.org/~ghc/9.4.2/docs/users_guide/exts/applicative_do.html