爲什麼foldr使用輔助函數？

在解釋foldr哈斯克爾新手，規範的定義是爲什麼foldr使用輔助函數？

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）提到了內聯，但我也沒有看到這個定義如何改善內聯。

來源

2014-10-07 Matt Adams

尚未提及的一個細節：ghc只在函數完全應用時內聯，*語法*在其左側。如果你習慣於考慮捲曲和創建漂亮的無點式代碼，這是非常奇怪和醜陋的。這就是爲什麼你有時會在優化代碼中看到'='右邊的愚蠢lambda表達式。 – jberryman 2014-10-07 21:07:34

我可以添加一些關於GHC優化系統的重要細節。

foldr的天真定義傳遞函數。在調用一個函數時有一個固有的開銷 - 特別是當這個函數在編譯時不知道的時候。如果能夠在編譯時知道函數的定義，那將非常好。

有一些技巧可用於在GHC中執行內聯 - 這是他們的一個例子。首先，foldr需要內聯（我會後來爲什麼）。 foldr的幼稚實現是遞歸的，所以不能被內聯。所以一個worker/wrapper轉換被應用於定義。工作人員是遞歸的，但包裝不是。這允許foldr內聯，儘管在列表結構上遞歸。

當foldr被內聯時，它也會創建其所有本地綁定的副本。它或多或少是一個直接的文本內聯（模仿一些重命名，並在脫嫁後發生）。這是事情變得有趣的地方。 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

這就是工作者包裝轉換允許的事情。我將跳過其餘的步驟，但很明顯GHC現在可以內聯dropR的定義，消除函數調用開銷。這是贏得巨大勝利的地方。

在其他的答案沒有提及

來源

2014-10-07 20:27:16 Carl

正如評論說：

-- 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已經應用後，可以內嵌在它像的情況

map (foldr (+) 0) some_list

。這使得它在更多情況下更容易優化。所有幫助函數都會屏蔽第三個參數，因此{-# INLINE #-}可以完成它的工作。

來源

2014-10-07 18:50:52 bheklilr

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替換，並且大的事情可能發生，例如中間值的取消裝箱。

來源

2014-10-07 20:03:44

一個微小重要的細節是GHC，給出一個函數定義像

f x y z w q = ...

不能內聯f，直到所有的x，y，z，w，並q應用的參數。這意味着使用worker/wrapper轉換來公開必須在內聯發生之前必須應用的最小函數參數集合通常是有利的。

來源

2014-10-08 01:54:51

爲什麼foldr使用輔助函數？

回答

相關問題