haskell - "floated out"是什么意思？

Question

在 Haskell wiki I read that this :

fib =
    let fib' 0 = 0
        fib' 1 = 1
        fib' n = fib (n - 1) + fib (n - 2)
    in  (map fib' [0 ..] !!)

比这更有效:

 fib x =
    let fib' 0 = 0
        fib' 1 = 1
        fib' n = fib (n - 1) + fib (n - 2)
    in  map fib' [0 ..] !! x

因为，“在第二种情况下，fib' 是(重新)为每个参数 x 定义的，因此它不能被浮出。”

我不明白这是什么意思。

“浮出水面”是什么意思？它是如何优化的？

为什么是 fib'为每次调用 fib 重新定义?

这是否是 eta 扩展？

Answer 1

这不是一个很好的解释。

“浮出”只是意味着:

\x -> let y = ... in z

如果 ...没有提到 x 那么它可以从 lambda 中浮出:

let y = ... in \x -> z

这意味着它只会计算一次，1 如果 ... 可以节省大量时间太贵了。然而，GHC 对执行这样的优化持保守态度，因为它们会引入空间泄漏。 (尽管如果你给它一个类型签名，它会为第二个定义这样做，正如 Daniel Fischer 在他的回答中指出的那样。)

不过，这与自动优化无关。第一个片段定义 fib'在 lambda 之外，而第二个在内部定义它(lambda 隐含在 fib x = ... 中，相当于 fib = \x -> ... )，这就是引用的意思。

然而，即使这也不是真正相关的。相关的是在第一个片段中， map fib' [0 ..]发生在 lambda 之外，因此它的结果在 lambda 的所有应用程序之间共享(在该代码中，“lambda”来自 (!!) 的部分应用程序)。在后者中，它位于 lambda 内部，因此很可能会为 fib 的每个应用程序重新计算。 .

最终结果是前一个实现缓存了值，因此比后者效率高得多。请注意，第一个片段的效率取决于 fib'不直接递归，而是通过 fib ，因此受益于内存。

它与eta-expansion有关；后一个片段是第一个片段的 eta 扩展。但是你引用的声明根本没有解释发生了什么。

1 请注意，这是特定于实现的行为，而不是 Haskell 语义的一部分。但是，所有合理的实现都会以这种方式运行。