Prime numbers have fascinated many people, and Haskell programmers are no exception. In fact, as in other languages in which the Sieve of Eratosthenes can be expressed concisely, this algorithm tends to feature prominently as an introductory example. Fewer Haskellers might now that this is not necessary the best way to compute primes.

First, the well-known Haskell incarnation of the Sieve of Eratosthenes. Note how this generate-and-test scheme considers each and every natural number as a prime candidate, passing it through a growing series of sieves, until it emerges at the end or one of the tests shows otherwise.

import Observe

primes :: [Integer]
primes = sieve [2..]

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

sieve l = observe "sieve" sieve' l

main = printO $ takeWhile (<50) primes

Next, Colin Runciman's Haskell implementation of the Wheel Sieve, modified to observe the primes and the wheels generated. For a full discussion of the problem, explanation of this code, other variants and further references, see Colin's JFP paper (I would be very interested to learn whether you find this animation of the Mark II version helpful when reading the paper). The core idea: as more and more prime numbers are computed, more and more information can be incorporated into the generator of further prime candidates. This idea leads to a lazily generated sequence of generators (the wheels). Instead of having to test each candidate, each wheel is used only as long as it generates prime numbers, replacing one wheel by the next before it could generate non-primes. So all computation is moved from testing candidates to computing better generators.

import Observe

-- Mark II lazy wheel-sieve.
-- Colin Runciman (colin@cs.york.ac.uk).
-- See article "Lazy wheel sieves and spirals of primes" .
-- Journal of Functional Programming, 7(2):219-225, March 1997

data Wheel = Wheel Int [Int] [Int]

instance Observable Wheel where
  observer (Wheel a b c) = send "Wheel" (return Wheel << a << b << c)

wheels = 
  Wheel 1 [1] [] :
  zipWith3 nextSize wheels primes squares 

nextSize (Wheel s ms ns) p q =
  Wheel (s*p) ms' ns'
  where
  (xs, ns') = span (<=q) (foldr (turn 0) (roll (p-1) s) ns)
  ms' = foldr (turn 0) xs ms
  roll 0 _ = []
  roll t o = 
    foldr (turn o) (foldr (turn o) (roll (t-1) (o+s)) ns) ms
  turn o n rs =
    let n' = o+n in [n' | n' `mod` p > 0] ++ rs

primes = spiral wheels primes squares

spiral (w:ws) ps qs = spiral' ((observe "wheel" w):ws) ps qs

spiral' (Wheel s ms ns:ws) ps qs =
  foldr (turn 0) (roll s) ns
  where
  roll o = 
    foldr (turn o) (foldr (turn o) (roll (o+s)) ns) ms
  turn o n rs =
    let n' = o+n in
    if n'==2 || n' < head qs then n':rs 
    else dropWhile (<n') (spiral ws (tail ps) (tail qs))

squares = [p*p | p <- primes]

main = printO $ take 100 (observe "primes" primes)

A few more details: The Wheels (the generators) are characterised by two parameters - their circumference and a list of "spikes" (distances from the start at which prime candidates are to be found). To facilitate switching from one wheel to the next (leaving the smaller wheel before it starts to generate candidates that aren't primes and starting the next wheel in mid-turn), the list of spikes is split into two.

So, the first wheel suggests every number (circumference 1, spike at 1). The second wheel suggests every second number (circumference 2, spike at 1). The third wheel suggests the first and fifth numbers out of every 6, and so on, each successive wheel suggesting fewer and fewer candidates out of increasing circumferences. Note that the circumferences are products of primes and that only the first few wheels go through a full or even more than one revolution (single-step between events 60 and 80 to see the third wheel being reused for more than one revolution). For later wheels, their full circumference is not observed, and indeed their initial segments are not used - they start in mid-revolution and are disused before completing a full revolution.

If you find it curious that the wheels seem to have different, not monotonically increasing, sizes, remember that you are not seeing the full wheels, only those parts that have been observed in the computation. Wheels are changed at prime squares (don't read this with cars in mind;-). Now think of prime twins (p is a prime and p+2 is a prime) as an extreme example -- they yield two neighbouring wheels, the second of which will only run between p*p and (p+2)*(p+2).