“浮出”是什么意思？

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 

因为，“在用于每个参数x被（重新）限定的第二壳体FIB”，因而它不能被漂走了。“

我不明白这是什么意思。

1. “浮出”是什么意思？它是如何优化？
2. 为什么fib'被重新定义为每次调用fib？
3. 这是一个eta扩展与否？

Answer 1

这不是一个很好的解释。

“浮出” 只是意味着，在：

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

如果...没有提到X然后它可以是浮出拉姆达的：

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

，这意味着它将只计算一次，如果...昂贵，可以节省大量时间。但是，GHC对于执行这样的优化是保守的，因为它们会引入空间泄漏。 （虽然它确实为第二个定义，如果你给它一个类型签名，就像Daniel Fischer在他的答案中指出的那样。）

虽然这不是自动优化。第一个片段定义了lambda之外的fib'，而第二个片段定义了其内部（lambda隐含在fib x = ...中，相当于fib = \x -> ...），这就是引用的内容。

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

最终的结果是前一个实现缓存了值，所以比后者更高效。请注意，第一个代码段的效率取决于以下事实：fib'不直接递归，而是通过fib，因此受益于记忆。

它与eta-expansion相关;后面的片段是第一个的eta扩展。但是你所引用的陈述并不能解释发生了什么事情。

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

Answer 2

ehird的回答解释了事情非常好，但是有一点

最终的结果是，前者的实现缓存值，因此比后者更为有效。

这有时是错误的。

如果您编译包含或者与最佳化定义模块（我检查只-02，不-O1，当然只有GHC），有几种情况要考虑：

1. 没有类型的第一个定义签名
2. 类型签名第二定义fib :: Int -> Integer
3. 多态型的第一个定义fib :: Num a => Int -> a
4. 而不类型签名第二个定义
5. 类型签名fib :: Num a => Int -> a

第二定义在情况1中，单态限制产生的类型fib :: Int -> Integer和列表map fib' [0 .. ]跨越的fib所有调用共享。这意味着，如果您查询fib (10^6)，您将获得内存中第一百万（+1）个斐波那契数字的列表，并且只有在垃圾收集器可以确定它不再使用时才会收集它。这通常是内存泄漏。

在情况2中，结果（正在芯）实际上是相同的外壳1

在情况4中，在列表中不跨越不同fib顶层调用共享（当然;结果可以有很多类型，所以会有很多列表共享），但是它在每个顶级调用中被实例化并且被重复用于来自fib'的调用，所以计算fib n需要O（n）加法和O（n^2）步骤列表。这并不算糟糕。计算完成后收集清单，因此不会有空间泄漏。

情况3是几乎相同为4

案例5，但是，比幼稚递归更糟。由于它是明确的多态，并且列表绑定在lambda内部，所以列表不能被递归调用重用，每次递归调用都会创建一个新列表...