haskell - 在haskell中函数定义的LHS中添加参数的语义是什么？

Question

我是 haskell 的初学者，试图理解 Let vs Where wiki page 。最后有一个示例，在函数定义 fib 的左侧添加参数 x 会更改语义。

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

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

wiki 页面指出“在第二种情况 [fib2] 中，fib' 会为每个参数 x 重新定义”。我正在寻找一个适合初学者的解释，解释为什么会发生这种情况，一般来说，是否还有更多这样的隐藏副作用？

维基页面还有一个关于 eta reduction 的解释的链接，它表明表达式及其 eta 约简是等价的。那么，如果 fib2 是 fib1 的 eta 抽象，为什么它们不等价呢？

Answer 1

你的最后一点也许是最重要的 - fib1 和 fib2 确实是 eta 等价的，并且编译器完全可以自由地将一种转变为另一种。由于这种转换对指称语义没有影响，只影响操作语义，因此如果它“改进”了程序的操作语义，则通常将其称为优化。问题是很难说出“改进”的真正含义。

维基页面指出

The compiler cannot know whether you intended this -- while it increases time complexity it may reduce space complexity.

确实如此 - 一般来说，这种“优化”可能不是优化，具体取决于您衡量性能的方式。因此，一般来说，编译器不会执行此优化，如果程序员愿意，则将这样做的负担留给程序员，除非确实确定它确实会提高代码的性能。

这种差异是一种称为共享的特征。在 fib1 中，map fib' 中的 fib' 调用将在 fib1 内部的不同调用之间共享fib' 函数。这意味着只要计算函数，就必须保留整个列表map fib' [0..n]。在某些情况下，这可能会降低性能，但在这种情况下，它可以为您节省大量递归函数调用。在 fib2 中，每个 map fib' 都是单独计算的，因为参数位于 let 之外。考虑这个程序，即使没有优化，它也相当于 fib1:

fib3 :: Int -> Integer 
fib3 =
   let fib' 0 = 0
       fib' 1 = 1
       fib' n = fib1 (n - 1) + fib1 (n - 2)
    in \x -> map fib' [0 ..] !! x

\x -> .. 的位置至关重要 - 这里是 let fib' = .. in\x -> map fib' .. 但是在 fib2 中，它是 \x -> let fib' = .. in map fib' ...

Thus it will not float the definition out from under the binding of x.

这显然取决于您使用的特定编译器以及编译程序的方式!我假设这个 wiki 页面是在编译器不够智能来找出这个特定示例的时候编写的，但是使用 GHC 7.10.3 和 -O2，编译器实际上生成 这两个程序的代码相同。

如果您在没有优化的情况下进行编译或解释，性能差异将变得显而易见。这不是由于单态限制 - 即使您为函数提供单态类型，它仍然存在:

fib1 :: Int -> Integer 
fib1 = ..

fib2 :: Int -> Integer 
fib2 x = ..

区别很明显:

>:set +s
>fib2 32
2178309
(10.86 secs, 6,063,137,456 bytes)
>fib1 32
2178309
(0.00 secs, 0 bytes)