foldr和foldl的高階函數特徵

Question

我無法解釋foldl的函數簽名。我瞭解它的工作原理，但我不確定它與簽名之間的關係。

我有關於它的細節了幾個問題

foldr :: (a -> b -> b) -> b -> [a] -> b 

foldr (+) 5 [1,2,3,4] 

這似乎是第一個參數需要一個新增功能：

(a -> b -> b) 

在該函數的參數，究竟是怎麼回事？本節是否將最右邊的整數a應用於累加器b以在此情況下生成另一個整數9？在此之後，它是否會返回一個將累加器作爲參數的函數？

然後，下面的最後兩個參數是什麼意思？

[a] -> b 

非常感謝。

Answer 1

當您將(+)傳入foldr的第一個參數時，您會隱式聲明a與b相同。這得到混亂，因爲我們往往會重複使用的名字，但如果我寫它一起使用的類型變量

(+)  :: Num i => i -> i -> i 
foldr  :: (a -> b -> b) -> b -> [a] -> b 
foldr (+) :: Num i => i -> [i] -> i 

相同的命名空間，其中第三線意味着i ~ a和i ~ b因此，通過傳遞，a ~ b。此外，在這裏可能會更清楚地看到foldr (+)中的第一個剩餘參數是摺疊的「初始」值，而[i]位是我們正在壓縮，摺疊，減少的列表。

通過foldr (+) 0更常見的名稱sum :: Num a => [a] -> a可能更清楚。我們也有foldr (*) 1作爲product :: Num a => a -> [a]。

所以是的，您對foldr (+)中累加器函數的表現的描述完全正確，但比函數更具體。例如，我們可以使用foldr來構建一個Map。

foldr (\(k, v) m -> Map.insert m k v) Map.empty :: Ord k => [(k, v)] -> Map k v 

在這種情況下，蓄壓器功能需要我們的協會名單，並保持插入值到我們的accumulat * ING * Map，它開始是空的。要完全徹底這裏，讓我寫出來的類型一起再次

(\(k, v) -> m -> Map.insert m k v)  :: Ord k => (k, v) -> Map k v -> Map k v 
foldr         :: (a -> b -> b) -> b -> [a] -> b 
foldr (\(k, v) -> m -> Map.insert m k v) :: Ord k => Map k v -> [(k, v)] -> Map k v 

，我們已經被迫a ~ (k, v)和b ~ Map k v。

---

作爲對此事的最終意見，這裏是foldr相似的一些暗示性的變量名

foldr _ b []  = b 
foldr (<>) b (a:as) = a <> foldr f b as 

定義所以你可以看到如何(<>) :: a -> b -> b結合a和b類型。我們可以明確地「運行」這個定義，看看它是如何構建計算的。

foldr (+) 0 [1,2,3] 
1 + (foldr (+) 0 [2,3]) 
1 + (2 + (foldr (+) 0 [3])) 
1 + (2 + (3 + (foldr (+) 0 []))) 
1 + (2 + (3 + 0)) 
1 + (2 + 3) 
1 + 5 
6 

當我們使用非對稱的操作像上面Map例子可能會更加清楚。下面我使用{{ k -> v, k -> v }}來表示Map，因爲它不是直接打印的。

-- inserts a single (k,v) pair into a Map 
ins :: Ord k => (k, v) -> Map k v -> Map k v 
ins (k, v) m = Map.insert m k v 

foldr ins Map.empty [('a', 1), ('b', 2)] 
ins ('a', 1) (foldr ins Map.empty [('b', 2)]) 
ins ('a', 1) (ins ('b', 2) (foldr ins Map.empty [])) 
ins ('a', 1) (ins ('b', 2) Map.empty) 
ins ('a', 1) (ins ('b', 2) {{ }}) 
ins ('a', 1) {{ 'b' -> 2 }} 
{{ 'b' -> 2, 'a' -> 1 }} 

Answer 2

這取決於你如何看待它。第一步產生(+) 1 (foldr (+) 5 [2,3,4])。當您嘗試使用摺疊結果時，這將強制（+）的第二個參數的評估，並且由於（+）是嚴格的，因此會拆散整個列表。最後一步產生(+) 1 ((+) 2 ((+) 3 ((+) 4 5)))。所以，是的，前兩個數字是4和5，但這不是foldr的第一件事情，在這種情況下，您將首先用thunk樹替換列表，然後評估它得到所有的總和數字和5.

在函數不嚴格的情況下，使用thunks替換list是很好的 - 這種方式只能根據需要進行評估，甚至可能是無限列表。在功能嚴格的情況下，考慮用foldl'進行重寫是有意義的。

Answer 3

這裏是foldr相似的類型簽名：

foldr :: (a -> b -> b) -> b -> [a] -> b 

它需要一個函數（稱之爲步驟），其採用的下一個值（一個一個）以及累積值（b ），併產生一個新的累計值（也爲b）

step :: a -> b -> b 

而一個inititial accumulat或值（b）：

initialValue :: b 

和投入摺疊列表（的列表的的）：

inputs :: [a] 

最後你得到的輸出（ b）

output :: b 

所以，你得到一個一般形式：

output = foldr step initialValue inputs