Recursive Do Notation

Brief Explanation

An extended form of do notation allowing value recursion (or feedback) for monads in the MonadFix class.

References

• papers
• GHC documentation
• Arrows

Tickets

#64	add recursive do syntax

Variations

Using mfix adds a MonadFix constraint, and also affects the semantics for some monads, so a key choice is how mfix is introduced. As an experiment, two syntaxes are implemented in GHC, both for do-notation and arrow notation. It would clearly be preferable if there was only one variant of recursive do, even if arrow notation is not adopted.

Implicit recursion

(as implemented in GHC and Hugs)

A dependency analysis is performed over the list of statements, and minimal subsequences of interdependent statements are translated using mfix. That is, a variable used before it is bound is treated as recursively defined, while in a Haskell 98 do-statement it would be treated as shadowed.

To retain backwards compatibility, existing implementations use a different keyword (mdo) for expressions treated in this way, and always add a MonadFix constraint to these expressions. If the keyword mdo is not suggestive enough (see below) a new keyword (recdo?) could be chosen. An alternative is to extend the ordinary do-notation, sacrificing backwards compatibility. In that case, the MonadFix constraint would be added only if a recursive binding was present.

Cons

• either use another keyword for a second kind of do-statement, or break backwards compatibility. Opinion is divided on the value of variable shadowing.
• a dependency analysis is required to determine the semantics, making it significantly more difficult to understand the desugaring.

(The same approaches also work for arrow notation, with the same trade-offs.)

Explicit recursion

(as implemented in the do part of arrow notation and also in plain do in GHC with -farrows)

Add to the current do-notation a new rec statement containing a sequence of mutually recursive statements. The rec keyword is a bit more suggestive of its meaning than mdo. The extent of the recursion is explicit, though implementations can trim non-recursive variables from the feedback set without changing the semantics.

Cons

• contrasts with let/where bindings, in which recursion is implicit.
• rec is a common identifier.

Comment

For the purpose of this discussion, there are two classes of monads/arrows: those that support recursion, and those that don't. By contrast, recursion in a where or let is always a possibility. This suggests two different keywords, do and e.g. recdo to clearly signal the intent. recdo could most likely be made to work for the arrow syntax as well, even if the "do" in the keyword has imperative connotations that wouldn't necessarily be appropriate (e.g. when declaratively specifying a network of stream processors or signal functions). Maybe an even better keyword would be found.

Pros

• makes programs much more readable that the equivalent forms using mfix.

Cons

• the candidate syntaxes have different drawbacks (see above)