非 pointfree 风格要慢得多

Question

我有以下经常被引用的代码，用于计算 Haskell 中的第 n 个斐波那契数：

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不敢苟同。有人对这种行为有解释吗？

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 并不总是执行此转换，因为这并不总是一种优化。第一个使用的缓存永远保存在内存中。这可能会导致内存浪费，具体取决于手头的功能。

Answer 2

我试图找到它，但被删除了。我想我在家里的电脑上有它。我读到的是使用定点的函数本质上更快。使用定点还有其他原因。我在写这个迭代斐波那契函数时遇到了一个。我想看看迭代版本的性能如何，然后我意识到我没有现成的衡量方法。我是 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]

非 pointfree 风格要慢得多

Non-pointfree style is substantially slower

haskell

memoization