title: Why does s ++ t not lead to a stack overflow for large s?
body: <p>I'm wondering why</p>
  
  <pre><code>Prelude&gt; head $ reverse $ [1..10000000] ++ [99]
  99
  </code></pre>
  
  <p>does not lead to a stack overflow error. The ++ in the prelude seems straight forward and non-tail-recursive:</p>
  
  <pre><code>(++) :: [a] -&gt; [a] -&gt; [a]
  (++) []     ys = ys
  (++) (x:xs) ys = x : xs ++ ys
  </code></pre>
  
  <p>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.</p>
  
  <p><em>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 ++:</em></p>
  
  <p>{-# RULES
  "++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs) ys
    #-}</p>
  
  <p>*Is that what helps avoiding the stack overflow? Could someone provide some hint for what's going on in this piece of code?** </p>