Generating finite lists of primes in Haskell

Question

There are a lot topics on generating prime numbers in Haskell, but in my opinion, they all rely on 'isPrime' function, which, if we don't know the primes sequence yet, should look like:

isPrime k = if k > 1 then null [ x | x <- [2,3..(div k 2) + 1], k `mod` x == 0]
                     else False

(div might be replaced with sqrt, but still...)

I've tried to construct prime numbers based on 'inductive definition' (assume we have a set of first n primes, then (n+1)th prime is the least integer such that none of the first n primes is a divisor of it). I've tried to do it in the Fibonacci sequence way, which is:

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fibs !! n
    where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

And I ended up with this:

-- checking if second number is a divisor of first one
ifDoesn'tDivide :: Int -> Int -> Bool
ifDoesn'tDivide n k 
    | mod n k == 0 = False
    | otherwise    = True

-- generating list which consists of first n prime numbers
firstPrimes :: Int -> [Int]
-- firstPrimes 1  = [2]
firstPrimes n     = take n primes 
    where primes = 2:(tail primes) ++ 
         [head [x | x <- [3,4..], k <- primes, ifDoesn'tDivide x k == True]]

But it doesn't work, stack overflow when n >= 2. Any advice on how to fix it?

"Haskell can define data structures in terms of themselves in effect creating infinite data structures". Those prime numbers and Fibonacci sequences mentioned earlier are specific cases of defining data structures in terms of themselves, and Fibonacci sequence works just fine, but these primes doesn't.

Am I missing something, are those two algorithms different in a substantive way?

P.S. So, I think, I'm just looking for most 'Haskellish' way to do that.

Answer 1

You can always use a sieve which is rather elegant in Haskell.

primes = sieve [2..]

sieve (p : xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]

So to get the first 10 primes

> take 10 primes
[2,3,5,7,11,13,17,19,23,29]

Notice that while isPrime is not explicitly used the list comprehension ensures that every number on the list must be prime relative to all the primes preceding it, which is to say prime.

This is more efficient and it's at the heart of Eratosthenes' sieve(Edit).

The code above is the first example in:

• Melissa E. O'Neill, The Genuine Sieve of Eratosthenes

The paper goes in to much more detail about the efficient implementation of sieves in Haskell and the role of laziness in the computation. Highly recommended!