# Recursive Do Notation

## Brief Explanation

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

#64

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