[Haskell-cafe] Re: Remember the future

[Benjamin Franksen]

Andrew Coppin wrote:
> Surely all this means is that the magical "mdo" keyword makes the 
> compiler arbitrarily reorder the expression...?

It is not magical but simple syntactic sugar. And no, the compiler does
not 'arbitrarily reorder' anything, you do the same in any imperative
language with pointers/references and mutation.

>From the ghc manual:

-----------
7.3.3. The recursive do-notation
...
 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 library introduces the MonadFix class. It's
definition is: 
class Monad m => MonadFix m where
   mfix :: (a -> m a) -> m a
-----------

It is unfortunate that the manual does not give the translation rules, or at
least the translation for the given example. If I understood things
correctly, the example is translated to

justOnes = mfix (\xs' -> do { xs <- Just (1:xs'); return xs }

You can imagine what happens operationally by thinking of variables as
pointers. As long as you don't de-reference them, you can use such pointers
in expressions and statements even if the object behind them has not yet
been initialized (=is undefined). The question is how the objects are
eventually be initialized. In imperative languages this is done by
mutation. In Haskell you employ lazy evaluation: the art of circular
programming is to use not-yet-defined variables lazily, that is, you must
never demand the object before the mdo block has been executed.

A good example is http://www.cse.ogi.edu/PacSoft/projects/rmb/doubly.html
which explains how to create a doubly linked circular list using mdo.

Cheers
Ben