[Haskell] Monadic Loops

[John Hughes]

Vivian McPhail wrote:

>Hi, 
>
>I've implemented a Neural Net simulator which needs to repeat a training loop many times. For this I used a while function: 
>
>while test body = do
>                  (cond,res) <- body
>                  if (test cond) then do rs <- while test body
>                                      return (res:rs)
>                  else return [res]
>However, when I run the program, the interpreter falls over after a few thousand iterations, running out of space. I think that this is because the Monadic implementation of the while loop actually nests functions of type (a -> M b) and there is a maximum ?stack size. 
>
>  
>
As others have pointed out, the problem is that while is not tail 
recursive, so the stack frame for return (res:rs) remains on the stack 
during the recursive call: result, you run out of stack.

However, this only happens because the monad you are using is strict -- 
or rather, the implementation of (>>=) is strict. If you use a monad 
with a lazy bind operator instead, then the recursive call will not be 
evaluated initially, just bound to rs, and evaluated when rs is used by 
the called, AFTER the return (res:rs). Result: no deep stack.

The advantage of doing this is that the elements of the list are 
available lazily as they are constructed, and so can be consumed as they 
are generated. Your solution (using a strict monad), and the tail 
recursive solution you've been offered, both build the entire list 
before returning it to the caller. If you are performing many thousands 
of recursions, and the list points at large structures, then this may 
give you a problematic space leak.

The ST monad comes in strict and lazy versions. Provided that's the 
monad you're using, or a monad built on top of it, you can switch to the 
lazy version just by importing Control.Monad.ST.Lazy instead of 
Control.Monad.ST. Documentation is here:

    
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control.Monad.ST.Lazy.html

If you are using the IO monad, then you achieve the same effect by 
wrapping the recursive call in unsafeInterleaveIO from System.IO.Unsafe. 
That will delay its evaluation until rs is evaluated, once again AFTER 
the enclosing call has returned. But that is -- well -- unsafe.

John Hughes

PS You can read about lazy state here:

http://portal.acm.org/citation.cfm?id=178246&coll=portal&dl=ACM&CFID=22769016&CFTOKEN=85305111