4

我正在研究 Real World 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和这里的各种回复让我相信这是懒惰评估的副产品，并且 thunk 正在积累直到它溢出，但到目前为止我一直没有成功修复它。我试过seq在各个地方使用强制评估，但没有效果。我在正确的轨道上吗？还有什么我没有得到的吗？

4

3 回答 3

6

正如我在评论中所说，您不应该通过将单个元素列表附加到非常长的列表（您的行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

显然，您不需要对isPrime函数进行参数化primes，但这只是一个小问题。此外，当您知道所有数字都是正数时，您应该使用rem而不是mod- 这会导致我的机器上的性能提高 30%（当找到第百万个素数时）。

于 2012-08-13T00:19:02.897 回答
2

首先，这里没有尾递归，而是有保护的递归，也就是尾递归模 cons。

正如其他人所评论的那样，你得到堆栈溢出的原因是一个 thunk 堆积。但是哪里？一个建议的罪魁祸首是您使用(++). 虽然不是最优的，但使用(++)不一定会导致 thunk 堆积和堆栈溢出。例如，调用

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

应该立即产生[15485863,15485867]，并且没有任何堆栈溢出。但它仍然是使用相同的代码(++)，对吧？

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

但是当它用于测试时，它不会被强制完成。如果发生这种情况，就不会有 SO 问题。它只是强制通过sqrt一个测试号。所以(++)thunks 确实会超过那个点。

当isPrime primes 15485863被调用时，它会强制顶层primes达到3935，即 547 个素数。内部测试素数列表也包含 547 个素数，其中只有前 19 个是强制的。

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

如果您仅在候选中看到它们的正方形testing-primes时才将新素数添加到列表的末尾，则列表将始终被强制完全或接近其末尾，并且不会出现导致 SO 的 thunk 堆积。并且当下一次访问强制该列表到其末尾并且没有留下任何thunk时，将 with 附加到强制列表的末尾并不是那么糟糕。（它仍然会复制列表。）testing-primes(++)

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

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

于 2012-08-13T11:10:48.547 回答
0

您可能应该检查以下两个问题：

  1. 如何使用 runhaskell 增加堆栈大小？
  2. 如何避免堆栈空间溢出？
于 2012-08-12T22:28:49.870 回答