ghci使用什么优化技术来加速递归映射？

Question

说我有以下功能:

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

它似乎像这样展开:

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

虽然它被懒惰地评估,但是要n在列表中构建每个新数字,必须展开表达n时间,这给我们带来了O(N^2)复杂性.但是通过执行时间,我可以看到真正的复杂性仍然是线性的!

Haskell在这种情况下使用了哪种优化,以及它如何展开这个表达式？

Answer 1

每个递归步骤之间共享自然列表.图表的评估方式如下.

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

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

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

这种共享意味着代码使用O(n)时间而不是预期的O(N ^ 2).