How to avoid stack overflow in Haskell?

问题:

Haskell does not support cycling for computation, instead it offers to use recursion algorithms. But this approach leads to growing of stack, and even stack overflow. I believe there should be approach to solve this problem in general. Here is the sample. I wanted to know, how many times getClockTime may be called per 5 seconds:

import System.Time

nSeconds = 5

main = do
    initTime <- totalPicoSeconds `fmap` getClockTime
    doWork initTime 1
    where
    doWork initTime n = do
        currTime <- totalPicoSeconds `fmap` getClockTime
        if (currTime - initTime) `div` 10 ^ 12 >= nSeconds
            then print n
            else doWork initTime (n+1)

totalPicoSeconds :: ClockTime -> Integer
totalPicoSeconds (TOD a b) = a * 10 ^ 12 + b

The program goes 5 seconds, but eventually I'm getting:

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

Manual management of stack size may help in particular case, but if I would wish to run this algo for 10 seconds, it may overflow again. So this is not a solution. How can I get this code working?

回答1:

The problem here is not the recursion, but the laziness of your n argument. Stack overflows in Haskell come from trying to evaluate deeply-nested thunks; in your case, each call to doWork initTime (n+1) is making a slightly-deeperly-nested thunk in the second argument. Simply make it strict, and things should be happy again: doWork initTime $! n+1.