Sieve of Sundaram for Project Euler 7
Prime sieves are really not well suited for linked lists. While sorting or merging are clever way to handle the lists in a functional context, the easiest way to improve preformance is to simply use mutable arrays, so it's more similar to the C++ version.

Here I just replaced the sorting and removeComposites with an unboxed STArray and indexing. The benifit with using STArray is that you still get a pure function, even though the array is mutable while generating. The times are now comparable with the C++ version.

import Data.Array.ST
import Data.Array.Unboxed

bound :: Int -&gt; Int
bound n = floor (n' * (log n' + log (log n')))
    where 
        n' = fromIntegral n

marked :: Int -&gt; [Int]
marked n =  [ i + j + 2*i*j | i &lt;- [1..iMax], j &lt;- [i..jMax i]]
    where 
        iMax = floor (sqrt (fromIntegral n))
        jMax i = quot (n - i) (2*i + 1)

marked' :: Int -&gt; UArray Int Bool
marked' n = runSTUArray $ do
    arr &lt;- newArray (1,n) True
    mapM_ (\i -&gt; writeArray arr i False) (marked n)
    return arr

sieveSundaram :: Int -&gt; [Int]
sieveSundaram n = 2: [2*x+1 | x &lt;- [1..n'], marked' n' ! x]
    where 
        n' = quot (bound n) 2

pe_007 = last . take n $ sieveSundaram n
    where n = 100001

main :: IO ()
main = print pe_007


On my system, with n=200001, the times are:

Haskell, Original version: 5.930s
Haskell, Neil's version:   5.916s
Haskell, Data.IntSet:      2.853s
Haskell, Boxed STArray:    0.209s
Haskell, Unboxed STUArray: 0.055s
C++:                       0.019s


It is probably possible to improve the times even more, but this takes care of most of the difference.



Update

Continuing on the theme of using the right data structure for the job, I tried using IntSets for aditional comparison. It is about twice as fast as the list based solutions, but still a lot slower than using mutable arrays (see updated table). So if you want to stay with pure haskell98, this might be an alternative. Here is my (naive) translation. I just create the set of numbers [1,n] and the set of numbers to remove (from marked) and take the difference.

import qualified Data.IntSet as IS

bound :: Int -&gt; Int
bound n = floor $ n' * (log n' + log (log n'))
    where 
        n' = fromIntegral n

marked :: Int -&gt; [Int]
marked n =  [ i + j + 2*i*j | i &lt;- [1..iMax], j &lt;- [i..jMax i]]
    where 
        iMax = floor (sqrt (fromIntegral n))
        jMax i = quot (n - i) (2*i + 1)

marked' :: Int -&gt; [Int]
marked' n = let
    l1 = IS.fromList [1..n]
    l2 = IS.fromList (marked n)
    in IS.toList $ l1 IS.\\ l2

sieveSundaram :: Int -&gt; [Int]
sieveSundaram n = 2: [2*x+1 | x &lt;- marked' n']
    where 
        n' = quot (bound n) 2

pe_007 = last . take n $ sieveSundaram n
    where n = 200001

main :: IO ()
main = print pe_007


IntSets are a really good data structure if you need to repeatedly modify the sets in a pure context, but for this problem nothing can beat an unboxed mutable array.