How to avoid stack overflow in Haskell?

Question

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?

@Swiss Yes, it's tail-recursive, but the stack that's growing isn't the stack you think is growing. — Daniel Wagner
– Daniel Wagner, Commented Sep 23, 2011 at 20:44

Daniel Wagner · Accepted Answer · 2011-09-23 20:43:38Z

38

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.

answered Sep 23, 2011 at 20:43

Daniel Wagner

156k10 gold badges231 silver badges392 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Daniel Wagner Over a year ago

P.S. Credit here goes to Brent Yorgey, who helped me debug an almost identical error in some of my code almost three years ago.

Collectives™ on Stack Overflow

How to avoid stack overflow in Haskell?

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related