Editing Prime numbers (section)

====Segmented merging via an array====

The removal of composites is easy with arrays. Starting points can be calculated directly:

<haskell>
import Data.List (inits, tails)
import Data.Array.Unboxed
 
primesSAE = 2 : sieve 2 4 (tail primesSAE) (inits primesSAE)
         -- (2:) . (sieve 2 4 . tail <*> inits) $ primesSAE
  where
  sieve r q ps (fs:ft) = [n | (n,True) <- assocs (
         accumArray (\ _ _ -> False) True (r+1,q-1)
                    [(m,()) | p <- fs, let s = p * div (r+p) p,
                              m <- [s,s+p..q-1]] :: UArray Int Bool )]
      ++ sieve q (head ps^2) (tail ps) ft
</haskell>

The pattern of iterated calls to <code>tail</code> is captured by a higher-order function <code>tails</code>, which explicitly generates the stream of tails of a stream, making for a bit more readable (even if possibly a bit less efficient) code:
<haskell>
psSAGE = 2 : [n | (r:q:_, fs) <- (zip . tails . (2:) . map (^2) <*> inits) psSAGE,
                  (n,True)    <- assocs (
                                   accumArray (\_ _ -> False) True (r+1, q-1) 
                        [(m,()) | p <- fs, let s = (r+p)`div`p*p, 
                                  m <- [s,s+p..q-1]] :: UArray Int Bool )] 
</haskell>