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)。