What causes a "C error stack overflow" in haskell usually

Question

What are the common causes of C errors in a Hugs Haskell implementation.

Answer 1

This can occur if you are used to functional languages ​​that usually use tail recursion factorization. Let's say you have a function:

sum = go 0 where go accum [] = accum go accum (x:xs) = go (accum+x) xs 

Which, incidentally, coincides with

 sum = foldl (+) 0 

If we evaluate the function, we can see the problem:

 sum [1,2,3,4] go 0 [1,2,3,4] go (0+1) [2,3,4] go ((0+1)+2) [3,4] go (((0+1)+2)+3) [4] go ((((0+1)+2)+3)+4) [] (((0+1)+2)+3)+4 

Now, to evaluate this expression, Haskell uses the stack:

 EXPR | STACK (((0+1)+2)+3)+4 | ((0+1)+2)+3 | +4 (0+1)+2 | +3 +4 (0+1) | +2 +3 +4 1 | +2 +3 +4 3 | +3 +4 6 | +4 10 | 

And overflow can occur here. If you estimated the sum [1,10 ^ 6], this stack will have a depth of one million records.

But pay attention to the pathology here. You rewrite the list only to create a huge fscking ("thunk") expression, and then use the stack to evaluate it. We would rather evaluate it when we recurs by making tail recursion strict:

 sum = go 0 where go accum [] = accum go accum (x:xs) = accum `seq` go (accum+x) xs 

This suggests evaluating the accuracies before trying to evaluate the recursive call, so we get (it may take some patience to understand):

 sum [1,2,3,4] go 0 [1,2,3,4] let accum = 0 in accum `seq` go (accum+1) [2,3,4] go (0+1) [2,3,4] let accum = 0+1 in accum `seq` go (accum+2) [3,4] go (1+2) [3,4] let accum = 1+2 in accum `seq` go (accum+3) [4] go (3+3) [4] let accum = 3+3 in accum `seq` go (accum+4) [] go (6+4) [] 6+4 10 

So, when we go through the list, we calculate the amount, so we do not need to use a deep stack to evaluate the result. This modified tail recursion pattern is encapsulated in Data.List.foldl ', therefore:

 sum = foldl' (+) 0 

A good rule of thumb is to never use foldl because it always creates gigantic tricks. Use foldl 'instead. If the output type has a lazy structure (such as a list or function), use foldr. But there is no silver bullet to avoid altogether, you just need to understand the behavior of your program. Sometimes it can be tricky.

But, if I understand correctly, stack overflow always arises from an attempt to evaluate a giant piece. Therefore, find the places where they can be created, and so that the evaluation of effectiveness occurs earlier.

Answer 2

Fluent recursion is the most likely candidate ... You need to give more information, although for a more accurate answer.

Answer 3

Here is the code that can cause runaway recursion:

 main = let x = x :: Int in print x 

What happens is that when x is evaluated in print x , it starts up and then finds out that to complete its evaluation, it needs to evaluate x .

Answer 4

The most likely cause should be uncontrolled recursion. Each recursive call consumes a bit more stack space for I / O parameters.