The canonical implementation of length :: [a] -> Int is:

length [] = 0
length (x:xs) = 1 + length xs

which is very beautiful but suffers from stack overflow as it uses linear space.

The tail-recursive version:

length xs = length' xs 0
  where length' [] n = n
        length' (x:xs) n = length xs (n + 1)

doesn't suffer from this problem, but I don't understand how this can run in constant space in a lazy language.

Isn't the runtime accumulating numerous (n + 1) thunks as it moves through the list? Shouldn't this function Haskell to consume O(n) space and lead to stack overflow?

(if it matters, I'm using GHC)