2014-11-22 59 views
8

在Haskell的維基教科書,如下foldr相似被實現。但據我所知,acc是操作的標識值(例如0表示總和或1表示產品),其值在執行函數期間不會改變。那麼爲什麼它在這裏和其他文本中被稱爲累加器,這意味着它會逐步改變或累積一個值?累加器在foldr相似

我可以看到一個累加器在左邊摺疊中是相關的,比如foldl,但是wikibook解釋是不正確的,只是對稱性,在這種情況下它是錯誤的?

+0

積累與foldl從foldr相似左側和積累情況從右側發生。 – 2014-11-22 04:44:34

+3

是的,這很有趣。將'f'的第二個參數稱爲累加器可能更合適。我通常使用'z'(connoting zero)或'nil'(包含它所對應的構造函數)編寫foldr-esque模式。 – luqui 2014-11-22 04:46:23

回答

8

考慮您提供基於(正確的)定義一個簡單的foldr表達的評價:

foldr (+) 0 [1,2,3,4] 
= 1 + foldr (+) 0 [2,3,4] 
= 1 + 2 + foldr (+) 0 [3,4] 
= 1 + 2 + 3 + foldr (+) 0 [4] 
= 1 + 2 + 3 + 4 + foldr (+) 0 [] 
= 1 + 2 + 3 + 4 + 0 
= 10 

所以,你是對的:acc並沒有真正「積累」任何東西。它永遠不會超過0以外的值。

爲什麼它稱爲「acc」,如果它不是累加器?與foldl相似? Hysterical raisins? A lie to children?我不確定。

編輯:我還要指出,foldr的GHC實現使用z(推測爲零)而不是acc

+0

那麼,它的累加器不會改變:P – alternative 2014-11-22 13:43:13

1

accfoldr的情況下沒有真正積累任何東西,正如已經指出的那樣。

我想補充說,沒有它,目前還不清楚當輸入是一個空列表時應該發生什麼。

它也改變了f的類型簽名,限制了可以使用的功能。

E.g:

foldr' :: (a -> a -> a) -> [a] -> a 
foldr' f [] = error "empty list???" 
foldr' f (x:[]) = x 
foldr' f (x:xs) = f x (foldr' f xs) 
+0

你描述的是'foldr1',它確實在空列表上出現錯誤。 – 2014-11-23 15:56:34