4

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!

Improve this question
4
  • 2
    Stick to a single question at a time, please. (Though, this looks almost exactly like the scenario discussed here: wiki.haskell.org/Stack_overflow) Commented Dec 17, 2018 at 17:47
  • 2
    "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." Programming doesn't work this way. Unless you are happy to get your answer in one of the coming millennia, that is. Commented Dec 17, 2018 at 17:50
  • 1
    Doesn't reproduce. Try compiling your code rather than loading the source to GHCi. Commented Dec 17, 2018 at 17:58
  • The question asks specifically about GHCi. And I think it's reasonable for op to want their code here to Just Work, after all that's what your suggestion to compile with optimizations is essentially. Commented Dec 17, 2018 at 18:20

1 Answer 1

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

thanks, I now understand why lazyness 'creates' a huge expression in this case, and how Seq can solve this. Thansk man! very useful answer!
thanks again for your previous answer. However I have a doubt now. Running GHCi with the flag ":set +s" to see execution time and memory usage, I see that the program newsum' is still using a linear (in n) amount of memory: try 10000, 100000 and 1000000. How is this possible? How can I really get a constant-space function ? Thanks!
@makkiato :set +s outputs total allocations over the whole evaluation, not peak memory usage (I use top or htop in another terminal to visualize that)
@makkiato the difference between the versions, is that the strict one can garbage collect the allocations as it goes along, instead of only at the very end

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.