Why does s ++ t not lead to a stack overflow for large s?

Question

I'm wondering why

Prelude> head $ reverse $ [1..10000000] ++ [99]
99

does not lead to a stack overflow error. The ++ in the prelude seems straight forward and non-tail-recursive:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

EDIT: Initially, I thought the issue has something to do with the way ++ is defined in the prelude, especially with the rewriting rules, hence the question continued as below. The discussion showed me that this is not the case. I think now that some lazy evaluation effect causes the code to run without a stack overflow, but I don't quite figure how.

So just with this, it should run into a stack overflow, right? So I figure it probably has something to do with the ghc magic that follows the definition of ++:

{-# RULES "++" [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys #-}

Is that what helps avoiding the stack overflow? Could someone provide some hint for what's going on in this piece of code?*

Answer 1

EDIT: The answer below is completely irrelevant, if not downright wrong. Don Stewart, who demonstrates that he actually understands lazy evaluation, has the right explanation.

---

If you run ghc -ddump-simpl, you'll see that the functions being used are GHC.Base.++ and GHC.List.reverse. These functions are engineered not to overflow the stack on large lists. What you see in the Prelude is a "reference implementation," not the code that is actually compiled.

Here's some code I dug out of the GHC source distribution:

reverse                 :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
reverse                 =  foldl (flip (:)) []
#else
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
#endif

And this:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

{-# RULES
"++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs)     ys
  #-}

In the first case, it should be clear what's going on. In the second, I'm a little fuzzy on the rewrite rules...

Answer 2

The ++ in the prelude seems straight forward and non-tail-recursive ... So just with this, it should run into a stack overflow, right?

Not-tail-recursive is often better than tail-recursive in Haskell, because not-tail-recursive things can be lazy. The definition you list there is much better than a tail-recursive one, because a tail-recursive one would keep recursing and generate the entire list, even if you need only the first element; whereas a non-tail recursive one would do only as much work as necessary.

Answer 3

This doesn't stack overflow - even in the interpreter, where there are no optimizations and no rewrite rules - because it doesn't use the stack.

Look at the definition of (++), for example,:

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

The key thing is x : (xs ++ ys) -- that is, it is recursion guarded by the (:) "cons" constructor. Because Haskell is lazy, it allocates a thunk for the cons operation, and the recursive call goes onto this (heap-allocated) thunk. So your stack allocation is now heap allocation, which can expand quite a bit. So all this does is walk the big list, allocating new cons objects on the heap to replace the ones it is traversing. Easy!

"reverse" is a bit different:

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

That is a tail recursive, accumulator-style function, so again, it will allocate on the heap.

So you see, the functions rely on using cons cells on the heap, instead of on the stack, hence no stack overflow.

To really nail this, look at the runtime stats from the GC vm:

$ time ./B +RTS -s
99

         833 MB total memory in use (13 MB lost due to fragmentation)
         Generation 0:  3054 collections,     0 parallel,  0.99s,  1.00s elapsed
         %GC time      82.2%  (85.8% elapsed)

There's your big list -- it is allocated on the heap, and we spend 80% of the time cleaning up cons nodes that are created by (++).

Lesson: you can often trade stack for heap.