This isn't a variant of the "folklore sieve", it's actually the real one! :-)
well, one thing i was trying for (and what perhaps one might like to see in a paper), is a way of relating the various code alternatives to each other, with suitably similar intermediate stages. not quite as detailed as deriving one from the other by program transformation, and not always meaning-preserving, but small enough steps that it becomes easier to understand the differences, and how one version might grow out of another, based on which performance concerns and implementation decisions. your paper does some of that, but the steps feel more like jumps to me. we don't usually have compiler optimisations that could effectively transform the folklore version of the sieve into any of the other prime enumerators we've seen. and it is nice to see sieve added to the infamous quicksort as an example of a well-known to be beautiful, but little-known to be inefficiently realised specification (Lennart provided a convincing alternative for that other one, too;) - they are advertised and accepted unquestioned all too often. but something in me balks at the idea that the folkore version of the sieve is not "the" sieve *algorithm*, in spite of your detailed cross-off footprint and performance curve arguments. i'm not saying you're wrong, and as one of those who prefer operational semantics over denotational semantics in many contexts, i realise that it may be seen as odd if i prefer to see the high-level versions as specifications of algorithms, when the implementation behaviour might differ substantially from the intended algorithm. but we are in the grey area between "permute until sorted" and "sort like this", and thinking of the modulus of a number as a static property (that might be derived incrementally from that of its predecessor) rather than an explicit check for divisibility looks very similar to "this is quicksort, but i didn't really mean (++) to do appends". if one has to use quicksort on binary lists, one better uses Augustsson's append-free qsort instead of the folklore version, but is that a better implementation, or a different algorithm? does it depend on how we look at the question? if you could make that part of your argument in a less controversial style, without loaded words like "real", "phony", "fooling", focussing more on observations than on any agenda (however innocent), this reader at least would find it easier to focus on the really interesting issues you raise for discussion. also, the present thread (one of many incarnations) demonstrates that there are other issues to be exposed and explored when discussing styles of prime sieves. not to mention the modern-again issue of transforming executable specifications to efficient implementations. the progression mod sieves (folklore) ->start (sieve p) at p*p ->incremental sieves (folklore2) ->merged incremental sieves (folklore3) ->more efficient representation of merged sieves (your priority queue version) ->other useful optimisations and tweaks that further hide the ideas (your fastest versions) .. makes it easier for me to see how the initial program relates to the others, and the closeness of folklore3 to one of your versions is intentional, as are the differences. the versions are not quite equivalent (eg folklore2/3 go wrong earlier than folklore when using Int instead of Integer), but if there is any difference wrt the cross-out footprint (apart from the p*p thing), it is likely to be in the precise organisation of sieve merging after folklore2. otherwise, they seem to embody fairly natural improvement steps of the original specification-level code.
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.
as it happens, even if we run folklore3 over [2..], 70 will be crossed off exactly once, by the sieve for 2. the sieves for 5 and 7 run over the gap left behind, as they do in folklore and folklore2 (one could move that gap jumping from sieve3 to insert, though..). the sieves for 5 and 7 "know" about 70 the same way that (`mod`5) and (`mod`7) know about 70, but that knowledge isn't called upon for sieving, only to find greater numbers with modulus 0. in contrast, sieves in genuine will replace non-primes by zero, so later sieves can still run into the same position. whether we count the zero in that position as a gap, to be left intact, or as a ghost of the non-prime, to be zeroed again, would seem to be a matter of viewpoint? for me, the question is more one of vertical vs horizontal, or from-scratch vs incremental, or level of abstraction. if i have a list of numbers list = [0..20] do i compute their moduli from scratch, starting recursions orthogonal to the list direction map (\x->(x,x`mod` 3)) list or do i compute them incrementally, aligning my recursion with the list direction zip list (cycle [0..2]) do i see the former as associating the list elements with their moduli, or as testing them for divisibility? and is the latter the same as the former, or something different? it is the same thing, computed differently, of course. but if i use that thing as a component of describing a more complex algorithm, am i talking about different algorithms, or about the same algorithm, computed differently? does it depend on our point of view, or must we talk in absolutes? claus