什么“浮出”？意思？ [英] What does "floated out" mean?

问题描述

在 Haskell维基上，我读到了这个：

  fib = 
 let fib'0 = 0 
 fib'1 = 1 
 fib'n = fib （b-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）
 map fib'[0 ..] !! x 
  

因为，在第二种情况下，fib'参数x，因此它不能被浮动。

我不明白这是什么意思。

1. 浮出是什么意思？为什么在每次调用时都会重新定义 fib'>
fib ？

2. 这是一个eta扩展吗？
   

Floated out仅仅意味着： $ b $ b

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

if ... 没有提及 x ，那么它可以被浮动为lambda：

  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 ，因此可以从memoisation中受益。

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

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

On the 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 ..] !!)

is more efficient than this:

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

Because, "In the second case fib' is (re-)defined for every argument x, thus it cannot be floated out."

I don't understand what this means.

1. What does "floated out" mean? How is it an optimization?
2. Why is fib' being redefined for each invocation of fib?
3. Is this an eta-expansion or not?

解决方案

It's not a very good explanation.

"Floated out" simply means that in:

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

if ... does not mention x then it can be floated out of the lambda:

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

which means it will only be computed once,¹ which could save a lot of time if ... is expensive. However, GHC is conservative about performing optimisations like this, since they can introduce space leaks. (Though it does do so for the second definition if you give it a type signature, as Daniel Fischer points out in his answer.)

This isn't about automatic optimisation, though. The first snippet defines fib' outside of the lambda, whereas the second defines it inside (the lambda is implicit in fib x = ..., which is equivalent to fib = \x -> ...), which is what the quote is saying.

Even that's not really relevant, however; what's relevant is that in the first snippet, map fib' [0 ..] occurs outside the lambda, and so its result is shared among all applications of the lambda (in that code, the "lambda" arises from the partial application of (!!)). In the latter, it's inside the lambda, and so likely to be recomputed for every application of fib.

The end result is that the former implementation caches the values and so is far more efficient than the latter. Note that the first snippet's efficiency is dependent on the fact that fib' doesn't recurse directly, but instead through fib, and therefore benefits from the memoisation.

It's related to eta-expansion; the latter snippet is an eta-expansion of the first. But the statement you quoted doesn't explain what's going on at all.

¹ Note that this is implementation-specific behaviour, and not part of Haskell's semantics. However, all reasonable implementations will behave in this manner.

这篇关于什么“浮出”？意思？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！