假设我有以下功能:
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:map (+1) _
^ |
`---------'
1: (2 : map (+1) _)
^ |
`----------'
1: (2 : (3 : map (+1) _)
^ |
`----------'
这种共享意味着代码使用 O(n) 时间而不是预期的 O(N^2)。
关于haskell - ghci 使用什么优化技术来加速递归映射？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28913860/