GHC优化

Question

下面两个Haskell函数的区别似乎仅在于索引变量是隐式的还是显式的，但是性能上的差异是两个数量级。

这个函数大约需要0.03秒来计算mfib 30：

let mfib = (map fib [0..] !!)
  where
    fib 0 = 0
    fib 1 = 1
    fib x = mfib (x-1) + mfib (x-2)

对于mfib 30，此功能大约需要3秒：

let mfib i = map fib [0..] !! i
  where
    fib 0 = 0
    fib 1 = 1
    fib x = mfib (x-1) + mfib (x-2)

我猜想它与GHC内联规则有关，并一直试图添加内联/noinline杂注以获得匹配性能。

编辑:我理解如何查找懒散列表可以用来回忆录fib函数，以及为什么传统的fib定义非常慢。我期待着回忆录在第二个功能和第一个功能中发挥作用，但我不明白为什么不是。

Answer 1

在查看desugared代码时，更容易理解这些差异，因此这里有两个函数的部分desugared版本。

let mfib = let fib 0 = 0
               fib 1 = 1
               fib x = mfib (x-1) + mfib (x-2)
           in (!!) (map fib [0..])

对比

let mfib = \i ->
               let fib 0 = 0
                   fib 1 = 1
                   fib x = mfib (x-1) + mfib (x-2)
               in map fib [0..] !! i

注意，在第二个程序中，表达式map fib [0..]出现在\i -> ...中，因此它将(通常，不进行优化)对i的每个值进行计算。请参阅When is memoization automatic in GHC Haskell?