[Haskell] Monadic Loops
John Hughes
rjmh at cs.chalmers.se
Fri Jun 18 05:02:53 EDT 2004
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
More information about the Haskell
mailing list