Turner's to Bird's

Turner's to Bird's.hs

sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]                       -- (0)   Turner's
ps = sieve [2..]                                                           
------------------------------------------------------------------------
ps = 2 : sieve ps [3..] 
sieve (p:pt) xs | (h,t) <- span (< p*p) xs =                               -- (1)               
                  h ++ sieve pt [x | x<-t, rem x p /= 0]                   --      Postponed Turner's

ps = 2 : sieve 3 0 ps ps
sieve x k (p:pt) ps | pfx <- take k ps, q <- p*p =                         -- (2)               
    [x | x<-[x..q-1], and [rem x f /= 0 | f<-pfx]] ++ sieve q (k+1) pt ps  -- Segmentwise generative 
------------------------------------------------------------------------   --                Turner's
 --        rem x p /= 0                        ===      not $ ordElem x [p,p+p..]
 -- [x | x <- xs, not $ ordElem x [p,p+p..]]   ===      minus xs [p,p+p..]
 ------------------------------------------------------------------------
ps = 2 : sieve ps [3..] 
sieve (p:pt) xs | (h,t) <- span (< p*p) xs =                               -- (1) -> (3)        
                  h ++ sieve pt (minus t [p*p, p*p+p..])                   --   Postponed Eratosthenes'

ps = 2 : sieve 3 ps [] 
sieve x (p:pt) cs | q<-p*p, (h,t) <- span (< q) cs =                       -- (4)              
   minus [x..q-1] h ++ sieve q pt (union t [q, q+p..])                     -- Segmentwise Postponed
                                                                           --              Eratosthenes'
ps = 2 : 3 : minus [4..] (sieve ps [])
sieve (p:pt) cs | q<-p*p, (h,t) <- span (< q) cs =                         -- (5)               
                  h ++ sieve pt (union t [q, q+p..])                       -- Combined Composites

ps = 2 : minus [3..] (foldr (\p-> (p*p:).union [p*p+p,p*p+2*p..]) [] ps)   -- (6)    Bird's
------------------------------------------------------------------------

ps = 2 : sieve 3 0 ps ps
sieve x k (p:pt) ps | pfx <- take k ps, q <- p*p =                         -- (2),(4) -> (7)    
   (`minus` foldr (\p-> let s=(x`div`p)*p in union [s,s+p..q-1]) [] pfx)   -- Segmentwise generative 
           [x..q-1] ++ sieve q (k+1) pt ps                                 --              Eratosthenes'

(3)->(4) idea from https://gist.github.com/WillNess/5659214 i.e. from http://stackoverflow.com/q/16271592

------------------------------------------------------------------------
_Y g = g (_Y g)

ps = _Y $ (2 :) . minus [3..] . foldr (\p-> (p*p:).union [p*p+p,p*p+2*p..]) []
   = (2:) . _Y $ (3:) . minus [5,7..] . foldi (\(x:xs)->(x:).union xs) 
                      . map (\p-> [p*p, p*p+2*p ..])
   = (2:) . _Y $ (3:) . minus (tail . scanl (+) 3 $ cycle [2]) 
                      . foldi (\(x:xs)->(x:).union xs) 
                  --  . map (\p-> map (p*) $ scanl (+) p (cycle [2]))   
                      . map (\p-> scanl (\a d->a+p*d) (p*p) (cycle [2]))        
                            --          ((.(p*)).(+))               
                            --  (curry(uncurry (+) . second (p*)))  
   = ([2,3,5,7]++) . _Y $ (11:) . tail . minus (scanl (+) 11 wh11) 
                   . foldi (\(x:xs)-> (x:) . union xs)
                   . map (\(w,p)-> scanl (\c d-> c + p*d) (p*p) w)
                   . equalsBy snd (tails wh11 `zip` scanl (+) 11 wh11)

-- general code: https://ideone.com/nuoLUE     foldi: http://www.haskell.org/
-- gaps&hits: https://ideone.com/vkXCXt           /haskellwiki/Fold#Tree-like_folds