Version 7 (modified by 12 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)