Lazy computation of primes in Haskell

Question

I wanted to give Haskell a try, and I started with a simple exercise I found here.

1. Write isPrime :: Integer -> Bool, which determines whether a given integer is prime.
2. Define primes :: [Integer], the list of all primes.
3. Revise isPrime so that it only tests divisibility by prime factors.

My answer to Q1

isPrime :: Integer -> Bool
isPrime v = let maxDiv = floor(sqrt (fromIntegral v))
            in all (\x -> (v `rem` x) /= 0) [2..maxDiv]

This one was easy, except for the explicit numeric types conversions I had a hard time to get right.

My answer to Q2

primes = filter isPrime [0..]

This one was easy, too.

My answer to Q3

It took me several hours to answer this one. I quickly understood that isPrime could leverage the values already computed in the array primes. So, my first attempt was :

isPrime :: Integer -> Bool
isPrime v | v < 2 = False
          | otherwise = all (\x -> (v `rem` x) /= 0) (takeWhile (<v) primes)

isPrime works fine for v=0 and v=1, but hangs forever for v>1. Ok, I get it : the mutual recursion creates an infinite loop, due to takeWhile trying to access a primes element which is not yet computed.

One thing I don't understand though, is why primes !! 0 and primes !! 1 hang forever, too.

I tried many approaches for replacing this (takeWhile (<v) primes) by an expression that would stop before reaching a not-yet-computed value. I came to this solution :

isPrime :: Integer -> Bool
isPrime v | v < 2 = False
          | v == 2 = True
          | otherwise = all (\x -> (v `rem` x) /= 0) (takeWhile' (\t -> t*t<=v) primes)

takeWhile' :: (a -> Bool) -> [a] -> [a]
takeWhile' p (x:xs) = if p x then x : takeWhile' p xs else [x]

This solution works. But I had to define a takeWhile' that works just like takeWhile, but also includes the first non-matching element.

Here are my questions to you :

QA : why do primes !! 0 and primes !! 1 hangs in my first attempt ?

QB : is there a magical takeWhileOnlyForAlreadyComputedElements function ? Or a construct that would prevent the infinite loop of this mutual recursion ?

QC : does takeWhile' already exist in the stdlib ? Or maybe the same effect can be achieved in a simpler way ?

Answer 1

Not an answer to your questions, but a correction for your first, looping attempt for Q3:

Things get much easier if you initially have at least one prime number in your list. You could ensure this by a separate case in isPrime, but why not cheat a little bit, and add it directly?

primes = 2 : filter isPrime [3..]

Then you can use your solution for Q1 without much changes (I took the freedom to kill some parens etc):

isPrime :: Integer -> Bool
isPrime v = let maxDiv = floor $ sqrt $ fromIntegral v
            in all ((/= 0).(v `rem`)) $ takeWhile (<= maxDiv) primes

However, this is not the best way to generate a list of primes. Read the excellent paper http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf for details.

[Edit]

I forgot to mention http://www.haskell.org/haskellwiki/Prime_numbers with many interesting techniques.