Lazy List of Prime Numbers

Question

How would one implement a list of prime numbers in Haskell so that they could be retrieved lazily?

I am new to Haskell, and would like to learn about practical uses of the lazy evaluation functionality.

Answer 1

Here's a short Haskell function that enumerates primes from Literate Programs:

primes :: [Integer]
primes = sieve [2..]
  where
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

Apparently, this is not the Sieve of Eratosthenes (thanks, Landei). I think it's still an instructive example that shows you can write very elegant, short code in Haskell and that shows how the choice of the wrong data structure can badly hurt efficiency.

Answer 2

There are a number of solutions for lazy generation of prime sequences right in the haskell wiki. The first and simplest is the Postponed Turner sieve. From http://www.haskell.org/haskellwiki/Prime_numbers#Postponed_Filters_Sieve

primes :: [Integer]
primes = 2: 3: sieve (tail primes) [5,7..]
 where 
  sieve (p:ps) xs = h ++ sieve ps [x | x <- t, x `rem` p /= 0]  
                                -- or:  filter ((/=0).(`rem`p)) t
                  where (h,~(_:t)) = span (< p*p) xs

Answer 3

I'd suggest to take one of the implementations from this paper: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf