How to avoid stack space overflows?

Question

I've been a bit surprised by GHC throwing stack overflows if I'd need to get value of large list containing memory intensive elements. I did expected GHC has TCO so I'll never meet such situations.

To most simplify the case look at the following straightforward implementations of functions returning Fibonacci numbers (taken from HaskellWiki). The goal is to display millionth number.

import Data.List

# elegant recursive definition
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

# a bit tricky using unfoldr from Data.List
fibs' = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)

# version using iterate
fibs'' = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

# calculate number by definition
fib_at 0 = 0
fib_at 1 = 1
fib_at n = fib_at (n-1) + fib_at (n-2)

main = do
    {-- All following expressions abort with
        Stack space overflow: current size 8388608 bytes.
        Use `+RTS -Ksize -RTS' to increase it.
     --}
    print $ fibs !! (10^6)
    print . last $ take (10^6) fibs
    print $ fibs' !! (10^6)
    print $ fibs'' !! (10^6)

    -- following expression does not finish after several 
    -- minutes
    print $ fib_at (10^6)

The source is compiled with ghc -O2.

What am I doing wrong ? I'd like to avoid recompiling with increased stack size or other specific compiler options.

Answer 1

These links here will give you a good introduction to your problem of too many thunks (space leaks).

If you know what to look out for (and have a decent model of lazy evaluation), then solving them is quite easy, for example:

{-# LANGUAGE BangPatterns #-}                        

import Data.List                                     

fibs' = unfoldr (\(!a,!b) -> Just (a,(b,a+b))) (0,1) 

main = do                                            
    print $ fibs' !! (10^6)  -- no more stack overflow