I have just finished benchmarking all the implementations provided in http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip (the zip file linked to from the Haskell wiki article on primes).
NaurPrimes.hs is by far the fastest version, and at least 2 or 3 times faster than your current implementation.
Thanks for the benchmarks!
I'm pretty sure it also uses less memory.
Do you understand the memory requirements of my implementation? I'm not sure if I do. Is it only that the queue of multiples gets larger and larger the more primes we query?
I want to find efficient algorithms for the other proposed functions before forking, but I figured I'd let you know in the meantime.
Thanks! Feel free to incorporate ideas from NaurPrimes.hs. I don't understand them yet. Cheers, Sebastian