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!
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With