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 ?

• barjak: I realize QA may be a better fit on stackoverflow, but the questions I'm more interrested in are QB and QC, which (I think) belong to codereview.
• AlucardTheRipper: QC: haskell.org/hoogle/?hoogle=takeWhile Hoogle is very useful.

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.

• barjak: Thanks, initializing primes with the first value is clearly the way to go. I'll remember the $ function, too (I saw it in the Prelude, but didn't get its usefulness).
• CiaPan: A better (more persistent, hopefully) location of 'the excellent paper' is doi.org/10.1017/S0956796808007004 and here are the full bibliographic data (in case both URLs become invalid some day): Melissa E. O’Neill The Genuine Sieve of Eratosthenes, Journal of Functional Programming, Volume 19, Issue 1, January 2009, pp. 95 - 106