什么"浮出来"是什么意思？

Question

在Haskell维基上,我读到了这个:

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定义的,因此它不能浮出来."

我不明白这意味着什么.

1. 什么"浮出来"是什么意思？它是如何优化的？
2. 为什么fib'要为每次调用重新定义fib？
3. 这是eta扩张吗？

Answer 1

这不是一个很好的解释.

"浮出水面"仅仅意味着:

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

如果...不提x那么它可以浮出 lambda:

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

这意味着它只会计算一次,¹如果...价格昂贵,可以节省大量时间.但是,GHC对于执行这样的优化是保守的,因为它们会引入空间泄漏.(虽然如果你给它一个类型签名,它会为第二个定义这样做,正如Daniel Fischer在他的回答中指出的那样.)

但这与自动优化无关.第一个片段定义fib'在lambda之外,而第二个片段定义在lambda内部(lambda隐含在fib x = ...,相当于fib = \x -> ...),这就是引用所说的内容.

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

最终结果是前一个实现缓存了值,因此比后者更有效.请注意,第一个片段的效率取决于fib'不直接递归的事实,而是通过fib记忆,从而受益于记忆.

它与eta扩展有关; 后一个片段是第一个的eta扩展.但你引用的陈述并没有解释究竟发生了什么.

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

Answer 2

艾哈德的回答很好地解释了事情,但有一点

最终结果是前一个实现缓存了值,因此比后者更有效.

这有时是错误的.

如果您编译包含带优化的定义的模块(我只检查了-O2,而不是-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内,因此列表不能重用于递归调用,每个递归调用都会创建一个新列表...