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