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

Question

我是haskell的初学者,并试图了解Let vs Where wiki页面.最后有一个例子,x在函数定义的左侧添加参数会fib改变语义.

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

维基页面声明"在第二种情况下[ fib2],为每个参数x"重新定义了fib'.我正在寻找一个初学者友好的解释为什么会发生这种情况,一般来说,是否有更多这样隐藏的副作用？

维基页面还有一个关于eta减少的解释的链接,该解释表明表达式和它的eta减少是等价的.那么,如果fib2是eta抽象fib1,为什么它们不等同？

Answer 1

你的最后一点可能是最重要的- fib1并且fib2 是确实ETA当量,编译器是完全免费的变换相互转化.由于这种转换对指称语义没有影响,只有操作语义,如果它"改进"程序的操作语义,它通常被称为优化.麻烦的是,很难说出"改进"的真正含义.

维基页面说明

编译器无法知道您是否打算这样做 - 虽然它增加了时间复杂度,但可能会降低空间复杂性.

这是正确的 - 通常,这种"优化"可能不是优化,具体取决于您如何衡量绩效.因此,一般情况下,编译器不会执行此优化,如果他们愿意,请将这样做的负担留给程序员,除非确实它确实会提高代码的性能.

差异是一种称为共享的特征.在fib1,fib'调用map 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' ...

因此,它不会将定义从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)