What optimization technique does ghci use to speed up recursive map?

Question

Say I have the following function:

minc = map (+1)
natural = 1:minc natural

It seems like it unfolds like this:

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...
...                                                                

Although it's lazily evaluated, to build each new number n in the list is has to unfold an expression n times which gives us O(N^2) complexity. But by the execution time I can see that the real complexity is still linear!

Which optimization does Haskell use in this case and how does it unfold this expression?

Answer 1

The list of naturals is being shared between each recursive step. The graph is evaluated like this.

1:map (+1) _
 ^         |
 `---------'

1: (2 : map (+1) _)
      ^          |
      `----------'

1: (2 : (3 : map (+1) _)
           ^          |
           `----------'

This sharing means that the code uses O(n) time rather than the expected O(N^2).