Why isn't this recursive function being optimized? (Haskell)

Question

I wrote my own 'sum' function in Haskell:

mySum [a] = a
mySum (a:as) = a + mySum as

And tested it with

main = putStrLn . show $ mySum [1 .. 400000000]

Only to receive a stack overflow error.

Using the Prelude's sum in the same manner:

main = putStrLn . show $ sum [1 .. 400000000]

I get no stack overflow.

It could be the huge list I'm evaluating, especially if the list passed to my function is being evaluated strictly, though my only reason for not suspecting this is that using the Prelude's sum with the same list I get no error.

Answer 1

Your function fails with a stack overflow because it isn't tail recursive. One stack frame is consumed on each call holding onto the partial sum of 'a' at each step.

The Prelude's sum is implemented with a tail call:

sum     l       = sum' l 0
   where
    sum' []     a = a
    sum' (x:xs) a = sum' xs (a+x)

{-# SPECIALISE sum     :: [Int] -> Int #-}
{-# SPECIALISE sum     :: [Integer] -> Integer #-}
{-# INLINABLE sum #-}

which doesn't consume stack space.

Note that the specialize and inline pragmas are necessary to expose the strictness information that makes the 'a' accumulator safe to use without thunks accumulating. A more modern version would be:

    sum' []     !a = a
    sum' (x:xs) !a = sum' xs (a+x)

to make the strictness assumptions explicit. This is almost equivalent to the foldl' version wrt. strictness.