The recursive do-notation (also known as mdo-notation) is implemented as described in: “A recursive do for Haskell”, Levent Erkök and John Launchbury, Haskell Workshop 2002, pages: 29–37. Pittsburgh, Pennsylvania.

The do-notation of Haskell does not allow recursive bindings, that is, the variables bound in a do-expression are visible only in the textually following code block. Compare this to a let-expression, where bound variables are visible in the entire binding group. It turns out that several applications can benefit from recursive bindings in the do-notation, and this extension provides the necessary syntactic support.

Here is a simple (yet contrived) example:

import Control.Monad.Fix

justOnes = mdo xs <- Just (1:xs)
               return xs

As you can guess justOnes will evaluate to Just [1,1,1,...

The Control.Monad.Fix module introduces the MonadFix class, defined as

class Monad m => MonadFix m where
    mfix :: (a -> m a) -> m a

The function mfix dictates how the required recursion operation should be performed. If recursive bindings are required for a monad, then that monad must be declared an instance of the MonadFix class. For details, see the above mentioned reference.

The Control.Monad.Fix module also defines instances of MonadFix for lists, Maybe and IO. Furthermore, several other monad modules provide instances of the MonadFix class, including the Control.Monad.ST and Control.Monad.ST.Lazy modules for Haskell's internal state monad (strict and lazy, respectively).

There are three important points in using the recursive-do notation:

The web page: “http://www.cse.ogi.edu/PacSoft/projects/rmb” contains up to date information on recursive monadic bindings.

Parallel list comprehensions are a natural extension to list comprehensions. List comprehensions can be thought of as a nice syntax for writing maps and filters. Parallel comprehensions extend this to include the zipWith family.

A parallel list comprehension has multiple independent branches of qualifier lists, each separated by a “|” symbol. For example, the following zips together two lists:

[ (x, y) | x <- xs | y <- ys ]

The behavior of parallel list comprehensions follows that of zip, in that the resulting list will have the same length as the shortest branch.

We can define parallel list comprehensions by translation to regular comprehensions. Given a parallel comprehension of the form:

[ e | p1 <- e11, p2 <- e12, ...
    | q1 <- e21, q2 <- e22, ...
    ...
]

This will be translated to:

[ e | ((p1,p2), (q1,q2), ...) <- zipN [(p1,p2) | p1 <- e11, p2 <- e12, ...]
                                      [(q1,q2) | q1 <- e21, q2 <- e22, ...]
                                      ...
]

where “zipN” is the appropriate zip for the given number of branches. These functions must be in scope; the Prelude defines zip and zip3, but if you want to handle 4 or more lists in parallel, you will need to import List or Data.List.