haskell - 为什么 foldr 使用辅助函数？

Question

在解释foldr对于 Haskell 新手来说，规范的定义是

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

但是在 GHC.Base 中， foldr定义为

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

似乎这个定义是对速度的优化，但我不明白为什么要使用辅助函数 go会让它更快。源评论( see here )提到了内联，但我也看不出这个定义将如何改进内联。

Answer 1

我可以添加一些关于 GHC 优化系统的重要细节。
foldr 的幼稚定义传递一个函数。调用函数存在固有的开销——尤其是当函数在编译时未知时。如果在编译时知道函数的定义，那么能够内联函数的定义会非常好。

有一些技巧可以在 GHC 中执行该内联 - 这是其中的一个示例。一、foldr需要内联(我稍后会解释为什么)。 foldr的幼稚实现是递归的，因此不能内联。因此，工作人员/包装器转换应用于定义。 worker 是递归的，但包装器不是。这允许 foldr被内联，尽管递归了列表的结构。

当foldr是内联的，它也会创建其所有本地绑定(bind)的副本。它或多或少是一个直接的文本内联(以一些重命名为模，并在脱糖传递之后发生)。这就是事情变得有趣的地方。 go是一个本地绑定(bind)，优化器可以查看它的内部。它注意到它在本地范围内调用了一个函数，它命名为 k . GHC 通常会删除 k完全变量，并将其替换为表达式 k减少到。然后，如果函数应用程序适合内联，则此时可以内联 - 完全消除调用一等函数的开销。

让我们看一个简单而具体的例子。该程序将回显一行输入，所有尾随 'x'删除的字符:

dropR :: Char -> String -> String
dropR x r = if x == 'x' && null r then "" else x : r

main :: IO ()
main = do
    s <- getLine
    putStrLn $ foldr dropR "" s

首先，优化器将内联 foldr的定义和简化，导致代码看起来像这样:

main :: IO ()
main = do
    s <- getLine
    -- I'm changing the where clause to a let expression for the sake of readability
    putStrLn $ let { go [] = ""; go (x:xs) = dropR x (go xs) } in go s

这就是 worker-wrapper 转换允许的事情。我将跳过剩余的步骤，但很明显 GHC 现在可以内联 dropR 的定义，消除函数调用开销。这就是巨大的性能胜利的来源。