为什么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会使它更快.源评论(见这里)提到了内联,但我也没有看到这个定义如何改进内联.

Answer 1

我可以添加一些关于GHC优化系统的重要细节.

foldr围绕函数传递的天真定义.调用函数有一个固有的开销 - 特别是在编译时不知道函数时.如果在编译时知道函数的内容,那么能够内联函数的定义真的很棒.

有一些技巧可以在GHC中执行内联 - 这就是它们的一个例子.首先,foldr需要内联(我将在后面讨论).foldr天真的实现是递归的,所以不能内联.因此,将工作者/包装器转换应用于定义.worker是递归的,但包装器不是.foldr尽管对列表结构进行了递归,但这允许内联.

当foldr被内联,它创建所有的本地绑定的副本了.它或多或少是一个直接的文本内联(模数一些重命名,并在desugaring传递后发生).这是事情变得有趣的地方.go是一个本地绑定,优化器可以查看它.它注意到它在本地范围内调用一个函数,它命名为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,消除函数调用开销.这是获得巨大成功的地方.

Answer 2

GHC不能内联递归函数,所以

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

无法内联.但

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

不是递归函数.它是一个非递归函数,具有局部递归定义!

这意味着,作为@bheklilr写入,在map (foldr (+) 0)所述foldr可内联,并因此f与z所取代(+)和0在新的go,并且大的事情可能发生,例如中间值的取消装箱.

Answer 3

正如评论所说:

-- Inline only in the final stage, after the foldr/cons rule has had a chance
-- Also note that we inline it when it has *two* parameters, which are the
-- ones we are keen about specialising!

特别要注意的是"当它有两个参数时,我们可以内联它,这是我们热衷于专业化的参数!"

这就是说,当foldr内联时,它只是为了特定的选择而被内联,f而z不是为了折叠列表的选择.我不是专家,但它似乎可以在类似的情况下内联它

map (foldr (+) 0) some_list

所以内联发生在这一行,而不是在map应用之后.这使得它在更多情况下更容易优化.所有辅助函数都会屏蔽第三个参数,所以{-# INLINE #-}可以做它的事情.

Answer 4

其他答案中没有提到的一个微小的重要细节是GHC,给出了类似的函数定义

f x y z w q = ...

不能内联f,直到所有的参数x,y,z,w,和q应用.这意味着使用worker/wrapper转换来公开一组最小的函数参数通常是有利的,这些函数参数必须在内联发生之前应用.