Claus Reinke wrote:
folklore3: merging the sieves, instead of stacking them as implicit thunks
Here's Claus's code: primes3 = 2 : folklore3 [] [3,5..]
folklore3 pns xs = x : folklore3 (insert (x,x*x) pns') xs' where (x,pns',xs') = sieve3 pns xs
sieve3 ((p,n):pns) (x:xs) | x
n]++xs) sieve3 [] (x:xs) = (x,[],xs) insert (p,n) [] = [(p,n)] insert (p,n) ((p',n'):pns) | n<=n' = (p,n):(p',n'):pns | otherwise = (p',n'):insert (p,n) pns
This isn't a variant of the "folklore sieve", it's actually the real one! Let's take a look at ``pns'' at the 20th prime, having just found that 67 is prime (we're about to discover that 71 is prime): [(3,69),(5,70),(7,70),(11,121),(13,169),(17,289),(19,361),(23,529), (29,841),(31,961),(37,1369),(41,1681),(43,1849),(47,2209),(53,2809), (59,3481),(61,3721),(67,4489)] As you can see, 70 will be crossed off twice, once by the 5 iterator and once by the iterator for 7. And we won't think about 11, 13, etc. until they're needed. This algorithm is doing pretty much exactly what mine does, except that in mine I use a priority queue to represent this information. In fact, with my most recent code, I'd only store (3,69), (5,70), (7,70) in the priority queue and keep (11,121), (13,169), ..., (67,4489) in a feeder queue so that I only use the power of the priority queue when I need it. Melissa. P.S. Mine actually wouldn't have quite the same numbers, because I go to a bit of trouble to skip numbers like 70 which will never actually show up in the x:xs list.