Haskell: repeat a function a large number of times without stackoverflow

Question

As a newbie to Haskell I am trying to iterate a function (e.g., the logistic map) a large number of times. In an imperative language this would be a simple loop, however in Haskell I end up with stack overflow. Take for example this code:

main  = print $ iter 1000000

f x = 4.0*x*(1.0-x)

iter :: Int -> Double
iter 0 = 0.3
iter n = f $ iter (n-1)

For a small number of iterations the code works, but for a million iterations I get a stack space overflow:

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

I cannot understand why this does happen. The tail recursion should be fine here. Maybe the problem is lazy evaluation. I experimented with several ways to force strict evaluation, by inserting $! or seq at various positions, but with no success.

What would be the Haskell way to iterate a function a huge number of times?

I have tried suggestions from related posts: here or here, but I always ended up with stackoverflow for a large number of iterations, e.g., main = print $ iterate f 0.3 !! 1000000.

Answer 1

The problem is that your definition

iter :: Int -> Double
iter 0 = 0.3
iter n = f $ iter (n-1)

tries to evaluate in the wrong direction. Unfolding it for a few steps, we obtain

iter n = f (iter (n-1))
       = f (f (iter (n-2)))
       = f (f (f (iter (n-3))))
       ...

and the entire call stack from iter 1000000 to iter 0 has to be built before anything can be evaluated. It would be the same in a strict language. You have to organise it so that part of the evaluation can take place before recurring. The usual way is to have an accumulation parameter, like

iter n = go n 0.3
  where
    go 0 x = x
    go k x = go (k-1) (f x)

Then adding strictness annotations - in case the compiler doesn't already add them - will make it run smoothly without consuming stack.

The iterate variant has the same problem as your iter, only the call stack is built inside-out rather than outside-in as for yours. But since iterate builds its call-stack inside-out, a stricter version of iterate (or a consumption pattern where earlier iterations are forced before) solves the problem,

iterate' :: (a -> a) -> a -> [a]
iterate' f x = x `seq` (x : iterate' f (f x))

calculates iterate' f 0.3 !! 1000000 without problem.