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: ^{(old revision ... NB)}

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