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

to build each new number n in the list is has to unfold an expression n times which gives us O(N²) complexity.

不完全是。以这种方式展开前 N 个数字的复杂度确实是 O(N²)^{看来我错了[1]}。但是如果你只请求第 N 个数字，那么它实际上是这样计算的：

(!!n) $ 1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc...
(!!n-1) $ minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc...
(!!n-1) $ (1+1):minc(minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc...
            -- note that `(1+1)` isn't actually calculated!
(!!n-2) $ minc(minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc...
(!!n-2) $ ((1+1)+1):minc(minc(minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc...
            -- again, neither of the additions is actually calculated.
(!!n-3) $ minc(minc(minc(1:minc(1:minc(1:minc(1:minc(1:minc(1:minc...
(!!n-3) $ ((...)+1):minc(minc(minc(minc(1:minc(1:minc(1:minc(1:minc(1:minc...
...
(!!n-n) $ ((...+1)+1) : minc(minc(...minc(minc(1:minc(...
           ╰─ n ─╯
(!!0) $ (n+1) : _
n+1

每次增加 N 只需要固定数量的两个步骤，一旦达到索引，再加上 N 添加 - 这仍然是O(N) 总而言之.

这里的关键是，基本上，map 只对整个列表应用一次。它是完全懒惰的，即要产生一个 _:_ thunk，它只需要知道列表至少有 length 1，但实际元素根本不重要。

这样，我们写的 minc(minc(...(minc(1 : ... 只需一步就被 (... + 1) : minc(... 替换了。

^[1]_{事实证明，即使我们 sum 第一个 N个数，在O(N)中完成。不知道怎么样。}

Answer 2

自然数列表在每个递归步骤之间共享。该图是这样计算的。

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

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

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

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

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

What optimization technique does ghci use to speed up recursive map?

optimization

haskell

expression