Chad.Scherrer:

...

Ah ha. That'll do. Lesson: avoid hidden space leaks in monads.

Hmm, I'm still missing something. It seems a good lesson, but practically speaking, it doesn't help me any more than saying "write efficient programs". What could I have looked for in the original code to predict it may be leaky? Is there a way of thinking about this that can help me stop hitting space leaks like this?

Normally, you can just profile the code revealing the function that's causing trouble, and then usually the leak is obvious (at least once you've done this a couple of times). Practice helps, as does an understanding of the execution model (see the Spineless Tagless G-machine paper). You really don't know what to look for, I guess, unless you know what `let' versus `case' does at runtime. Here however, it was the `hidden' allocations in the monad that were to blame, so it took a bit more thinking to realise the problem. Profiling told us what function was misbehaving, but glancing at the function didn't reveal anything obvious (except we should have realised that lazily threading StdGen state was going to be a problem, with hindsight). The fact that there is this hidden allocation when you use a state monad is a point to keep in mind - allocation where you don't write the `let' yourself. Have a look at the definition of the State monad to see how the state is actually threaded. There's an interesting comment in the strict ST monad code, fptools/libraries/base/GHC/ST.lhs: > By default the monad is strict; too many people got bitten by > space leaks when it was lazy. Which is what happenened here, I think. For repeated, heavy calls like this, maybe ST (or even IORefs in IO) are more your friends, than State. But, as I say, I think the best way is to get an understanding of the execution model, and get some experience squashing leaks, as they tend to be of very similar form usually, so practice helps.

BTW, I really do appreciate the help. I've been amazed at the level of effort put forth by the Haskell community as a whole to help out newcomers.

No worries! -- Don