*** Exception: stack overflow : Stack overflow

Question

I am learning Haskell and I am getting an exception "stack overflow" I was not expecting.

The code is fairly simple:

type Reals = Double

prod :: Reals -> Reals -> Reals
prod a b = a*b

coprod :: Reals -> Reals -> Reals
coprod a b = a + b - (prod a b)

newsum :: Reals -> Reals -> Int -> Reals
newsum a b n =   
    approxA!!n 
    where
      approxA = a : zipWith coprod approxA approxB 
      approxB = b : zipWith prod approxA approxB 

The functions prod, coprod are intended to be evalated on reals in [0,1]. The function

newsum a b n

for n going to infinity, computes the function (a,b) -> min(1, a+b).

You can try

newsum 0.5 0.5 10

and

newsum 0.5 0.5 10000

to see this. However, by calling

newsum 0.5 0.5 10000000

I get a stack overflow. The newsum function is simple and makes a linear (in n) number of operations of Double type. In other words, the construction n-th element of the(infinite) lists of type [Reals]

approxA

and

approxB

takes linear time.

QUESTION 1: Why am I getting the stack overflow? | What are the limits of Haskell (or GHCi) and how can I estimate them (in advance) in a simple program like the one above?

QUESTION 2: Is there a flag/command in Haskell to instruct the interpreter to page the memory automatically, if needed? I want to write code that resemble Math, and don't want to spend time thinking about memory limits, stack overflows and stuff like that.

thanks!

Answer 1

The problem is that (!!) is lazy: it doesn't force earlier values in the list to be evaluated, so ghci ends up with a huge expression for the nth item, which overflows its stack.

You can increase the stack size with run time options, eg for a 16GB stack:

$ ghci +RTS -K16G
> newsum 0.5 0.5 10000000
0.9999999000001789

But if you exceed the memory available to your system (which can include virtual memory / swap pages), you will have problems (here the Linux OOM killer struck me down):

> newsum 0.5 0.5 100000000
Killed
$

This can be fixed in practice by writing a function that forces each head of the list to be evaluated before its tail can be accessed:

strict :: [a] -> [a]
strict [] = []
strict (x:xs) = seq x (x : strict xs)

seq x y forces x to be evaluated (to WHNF, which for Double means fully-evaluated) when the value of y is demanded. Use strict like this:

newsum' :: Reals -> Reals -> Int -> Reals
newsum' a b n =
    strict approxA!!n
    where
      approxA = a : zipWith coprod approxA approxB
      approxB = b : zipWith prod approxA approxB

Now it runs in small constant memory.

An alternative is to use a stricter data structure (the !a is a strict a):

data List' a = !a :! List' a

but then you need to reimplement (!!) and zipWith for this type.