It bugs me a bit that the example code is brute force trial division instead of a true prime sieve. Sure, it highlights lazyness but the algorithm is less efficient.
i guess you are right that some do not care about constant factors, but i am very sure most do care about algorithmic complexity. and thinking about it, that's the approach you should use for anything where every last bit of performance is not utterly needed.
I'd love to see it as it shows off some great data structures available in the libraries (like priority queues) but it's getting longish.
The mutable array version is basically the same as imperative code everywhere
sieveUA :: Int -> UArray Int Bool
sieveUA top = runSTUArray $ do
let m = (top-1) `div` 2
r = floor . sqrt $ fromIntegral top + 1
sieve <- newArray (1,m) True
forM_ [1..r `div` 2] $ \i -> do
isPrime <- readArray sieve i
when isPrime $ do
forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> do
writeArray sieve j False
return sieve