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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
