在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

维基页面指出 "In the second case [fib2], fib' is redefined for every argument x"。我正在寻找一个初学者友好的解释为什么会发生这种情况，一般来说，是否有更多这样的隐藏副作用？

维基页面也有一个 link 对 eta reduction 的解释，它指出表达式和它的 eta-reduction 是等价的。所以，如果 fib2 是 fib1 的 eta 抽象，为什么它们不等价？

Answer 1

你的最后一点也许是最重要的一点 - fib1 和 fib2 确实是 等价的，编译器完全可以自由转换一个变成另一个。由于此转换对指称语义没有影响，仅对操作语义有影响，因此通常将其称为优化，如果它 "improves" 程序的操作语义。问题是很难说出 "improves" 的真正含义。

维基页面指出

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

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

区别在于一个叫做共享的特性。在 fib1 中，map fib' 中的 fib' 调用将在 fib' 函数内的 fib1 的不同调用之间共享。这意味着只要计算函数，就必须保留整个列表 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)

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

What are the semantics of adding the parameter in LHS of function definition in haskell?

haskell

functional-programming

lambda-calculus