haskell - 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

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

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?