非点免费风格要慢得多

Question

我有以下常用的代码来计算Haskell中的第n个Fibonacci数:

fibonacci :: Int -> Integer
fibonacci = (map fib [0..] !!)
    where fib 0 = 0
          fib 1 = 1
          fib n = fibonacci (n-2) + fibonacci (n-1)  

使用这个,我可以做如下调用:

ghci> fibonacci 1000

并得到几乎即时的答案.

但是,如果我修改上面的代码,使它不是无点样式,即

fibonacci :: Int -> Integer
fibonacci x = (map fib [0..] !!) x
    where fib 0 = 0
          fib 1 = 1
          fib n = fibonacci (n-2) + fibonacci (n-1) 

它要慢得多.在某种程度上,如一个电话

ghci> fibonacci 1000

挂起.

我的理解是上面两段代码是等价的,但GHCi要求不同.有没有人对这种行为有解释？

Answer 1

要观察差异,你应该看看Core.我的猜测归结为比较(粗略)

let f = map fib [0..] in \x -> f !! x

至

\x -> let f = map fib [0..] in f !! x

后者将f在每次调用时从头开始重新计算.前者没有,f为每次调用有效地缓存相同的内容.

碰巧在这种特定情况下,一旦启用优化,GHC就能够将第二个优化为第一个.

但请注意,GHC并不总是执行此转换,因为这并不总是优化.第一个使用的缓存永远保存在内存中.这可能会导致内存浪费,具体取决于手头的功能.