Previously: #2435. Seems to have been closed for lack of a proper proposal; having a proof of concept changes that, presumably..?

@hdgarrood I think so, yes. This PR implements exactly what was discussed in that issue. I can write up a proposal that matches it and then we can see how it works out immediately.

I think this documents the behavior of this PR quite well, with rationale for each deviation from GHC (which is quite a lot lol):

Applicative do-notation

The benefits of applicative do-notation are documented elsewhere. This proposal is about the specific implementation in PureScript. This proposal uses (<*>) several times, for ease of reading. The actual implementation does not use these; instead it uses apply.

Differences from GHC

GHC implements applicative do-notation. This proposal adds applicative do-notation to PureScript, with two important differences:

1. The desugaring is opt-in rather than applied to every do-block.
2. The implemenation described in this proposal addresses only those computations that use only applicative combinators. To mix in computations that depend on each other's results, one needs to resort to monadic do-notation (which may be nested inside applicative do-notation, and vice versa). A future proposal may extend this implementation to allow the use of bind, although that may interfere with the opt-in syntax.

Syntax

The syntax of applicative do-notation differs from that of monadic do-notation in two aspects. It is otherwise the same.

Opt-in applicative desugaring

Due to strict evaluation, it is not preferred to transform any do expression into an applicative computation whenever the types would allow this. Efficiency and termination could suffer due to the lack of thunking. Consider:

f 0 = pure 0
f n = do
  x <- a
  y <- f (n - 1)
  pure $ x + y

If this were translated to applicative combinators, f n = pure (+) <*> a <*> f (n - 1), it would not work as expected because the second argument to (<*>) is immediately evaluated.

Therefore this proposal adds a new keyword ado that complements do. Monadic do-notation will remain entirely unchanged.

No special interpretation of pure

It is not desired to interpret application of the pure function specially. This would incur problems with higher-order combinators such as $:

ado
  x <- a
  y <- b
  pure $ x y -- application of ($), not of pure

Instead, we use the in keyword, as suggested by @ElvishJerricco. This is mandatory and must be and must be only the last statement in the applicative do-block. It can be compared with the yield keyword in Scala.

ado
  x <- a
  y <- b
  in x y

Desugaring procedure

An applicative do-block is desugared into a map followed by a series of apply applications, or sometimes a single pure application.

This desugaring procedure is systematic, according to the following rules:

1. For each statement, in order:
   1. For each bind statement, the result expression is wrapped by a lambda abstraction that receives the result of the bind statement. The parameter of this lambda abstraction is the binder of the bind statement.
   2. For each value statement, the result expression is wrapped by a lambda abstraction that receives nothing. The parameter of this lambda abstraction is the null binder.
   3. For each let statement, the result expression is wrapped by a corresponding let expression. The value of the let expression may use values from previous bind and let statements.
2. Put everything together:
   1. If there are no non-let statements in the applicative do-block: App pure result.
   2. Otherwise, insert map and apply as appropriate.

Some examples:

ado
  in h x
-- desugars into
pure (h x)

------------------------------

ado
  x <- g
  in f x
-- desugars into
(\x -> f x) <$> g

------------------------------

ado
  x <- g
  y <- h
  in f x y
-- desugars into
(\x y -> f x y) <$> g <*> h

------------------------------

ado
  x <- g
  h
  in f x
-- desugars into
(\x _ -> f x) <$> g <*> h

------------------------------

ado
  x <- g
  let y = x + 1
  h
  in f x y
-- desugars into
(\x -> let y = x + 1 in \_ -> f x y) <$> g <*> h

------------------------------

-- and so on

Open issues

• Instead of making the syntax opt-in, make (<*>) take thunks as arguments.

Thanks for the PR and the detailed explanation!

I have a few comments:

• It seems like let can only be desugared if the bound names are only used in the result, not the intermediate computations.
• Can you please add an example where the computations on the RHS of <- have different types? That way we can make sure they're being applied in the right order.
• The use of pure/apply is probably nicer in terms of codegen, but unfortunately means we can't use ado with just an Apply (we always need a full Applicative)

And one random thought:

• It might be nice to have a variant of ado (and do for that matter) which supports recursion using Lazy.

This is a relatively benign change, but we should be sure to test it thoroughly. It's also breaking since it reserves a new keyword, so it'd have to go into 1.0 at the earliest.

@paf31 Thank you for the comments. I will now comment on them.

• let x = y could be desugared to x <- pure y, or could be inlined into the generated lambdas.
• Yes, I will. The order of sequencing is already checked by main (through Ref), and so is the order of application of apply (also by main, because it must print "Done", not "enoD" or something like that). I will add a test with different types anyway.
• That's right, it is not difficult to use (<$>) in place of pure. It may also be more efficient.

I figured out a way to get something like ApplicativeDo using just rebindable syntax:

http://try.purescript.org/?gist=91c8c58419ec2683d46b8d83eb88614c

So we should consider whether it's worth new code in the compiler if we can get 90% of the feature as a library.

To compare the two, this approach requires you to rebind bind and discard (or use _ <-) and the syntax is slightly less nice.

Edit: actually, this code illustrates exactly why ApplicativeDo is useful, since the name and email fields are the wrong way round :(

@rightfold Could you please rebase this one?

@paf31 On it!

Thanks!