Lazy computation of primes in Haskell I wanted to give Haskell a try, and I started with a simple exercise I found here.


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


My answer to Q1

isPrime :: Integer -&gt; Bool
isPrime v = let maxDiv = floor(sqrt (fromIntegral v))
            in all (\x -&gt; (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 -&gt; Bool
isPrime v | v &lt; 2 = False
          | otherwise = all (\x -&gt; (v `rem` x) /= 0) (takeWhile (&lt;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 (&lt;v) primes) by an expression that would stop before reaching a not-yet-computed value. I came to this solution :

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

takeWhile' :: (a -&gt; Bool) -&gt; [a] -&gt; [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 ?
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 -&gt; Bool
isPrime v = let maxDiv = floor $ sqrt $ fromIntegral v
            in all ((/= 0).(v `rem`)) $ takeWhile (&lt;= 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.