[Haskell-cafe] Re: Genuine Eratosthenes sieve [Was: Optimizationfun]

[Claus Reinke]

i have to say that i find the folklore sieve quite acceptable as a sieve, whereas 
the faster test-against-primes is obviously different. but the discussion has 
prompted me to write yet another sieve, perhaps more acceptable to purists. 

instead of using (mod p) repeatedly and filtering directly, we zero out 
multiples of p, for all p, then filter out non-zero elements in a second phase:

    primes = 2 : filter (>2) (foldr sieve id primes [0..])

    -- start sieve for p at position p*p, zeroing position off=(p-1)*(p-1)
    sieve p f xs@(off:_) = 0: tail (applyAt (p*p-off) (f . sieve' p) xs) 

    -- zero positions that are multiples of p
    sieve' p = applyAt p (\(_:b)->sieve' p (0:b))

    -- like splitAt, followed by (++), where only suffix is operated on
    -- infinite lists, non-negative offset
    applyAt 0 f xs     = f xs
    applyAt n f (x:xs) = x:applyAt (n-1) f xs

it seems to be a lot faster than the folklore sieve, and within a factor of 2 
of the faster test-against-primes (given the repeated use of applyAt, I guess
it could be sped up further by using a piecewise contiguous list representation, 
aka polymorphic ByteString).

claus