Stack space overflow when calculating prime numbers

Question

I work through Real World Haskell (I'm in Chapter 4) and practice a little outside the book. I created the following program to calculate the nth number.

import System.Environment isPrime primes test = loop primes test where loop (p:primes) test | test `mod` p == 0 = False | p * p > test = True | otherwise = loop primes test primes = [2, 3] ++ loop [2, 3] 5 where loop primes test | isPrime primes test = test:(loop primes' test') | otherwise = test' `seq` (loop primes test') where test' = test + 2 primes' = primes ++ [test] main :: IO() main = do args <- getArgs print(last (take (read (head args) :: Int) primes)) 

Obviously, since I keep a list of primes, this is not a permanent spatial solution. The problem is when I try to get a very big right word ./primes 1000000 I get an error:

  Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase 

I am sure I returned the tail correctly; reading http://www.haskell.org/haskellwiki/Stack_overflow , and the various answers here lead me to believe that this is a by-product of a lazy assessment, and the blood clots increase until it overflows, but still I was not successful in correcting it. I tried to use seq in different places for a forced evaluation, but this did not affect. Am I on the right track? Is there anything else I am not getting?

Answer 1

As I said in my comment, you should not create a list by adding one list of elements to the end of a very long list (your line is primes' = primes ++ [test] ). It’s better to just define an endless list of primes , and let a lazy rating do it. Something like the code below:

 primes = [2, 3] ++ loop 5 where. loop test | isPrime primes test = test:(loop test') | otherwise = test' `seq` (loop test') where test' = test + 2 

Obviously, you don't need to parameterize the isPrime function to primes , but it's just nit. In addition, when you know that all numbers are positive, you should use rem instead of mod - this leads to an increase in productivity on my machine by 30% (when looking for a millionth simple).

Answer 2

Firstly, there is no tail recursion, but guarded recursion, aka tail recursion modulo minus .

The reason you get stack overflows is because, as others commented, a bunch of storage. But where? One possible culprit is your use of (++) . Although this is not optimal, using (++) does not necessarily lead to thunk overflow and stack overflow. For example, calling

 take 2 $ filter (isPrime primes) [15485860..] 

should produce [15485863,15485867] as soon as possible and without. But this is all the same code that uses (++) , right?

The problem is that you have two lists that you call primes . One (at the top level) is infinite, co-recursively created through guarded (rather than tail) recursion. The other ( loop argument) is the final list, constructed by adding each newly found stroke to its end, used for testing.

But when it is used for testing, it does not drag out to the end. If this happened, there would be no SO problem. Runs only for sqrt test number . Thus, (++) thunks accumulate in the past.

When isPrime primes 15485863 , it forces the top level of primes to 3935 , which is 547 primes. The list of internal test samples also consists of 547 primes, of which only the first 19 are forced.

But when you call primes !! 1000000 primes !! 1000000 , out of 1,000,000 primes in the duplicate internal list, only 547 are forced. The rest are all in bogs.

If you added new primes to the end of the testing-primes list only when their square was seen among the candidates, the testing-primes list would always be forced completely or almost to the end, and there would be no fist calling SO. And adding (++) to the end of the forced list is not so bad when the next access causes this list to end and leaves no tricks. (He is still copying the list.)

Of course, the top-level primes list can be used directly, as Thomas M. Dubuison shows in his answer.

But the internal list has its uses. When this is correctly implemented, adding new primes to it only when their square is displayed among the candidates, it can allow your program to work in O(sqrt(n)) space when compiling with optimization.

Answer 3

You should probably check these two questions:

• How to increase stack size with runhaskell?
• How to avoid stack space overflow?