Version 7 (modified by ross@…, 9 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.

## References

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

## Pros

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

## Cons

- the candidate syntaxes have different drawbacks (see above)