Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

*** Exception: stack overflow : Stack overflow

Tags:

haskell

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!

like image 702
makkiato Avatar asked Oct 15 '25 04:10

makkiato


1 Answers

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.

like image 53
Claude Avatar answered Oct 17 '25 22:10

Claude



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!