Haskell/列表 III
與 map 類似，摺疊 也是一個高階函式，它接受一個函式和一個列表。但是，摺疊不是逐個元素地應用函式，而是使用它將列表元素組合成一個結果值。
讓我們看幾個具體的例子。sum 可以實現為
示例：sum
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs
而 product 可以實現為
示例：product
product :: [Integer] -> Integer
product [] = 1
product (x:xs) = x * product xs
concat，它接受一個列表列表並將它們連線（串聯）成一個列表
示例：concat
concat :: [[a]] -> [a]
concat [] = []
concat (x:xs) = x ++ concat xs
所有這些示例都展示了遞迴模式，稱為摺疊。可以將名稱視為將列表“摺疊”成單個值，或將函式“摺疊在”列表的元素之間。
Prelude 定義了四個 fold 函式：foldr、foldl、foldr1 和 foldl1。
右結合 的 foldr 從右到左摺疊一個列表。在進行過程中，foldr 使用給定的函式將每個元素與稱為累加器 的執行值組合起來。呼叫 foldr 時，累加器的初始值作為引數設定。
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)
foldr 的第一個引數是一個帶兩個引數的函式。第二個引數是累加器的值（通常從一箇中性的“零”值開始）。第三個引數是要摺疊的列表。
在 sum 中，f 是 (+)，而 acc 是 0。在 concat 中，f 是 (++)，而 acc 是 []。在許多情況下（就像我們迄今為止的所有示例一樣），傳遞給摺疊的函式將是一個接受相同型別兩個引數的函式，但這並非總是如此（正如我們可以從型別簽名中的 (a -> b -> b) 部分看到的那樣——如果型別必須相同，那麼型別簽名中的前兩個字母將匹配）。
請記住，在 Haskell 中寫成 [a, b, c] 的列表是 a : b : c : [] 的替代（語法糖）風格。
現在，foldr f acc xs 在 foldr 定義中只是用函式 f 替換 xs 列表中的每個 cons (:)，同時用 acc 替換結尾處的空列表
foldr f acc (a:b:c:[]) = f a (f b (f c acc))
注意括號如何巢狀在列表的右端。
一個優雅的視覺化方法是將列表資料結構想象成一棵樹
: f
/ \ / \
a : foldr f acc a f
/ \ -------------> / \
b : b f
/ \ / \
c [] c acc
我們可以看到 foldr (:) [] 將完全不改變地返回列表。這種沒有效果的函式稱為恆等函式。您應該開始養成在不同情況下尋找恆等函式的習慣，我們將在學習么半群 時更詳細地討論它們。
左結合 的 foldl 從左側第一個元素開始，以相反的方向處理列表。
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs
因此，結果表示式中的括號在列表的左側累積
foldl f acc (a:b:c:[]) = f (f (f acc a) b) c
相應的樹看起來像
: f
/ \ / \
a : foldl f acc f c
/ \ -------------> / \
b : f b
/ \ / \
c [] acc a
由於所有摺疊都包含左側和右側元素，因此初學者可能會被名稱搞糊塗。您可以將 foldr 視為 fold-right-to-left 的縮寫，將 foldl 視為 fold-left-to-right 的縮寫。名稱指的是摺疊的起點。
注意
技術說明：foldl 是尾遞迴 的，也就是說，它立即遞迴，呼叫自身。出於這個原因，編譯器將對其進行最佳化以提高效率，將其轉換為簡單的迴圈。但是，Haskell 是一種惰性語言，因此對f 的呼叫預設情況下將保持未評估狀態，從而在記憶體中構建一個包含列表整個長度的未評估表示式。為了避免記憶體溢位，我們有一個稱為 foldl' 的 foldl 版本，它是嚴格 的——它會在每一步立即強制評估f。
函式名稱末尾的撇號發音為“tick”，如“fold-L-tick”或“prime”，如“fold-L-prime”。撇號是 Haskell 識別符號中有效的字元。foldl' 可以從 Data.List 庫模組中找到（透過在原始檔的開頭新增 import Data.List 來匯入）。根據經驗，您應該在可能無限的列表上或摺疊正在構建資料結構的情況下使用 foldr，如果列表已知是有限的並且歸結為單個值，則使用 foldl'。幾乎沒有理由使用 foldl（沒有撇號），雖然如果饋送給它的列表不太長，它可能可以使用。
您可能會注意到，在某些情況下，foldl 和 foldr 似乎不是 反義詞。讓我們檢查一下其中一個情況，涉及減法作為組合運算。對於以下每個等式，我們將得到 True 還是 False？
foldl (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
foldr (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
將 foldr 視為從右到左進行，可能會讓我們假設第二個等式將為真，因為最右側的元素在最左側的元素之前出現。然而，事實並非如此
GHCi> foldl (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
True
GHCi> foldr (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
False
發生這種情況是因為 foldr 和 foldl 之間的差異在於結果表示式的關聯方式，而不是列表元素的從左到右順序。以下是上述表示式的展開，帶有顯式括號
foldl (-) 6 [3, 2, 1] == ((6 - 3) - 2) - 1 -- True
foldr (-) 6 [1, 2, 3] == 1 - (2 - (3 - 6)) -- True
還要注意初始累加器（在本例中為 6）始終位於最裡面的括號中。
為了對比，這裡是一個模擬的命令式風格，它確實改變了列表中元素的順序：[1]
GHCi> import Data.List -- So that we can give foldl' a try
GHCi> reduce f acc list = foldl' f acc list -- This is the same as plain old foldl'
GHCi> reduceRight f acc list = foldl' f acc (reverse list) -- keep foldl', but reverse list
現在我們從最初的示例中得到了兩個 True，因為兩者都是從左側摺疊的
GHCi> reduce (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
True
GHCi> reduceRight (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
True
如前所述，foldr 的型別宣告使列表元素和結果可能具有不同的型別。例如，“read” 是一個接受字串並將其轉換為某種型別的函式（型別系統足夠智慧，可以弄清楚是哪種型別）。在本例中，我們將其轉換為浮點數。
示例：列表元素和結果可以具有不同的型別
addStr :: String -> Float -> Float
addStr str x = read str + x
sumStr :: [String] -> Float
sumStr = foldr addStr 0.0
還有一個稱為 foldr1（“fold - R - one”）的變體，它透過採用列表的最後一個元素來放棄顯式的“零”累加器
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
foldr1 _ [] = error "Prelude.foldr1: empty list"
以及 foldl1
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f [x] = x
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = error "Prelude.foldl1: empty list"
注意：就像 foldl 一樣，Data.List 庫中包含 foldl1'，它是 foldl1 的嚴格版本。
使用 foldl1 和 foldr1，所有型別都必須相同，而空列表是錯誤。當沒有明顯的初始累加器值候選並且我們確定列表不會為空時，這些變體很有用。如有疑問，請堅持使用 foldr 或 foldl'。
右結合摺疊在 Haskell 中比左結合摺疊更自然的一個原因是，右摺疊可以對無限列表進行操作。返回無限列表的摺疊在更大的上下文中完全可用，而更大的上下文不需要訪問整個無限結果。在這種情況下，foldr 可以根據需要進行移動，編譯器會知道何時停止。但是，左摺疊必須遞迴呼叫自身，直到它到達輸入列表的末尾（因為遞迴呼叫不是在 f 的引數中進行的）。不用說，如果輸入列表對 foldl 是無限的，則永遠不會到達末尾。
作為一個玩具示例，考慮一個函式 echoes，它接受一個整數列表並生成一個列表，使得在輸入列表中出現數字 n 的地方，它在輸出列表中被複制 n 次。為了建立 echoes 函式，我們將使用 prelude 函式 replicate，其中 replicate n x 是一個長度為 n 的列表，其中 x 是每個元素的值。
我們可以相當方便地將 echoes 寫成一個 foldr
echoes :: [Int] -> [Int]
echoes = foldr (\ x xs -> (replicate x x) ++ xs) []
GHCi> take 10 (echoes [1..])
[1,2,2,3,3,3,4,4,4,4]
(注意：由於\ x xs ->語法，此定義很簡潔。\，看起來像一個lambda（λ），在不使用函式的任何其他地方時，作為一個未命名函式。因此，我們就地提供了我們的一次性函式的定義。在本例中，x和xs是引數，定義的右側是->之後的內容。)
我們也可以使用foldl
echoes :: [Int] -> [Int]
echoes = foldl (\ xs x -> xs ++ (replicate x x)) []
GHCi> take 10 (echoes [1..]) -- not terminating
但只有foldr版本適用於無限列表。如果你只是計算echoes [1..]會發生什麼？試試看！(如果你在GHCi或終端中嘗試過，請記住你可以使用Ctrl-c停止計算，但你必須動作快並留意系統監控器，否則你的記憶體很快就會被消耗掉，你的系統就會卡住。)
作為最後一個例子，map本身可以用fold實現
map :: (a -> b) -> [a] -> [b]
map f = foldr (\ x xs -> f x : xs) []
摺疊需要一些時間才能習慣，但它是函數語言程式設計中的一個基本模式，最終會變得非常自然。任何時候你想要遍歷一個列表並從它的成員中構建一個結果，你可能想要一個摺疊。
| 練習 |
|---|
|
“掃描”就像map和fold的混合。摺疊一個列表累積一個單獨的返回值，而對映將每個專案透過一個函式，為每個專案返回一個單獨的結果。掃描同時執行這兩項操作：它像fold一樣累積一個值，但它不是隻返回一個最終值，而是返回所有中間值的列表。
Prelude包含四個掃描函式
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl從左側累積列表，第二個引數成為結果列表中的第一個專案。因此，scanl (+) 0 [1,2,3] = [0,1,3,6].
scanl1 :: (a -> a -> a) -> [a] -> [a]
scanl1使用列表的第一個專案作為零引數。如果你希望輸入項和輸出項型別相同，你會經常使用它。請注意scanl和scanl1的型別簽名之間的區別。scanl1 (+) [1,2,3] = [1,3,6].
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr (+) 0 [1,2,3] = [6,5,3,0]
scanr1 :: (a -> a -> a) -> [a] -> [a]
scanr1 (+) [1,2,3] = [6,5,3]
這兩個函式是scanl和scanl1的對應函式，它們從右側累積總數。
| 練習 |
|---|
|
對列表執行的常見操作是過濾——生成一個新列表，該列表僅包含滿足特定條件的第一個列表中的元素。一個簡單的例子：從整數列表中生成僅包含偶數的列表。
retainEven :: [Int] -> [Int]
retainEven [] = []
retainEven (n:ns) =
-- mod n 2 computes the remainder for the integer division of n by 2.
if (mod n 2) == 0
then n : (retainEven ns)
else retainEven ns
此定義有點冗長且特定。Prelude提供了一個簡潔通用的filter函式，型別簽名如下
filter :: (a -> Bool) -> [a] -> [a]
因此，(a -> Bool)函式測試元素以滿足某個條件，然後我們將要過濾的列表輸入，並返回過濾後的列表。
要使用filter編寫retainEven，我們需要將條件宣告為輔助(a -> Bool)函式，如下所示
isEven :: Int -> Bool
isEven n = (mod n 2) == 0
然後retainEven就簡單地變成
retainEven ns = filter isEven ns
我們使用ns而不是xs來表明我們知道這些是數字，而不僅僅是任何東西，但我們可以忽略這一點，並使用更簡潔的無點定義
retainEven = filter isEven
這類似於我們之前對map和fold所做的演示。與filter一樣，它們接受另一個函式作為引數；使用它們無點強調了這種“函式的函式”的方面。
列表推導是某些常見列表操作（例如過濾）的語法糖。例如，我們可以這樣編寫retainEven，而不是使用Prelude filter
retainEven es = [n | n <- es, isEven n]
這種簡潔的語法可能看起來令人生畏，但它很容易分解。一種解釋是
- (從中間開始) 取列表es，並繪製（“<-”）它的每個元素作為值n。
- (在逗號之後) 對於每個繪製的n，測試布林條件
isEven n。 - (在豎線之前) 如果（且僅當）布林條件滿足，將n附加到正在建立的新列表中（注意整個表示式周圍的方括號）。
因此，如果es是[1,2,3,4]，那麼我們將得到列表[2,4]。1和3沒有被繪製，因為(isEven n) == False 。
列表推導的強大之處在於它易於擴充套件。首先，我們可以根據需要使用任意數量的測試（即使是零！）。多個條件被寫成逗號分隔的表示式列表（當然，這些表示式應該計算為布林值）。舉個簡單的例子，假設我們想修改retainEven，只保留大於100的數字
retainLargeEvens :: [Int] -> [Int]
retainLargeEvens es = [n | n <- es, isEven n, n > 100]
此外，我們不侷限於使用n作為生成新列表時要附加的元素。相反，我們可以在豎線之前放置任何表示式（當然，它必須與列表的型別相容）。例如，如果我們想要從每個偶數中減去一，只需要
evensMinusOne es = [n - 1 | n <- es, isEven n]
實際上，這意味著列表推導語法包含了map和filter的功能。
為了使事情更簡單，列表推導中的左箭頭符號可以與模式匹配結合使用。例如，假設我們有一個(Int, Int)元組的列表，並且我們想構造一個列表，其中包含每個元組中第二個元素為偶數的第一個元素。使用列表推導，我們可以這樣寫
firstForEvenSeconds :: [(Int, Int)] -> [Int]
firstForEvenSeconds ps = [fst p | p <- ps, isEven (snd p)] -- here, p is for pairs.
模式可以使其更具可讀性
firstForEvenSeconds ps = [x | (x, y) <- ps, isEven y]
與其他情況一樣，可以在|之前使用任意表達式。如果我們想要一個包含這些第一個元素的兩倍的列表
doubleOfFirstForEvenSeconds :: [(Int, Int)] -> [Int]
doubleOfFirstForEvenSeconds ps = [2 * x | (x, y) <- ps, isEven y]
不計算空格，該函式程式碼比它的描述性名稱更短！
還有更多可能的技巧
allPairs :: [(Int, Int)]
allPairs = [(x, y) | x <- [1..4], y <- [5..8]]
此推導來自兩個列表，並生成所有可能的(x, y)對，其中第一個元素從[1..4]中繪製，第二個元素從[5..8]中繪製。在最終的對列表中，第一個元素將是使用第一個列表的第一個元素（這裡為1）生成的元素，然後是使用第一個列表的第二個元素生成的元素，等等。在這個例子中，完整列表是（為了清晰起見添加了換行符）
Prelude> [(x, y) | x <- [1..4], y <- [5..8]] [(1,5),(1,6),(1,7),(1,8), (2,5),(2,6),(2,7),(2,8), (3,5),(3,6),(3,7),(3,8), (4,5),(4,6),(4,7),(4,8)]
我們可以輕鬆新增一個條件來限制進入最終列表的組合
somePairs = [(x, y) | x <- [1..4], y <- [5..8], x + y > 8]
此列表只包含元素總和大於8的對；從(1,8)開始，然後是(2,7)，依此類推。
| 練習 |
|---|
|
筆記
- ↑
reduce和reduceRight函式取自JavaScript，它們以這種方式執行。