{-# OPTIONS_GHC -O2 #-}
module Main where
main = print $ primes !! 1000000    --  -fno-cse -fno-full-laziness 

primes :: [Int]
primes = [2,3,5,7] ++ _Y ((11:) . tail        -- no leak on 7.8.3 either
                   . gaps 11 wh11 
                   . _U . map (\(w,p)->scanl (\c x-> c+p*x) (p*p) w)
                   . hits 11 wh11)
  where
    gaps k (d:w) s@(c:t) | k < c     = k       : gaps (k+d) w s
                         | otherwise =           gaps (k+d) w t   -- k==c
    hits k (d:w) s@(p:t) | k < p     =           hits (k+d) w s
                         | otherwise = (d:w,p) : hits (k+d) w t   -- k==p

_Y g = g (_Y g)        -- multistage with non-sharing fixpoint combinator
     -- = g (fix g)    -- two stages with sharing fixpoint combinator

_U ((x:xs):t)   = x : (union xs . _U . pairs) t 
  where
        pairs (xs:ys:t) = union xs ys : pairs t

union a@(x:xs) b@(y:ys) = case compare x y of 
                                 LT -> x : union  xs b   
                                 EQ -> x : union  xs ys  
                                 GT -> y : union  a  ys  

wh3  = 2:wh3                -- n=1, d=2  [3, 5..] \\ ((3*) <$> _) 
wh5  = 2:4:wh5              -- n=2, d=6   [5,7,_, 11,..] \\ ((5*) <$> _)  
wh7  = 4:2:4:2:4:6:2:6:wh7  -- n=8,  d=30   [7,11,13,17,19,23,_,29,31,_, 37..]
wh11 =                      -- n=48, d=210                \\ ((7*) <$> _)
       2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:  
       4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wh11  
       
primes2 = [2,3,5,7] ++ _Y ((11:) . tail . gaps (scanl (+) 11 wh11)
                                 . _U   . hits (scanl (+) 11 wh11))
  where
    gaps (n:w) s@(c:t) | n < c     = n              : gaps w s
                       | otherwise =                  gaps w t   -- k==c
    hits (n:w) s@(p:t) | n < p     =                  hits w s
                       | otherwise = map (p*) (p:w) : hits w t   -- n==p
      -- almost the same as Dave Bayer's code except here  _^_  he has, in effect,
      -- ~~~~~~                           (filter ((/=0).(`rem`p)) w)
      --    (and also, he doesn't sync on primes, since he uses the filter)
      --   see www.haskell.org/pipermail/haskell-cafe/2007-July/029077.html
    wo_hits_Bayer (n:w) (p:t) = map (p*) (p:w) :           
                          wo_hits_Bayer (filter ((/=0).(`rem`p)) w) t  
    -- also, he uses diff, but
    --  gaps a b == diff a b when b ⊂ a   is more efficient 
    
    -- but most importantly he names a lot of stuff, and thus creates
    -- and re-uses a lot of shared structure; in my code data separation
    -- is the goal, which enables definitions of gaps/hits be fused w/ scanl

{-  gaps ~= minus 
    hits ~= equalsBy 
     see  ideone.com/nuoLUE, rHJ9ub -}