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

说我有以下功能:

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在这种情况下使用了哪种优化,以及它如何展开这个表达式？

1> Alex..：

---

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

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

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

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

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

---

这里没有"优化",共享评估的唯一原因是因为只有一个"自然",只有一个存在于此列表中的位置.起初它只是一个thunk`1:minc natural`但是当你评估第二个元素时,它变成了一个列表1 cons`map(+1)(1:ref to tail of natural)``1 cons 2 cons` map(+1)(2:ref to tail of tail of natural)`,如你所见,下一步将是O(1),依此类推.