# Lazy computation of primes in Haskell

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.

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.

primes = filter isPrime [0..]


This one was easy, too.

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 ?

• 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. Sep 7, 2011 at 1:55
• QC: haskell.org/hoogle/?hoogle=takeWhile Hoogle is very useful. Apr 3, 2013 at 18:55

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

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.  I forgot to mention http://www.haskell.org/haskellwiki/Prime_numbers with many interesting techniques. • 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). Sep 7, 2011 at 9:00