计算素数时堆栈空间溢出

Question

我正在通过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,这里的各种回应让我相信它是懒惰评估的副产品,并且在它溢出之前,thunks正在积累,但到目前为止,我一直没有成功修复它.我曾尝试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

显然你不需要isPrime通过primes任何一个来参数化函数,但这只是一个问题.此外,当您知道所有数字都是正数时,您应该使用rem而不是mod- 这会导致我的机器性能提高30%(当找到百万次素数时).