Why does s ++ t not lead to a stack overflow for large s?
- by martingw
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
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?