while test body = do (cond,res) <- body if (test cond) then do rs <- while test body return (res:rs) else return [res]

do you need the monad here? what monad is it? the problem could to be that the "return $ res: rs" can happen only after it is certain that "while test body" succeeds. so you won't even see the very first cons cell before the last one is evaluated. could you produce a (lazy) list of results instead? the garbage collector might be able to collect the list cells that are no longer needed possibly, a lazy state monad would help (if the computation of "while test body" cannot fail)

Is there a better way to implement (possibly infinite) loops in Haskell?

generally, don't program your own recursions - use pre-defined combinators instead. (I like to think of this as a "higher analogon" of "don't use goto - use block structures" from imperative programming) if you need monads, have a look at sequence, sequence_, mapM, mapM_ http://www.haskell.org/onlinereport/monad.html if you can do with lists, then use iterate, fold etc. http://www.haskell.org/onlinereport/list.html best regards, -- -- Johannes Waldmann, Tel/Fax: (0341) 3076 6479 / 6480 -- ------ http://www.imn.htwk-leipzig.de/~waldmann/ ---------

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.... 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=2276901...