Search code examples
listhaskellprimeslazy-evaluation

Lazy List of Prime Numbers

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.

Solution

  • 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.