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.

Answer 2

You're probably hoping that the compiler will perform tail call optimization on your method. Unfortunately, this definition of mySum is not tail-call optimizable. What is required for it to be is for the last function being called to be the recursive call, so in this case you'd want mySum to be the last function called. However, the last function being called in your definition is (+), not mySum. You could instead write it as @DonStewart has suggested, who managed to type out that solution before I was able to.

Answer 3

Edit: I just realized that the question is a duplicate and I have basically reinvented its answer from Does Haskell have tail-recursive optimization?

GHC evaluates expressions using what is known as lazy evaluation. The most relevant feature of lazy evaluation for this discussion is what is known as "left-most, outermost evaluation" or normal-order evaluation. To see normal-order evaluation in action, let's follow the evaluation of two implementations of sum, a foldr implementation and a foldl implementation:

foldr (+) 0 (1:2:3:[])
1 + foldr (+) 0 (2:3:[])
1 + (2 + foldr (+) 0 (3:[]))
1 + (2 + (3 + foldr (+) 0 [])))
1 + (2 + (3 + 0))
1 + (2 + 3)
1 + 5
6

Note that because the recursive call to foldr is not left-most, outermost, lazy evaluation cannot reduce it. However, because (+) is strict in its second argument, the right hand side will be evaluated, leaving behind a chain of additions. Because the call to (+) is left-most, outermost, this implementation is similar to your implementation of sum.

One often hears that foldl is more efficient because of tail recursion, but is it so?

foldl (+) 0 (1:2:3:[])
foldl (+) (0+1) (2:3:[])
foldl (+) ((0+1)+2) (3:[])
foldl (+) (((0+1)+2)+3) []
((0+1)+2)+3
(1+2)+3
3+3
6

Note a few differences. First, the recursive call to foldl is left-most outermost and, because it is reduced by normal-order evaluation, does not take up any extra space on the stack. However, the calls to (+) are not reduced and do take up space on the stack. This should be enough to convince you that "tail recursion" is not sufficient to prevent space leaks in GHC.

So, we can use a tail position call to prevent the build-up of thunks representing calls to foldl (or sum' in Don's version), but how can we prevent the build-up of thunks for (+)? We can use strictness annotations, or let foldl' add them for us:

foldl' (+) 0 (1:2:3:[])
foldl' (+) 1 (2:3:[])
foldl' (+) 3 (3:[])
foldl' (+) 6 []
6

Note that this takes constant stack space and constant heap space.

In conclusion, if your recursive calls are left-most, outermost (which corresponds to tail position) they can be reduced by lazy evaluation. This is necessary but not sufficient in preventing the evaluation of your recursive function from using O(n) stack and heap space. foldl and foldr style recursion by themselves both take O(n) stack and heap space. foldl-style recursion with strictness annotations on accumulating parameters is necessary to get evaluation to operate in constant space.