当计算素数时堆栈空间溢出

Question

我正在通过真实世界Haskell（我在第4章）中工作，并且练习了一下我创建了以下程序来计算第n个素数。

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)) 

很明显，既然我保存了素数列表，这不是一个恒定的空间解决方案。问题是，当我试图得到一个非常大的素说./primes 1000000我收到的错误：

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

我相当肯定，我得到了尾递归权利;阅读http://www.haskell.org/haskellwiki/Stack_overflow，这里的各种回应让我相信它是懒惰评价的副产品，而且它正在积累，直到它溢出，但到目前为止，我一直未能解决它。我试过在各个地方使用seq来强制评估，但没有产生效果。我在正确的轨道上吗？还有什么我没有得到？

Answer 1

正如我在我的评论说，你不应该通过附加一个单一的元素列表建立一个列表到一个非常长的列表末尾（您的行primes' = primes ++ [test]）。最好定义无限列表，primes，让懒惰的评估做它的事情。像下面的代码：

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

很明显，你不需要通过primes无论是参数化isPrime功能，但是这只是一个挑剔。此外，当你知道所有的数字都是正数时，你应该使用rem而不是mod--这会导致我的机器性能提高30％（找到第一百万个素数时）。

Answer 2

你或许应该检查这两个问题：

1. How can I increase the stack size with runhaskell?
2. How to avoid stack space overflows?

Answer 3

首先，您在这里没有尾递归，但守护递归，又名tail recursion modulo cons。

正如其他人评论的那样，堆栈溢出的原因是thunk堆积。但是哪里？一个建议的罪魁祸首是您使用(++)。尽管不是最佳的，但使用(++)不一定导致thunk堆积和堆栈溢出。例如，调用

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

应该在任何时间产生[15485863,15485867]，且无任何堆栈溢出。但它仍然是使用(++)的代码，对吧？

的问题是，你有列出你叫primes。一个（在顶层）是无限的，通过守护（而非尾）递归共同递归产生。另一个（loop的参数）是一个有限列表，通过将每个新发现的素数添加到其末尾来构建，用于测试。

但是，当它用于测试时，它不会被迫通过它的结尾。如果发生这种情况，那么就不存在这样的问题。 它只能通过测试号的sqrt。所以(++) thunk克服了这一点。

当调用isPrime primes 15485863时，它会强制顶级primes高达3935，这是547个素数。内部测试素数列表也由547个素数组成，其中只有前19个是强制的。

但是，当您拨打primes !! 1000000时，重复内部列表中的1,000,000个素数中只有547个被强制。其余的都在thunk中。

如果你添加新的素数只有当他们的广场是候选人中看到testing-primes列表的末尾，该testing-primes清单将始终贯穿完全强制，或接近它的结束，就不会有引起SO的thunk pileup。并且附加(++)到强制列表的末尾并不是那么糟糕，当下一个访问强制列表到它的结尾并且没有留下thunk时。 （它仍然会复制列表。）

当然，顶级primes列表可以直接使用，正如Thomas M. DuBuisson在他的回答中所示。

但内部列表有其用途。如果正确实施，只有在候选人中看到他们的正方形时才添加新素数，它可能允许您的程序在优化编译时运行O(sqrt(n))空间。