非pointfree风格基本上是慢

我有以下的，用于在Haskell计算第n个斐波纳契数经常被引用的代码：非pointfree风格基本上是慢

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

并收到几乎即时的答案。

然而，如果我修改上面的代码，以便它不是在pointfree风格，即

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有所不同。有没有人有这种行为的解释？

来源

2015-10-04 MadMonty

第一个定义更像'fibonacci = let k = map fib [0 ..] in \ x - > k !! x'。它可能共享结果列表，而不是每次重新计算结果。 – melpomene

嗯，所以我很满意，这是“共享”（记忆），使第一个超级快。但为什么对于第二个呢？ – MadMonty

您正在GHCI中运行您的代码，没有进行优化。试着用'-O2'编译这两个函数，看看GHC是否足够聪明，可以为你解决问题。 – user2407038

要观察差异，你应该看看Core。我猜想，这可以归结为比较（大约）

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

到

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

后者将重新计算f从头每次调用。前者不会为每次调用有效缓存相同的f。

在这种特殊情况下，一旦启用优化，GHC就能够优化第二个到第一个。

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

来源

2015-10-04 18:24:31 chi

我试图找到它，但被删除。我想我在家里的电脑上有它。我读到的是使用固定点的函数本质上更快。使用固定点还有其他原因。我在写这个迭代的斐波那契函数时遇到过一个问题。我想看看迭代版本的表现如何，然后我意识到我没有现成的方法来衡量。我是一名Haskell新手。但是这是一个迭代版本供有人测试。我无法得到这个定义，除非我在第一个最后一个函数之后使用了点。我无法进一步减少它。 [0,1]参数是固定的，不能作为参数值提供。

Prelude> fib = last . flip take (iterate (\ls -> ls ++ [last ls + last (init ls)]) [0,1]) 
Prelude> fib 25

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025]

来源

2018-02-20 20:53:25 fpmora

非pointfree风格基本上是慢

回答

相关问题