Efficient Collatz sequence analysis I'm new to Haskell, and I'm wondering why my programs are so slow compared to other languages.

Haskell, 6 seconds (x64, -O2):

nextCollatz :: Int -&gt; Int
nextCollatz x = if even x
    then quot x 2
    else 3 * x + 1

collatzLength :: Int -&gt; Int
collatzLength x = if x == 1
    then 0
    else 1 + collatzLength (nextCollatz x)

main = print . show . sum . map collatzLength $ [1..3000000]


Julia, 0.8 seconds (excluding the compilation time):

function main()
    sum = 0
    for i = [1:3000000]
        while i &gt; 1
            i = isodd(i) ? 3 * i + 1 : i &gt;&gt; 1
            sum += 1
        end
    end
    sum
end

println(main())


Maybe the comparison isn't fair, but I'd like to know how to improve my Haskell code to bring it on par with other high-level languages such as Julia and JavaScript.

While memoization and parallelization would definitely help, currently I'm concerned with efficient iteration and arithmetic.
Your initial version - 6.834 seconds.

Version with quot and even operations replaced with bitwise - 6.651 seconds.

This version - 0.928 seconds:

import Data.Bits

tOdd sum 1 = sum
tOdd sum x = tEven (sum + (tEven2 0 x)) (x - 1)

tEven sum x = tOdd (sum + (tOdd2 0 x)) (x - 1)

tEven2 sum x | (x .&amp;. 2) == 0 = tEven2 (sum + 1) (x `shiftR` 1)
tEven2 sum x | otherwise      = tOdd2 (sum + 1) (x `shiftR` 1)

tOdd2 sum 1 = sum
tOdd2 sum x = tEven2 (sum + 1) (3 * x + 1)

main = print . show $ tEven (0 :: Int) (3000000 :: Int)


The previous with -O3 -fllvm -optlo-O3 flags - 0.686 seconds.

The previous with all functions supported with INLINE pragma - 0.604 seconds.

More than 10 times faster than initially :)

Yes, low-level numeric operations and iterations are hard in Haskell, the language doesn't suite well for this.