This is a sequel to my previous question: Sieve of Sundaram for Project Euler 7: Python implementation slower than C++ and RI am trying to implement the Sieve of Sundaram in various languages to solve Project Euler Problem #7.I have written a solution in Haskell (to which I am still very new, but eager to learn) based loosely on the example available on this blog.The approach is to find the upper bound for the value of the nth prime:$$\mathrm{Bound}(n) = n \times (\log(n) + \log(\log(n))) $$Then sieve all of the numbers up to the bound. I would like some advice on improving my style (conciseness, clarity), and the performance of my code, which is about 30x slower than the C++ solution included in my previous question.import Data.Listbound :: Int -> Intbound n = floor (n' * ((log n') + log (log n')))    where         n' = fromIntegral nmarked :: Int -> [Int]marked n = sort [ i + j + 2*i*j | i <- [1..iMax], j <- [i..jMax i]]    where         iMax = floor (sqrt (fromIntegral n))        jMax i = quot (n - i) (2*i + 1)removeComposites :: [Int] -> [Int] -> [Int]removeComposites [] _          = []removeComposites (s:ss) []     = 2*s + 1 : removeComposites ss []removeComposites (s:ss) (c:cs)    | s == c    = removeComposites ss cs    | s > c     = removeComposites (s:ss) cs    | otherwise = 2*s + 1 : removeComposites ss (c:cs)sieveSundaram :: Int -> [Int]sieveSundaram n = 2:(removeComposites [1..n'] (marked n'))    where         n' = quot (bound n) 2pe_007 = last (take n (sieveSundaram n))    where n = 10001main :: IO ()main = do    print pe_007
Sieve of Sundaram for Project Euler 7
performance;programming challenge;haskell;primes
The first thing to try is enable compiler optimization level 2 by adding:{-# OPTIONS_GHC -O2 #-}to the start of your file. This reduced my execution time by 9%.Next I removed the limits to take advantage of Haskell's laziness.{-# OPTIONS_GHC -O2 #-}-- doesn't workimport Data.Listmarked :: [Int]marked = [ i + j + 2*i*j | i <- [1..], j <- [i..]]removeComposites :: [Int] -> [Int] -> [Int]removeComposites [] _          = []removeComposites (s:ss) []     = 2*s + 1 : removeComposites ss []removeComposites (s:ss) (c:cs)    | s == c    = removeComposites ss cs    | s > c     = removeComposites (s:ss) cs    | otherwise = 2*s + 1 : removeComposites ss (c:cs)sieveSundaram :: [Int]sieveSundaram = 2:(removeComposites [1..] marked)pe_007 = last (take n (sieveSundaram))    where n = 100001main :: IO ()main = do    print pe_007Unfortunately that doesn't work because marked ends up being [4,7,10,13,16,19,22,25..] which is just i=1 and j<-[1..]. To solve this I generated a list for each i and merged the lists together using a fold.{-# OPTIONS_GHC -O2 #-}-- compiled execution time for 100001 is 0.877s (about 27% better)marked :: [Int]marked = fold $ map mark [1..]    where        fold ((x:xs):t) = x : (xs `union` fold t)        mark i = map (calc i) [i..]        calc i j = i + j + 2*i*junion :: [Int] -> [Int] -> [Int]union a         []        = aunion []        b         = bunion (x:xs) (y:ys)    | x < y     = x : union xs (y:ys)    | x == y    = x : union xs ys    | otherwise = y : union (x:xs) ysremoveComposites :: [Int] -> [Int] -> [Int]removeComposites [] _          = []removeComposites (s:ss) []     = 2*s + 1 : removeComposites ss []removeComposites (s:ss) (c:cs)    | s == c    = removeComposites ss cs    | s > c     = removeComposites (s:ss) cs    | otherwise = 2*s + 1 : removeComposites ss (c:cs)sieveSundaram :: [Int] sieveSundaram = 2:(removeComposites [1..] marked)pe_007 = last $ take n sieveSundaram    where n = 100001main :: IO ()main = do    print pe_007In addition to reducing the execution time by a modest amount it also makes it simpler to debug things inside ghci. You could also change the main to take n as an command line input so you wouldn't need to recompile.There is probably some inefficiency that I missed. For comparison, my Sieve of Eratosthenes code uses a similar merge fold and runs in 0.26s.UpdateI was curious about the drop in performance of my solution as N increased so I took some more time measurements. I also measured my Sieve of Eratosthenes code that uses a similar fold merge and a faster version I found that uses a treefold merge with a wheel.                                 10k     100k    200k    1MOriginal:                       0.073   1.210   2.788   20.983My simple fold merge:           0.038   0.875   2.634   38.835SoE simple fold merge:          0.028   0.270   0.646    6.214SoE treefold merge with wheel:  0.019   0.079   0.142    0.900HJulle's Unboxed STUarray:      0.015   0.021   0.038    0.172So it is possible to make a sieve using lists that is quite a bit faster than the one I posted. I find it useful to have the infinite list version for use in other Project Euler problems so I can avoid issues with setting the upper bound incorrectly. As far as my SoS code goes I'm not sure why it's so much worse than the SoE but I'm guessing it has to do with the double map in marked.One last thing to note is the original uses much more memory (1.7GB for N=100k) than the other solutions. 