I'm working my way through Real World Haskell (I'm in chapter 4) and to practice a bit off-book I've created the following program to calculate the nth prime.
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'm saving a list of primes this is not a constant space solution. The problem is when I try to get a very large prime say ./primes 1000000
I receive the error:
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase
I'm fairly sure that I got the tail recursion right; reading http://www.haskell.org/haskellwiki/Stack_overflow and the various responses here lead me to believe that it's a byproduct of lazy evaluation, and thunks are building up until it overflows, but so far I've been unsuccessful in fixing it. I've tried using seq
in various places to force evaluation, but it hasn't had an effect. Am I on the right track? Is there something else I'm not getting?
As I said in my comment, you shouldn't be building a list by appending a single element list to the end of a really long list (your line primes' = primes ++ [test]
). It is better to just define the infinite list, primes
, and let lazy evaluation do it's thing. Something like the below code:
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 by primes
either, but that's just a nit. Also, when you know all the numbers are positive you should use rem
instead of mod
- this results in a 30% performance increase on my machine (when finding the millionth prime).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With