title: What optimization technique does ghci use to speed up recursive map?
body: <p>Say I have the following function:</p>
  
  <pre><code>minc = map (+1)
  natural = 1:minc natural
  </code></pre>
  
  <p>It seems like it unfolds like this:</p>
  
  <pre><code>1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc...
  1:2:minc(minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc...
  1:2:minc(2:minc(2:minc(2:minc(2:minc(2:minc(2:minc(2:minc(2:minc(minc...
  1:2:3:minc(3:minc(3:minc(3:minc(3:minc(3:minc(3:minc(3:minc(minc(minc...
  ...                                                                
  </code></pre>
  
  <p>Although it's lazily evaluated, to build each new number <code>n</code> in the list is has to unfold an expression <code>n</code> times which gives us <code>O(N^2)</code> complexity. But by the execution time I can see that the real complexity is still linear!</p>
  
  <p>Which optimization does Haskell use in this case and how does it unfold this expression?</p>