在Haskell的維基教科書,如下foldr相似被實現。但據我所知,acc是操作的標識值(例如0表示總和或1表示產品),其值在執行函數期間不會改變。那麼爲什麼它在這裏和其他文本中被稱爲累加器,這意味着它會逐步改變或累積一個值?累加器在foldr相似
我可以看到一個累加器在左邊摺疊中是相關的,比如foldl,但是wikibook解釋是不正確的,只是對稱性,在這種情況下它是錯誤的?
在Haskell的維基教科書,如下foldr相似被實現。但據我所知,acc是操作的標識值(例如0表示總和或1表示產品),其值在執行函數期間不會改變。那麼爲什麼它在這裏和其他文本中被稱爲累加器,這意味着它會逐步改變或累積一個值?累加器在foldr相似
我可以看到一個累加器在左邊摺疊中是相關的,比如foldl,但是wikibook解釋是不正確的,只是對稱性,在這種情況下它是錯誤的?
考慮您提供基於(正確的)定義一個簡單的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
。
那麼,它的累加器不會改變:P – alternative 2014-11-22 13:43:13
acc
在foldr
的情況下沒有真正積累任何東西,正如已經指出的那樣。
我想補充說,沒有它,目前還不清楚當輸入是一個空列表時應該發生什麼。
它也改變了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)
你描述的是'foldr1',它確實在空列表上出現錯誤。 – 2014-11-23 15:56:34
積累與foldl從foldr相似左側和積累情況從右側發生。 – 2014-11-22 04:44:34
是的,這很有趣。將'f'的第二個參數稱爲累加器可能更合適。我通常使用'z'(connoting zero)或'nil'(包含它所對應的構造函數)編寫foldr-esque模式。 – luqui 2014-11-22 04:46:23