Version 6 (modified by ross@…, 10 years ago) (diff)

--

# Recursive Do Notation

## Brief Explanation

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

## 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.

## Pros

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

## Cons

• the candidate syntaxes have different drawbacks (see above)