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) []
摺疊需要一段時間才能習慣，但它是函數語言程式設計中的一個基本模式，最終會變得非常自然。任何時候你想要遍歷一個列表並從它的成員中累積一個結果，你可能都需要一個 fold。
| 練習 |
|---|
|
掃描
[edit | edit source]“掃描”就像 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 的對應函式，它們從右側累積總計。
| 練習 |
|---|
|
過濾
[edit | edit source]對列表執行的常見操作是 過濾 - 生成一個新列表，其中只包含滿足特定條件的第一個列表中的元素。一個簡單的例子：從整數列表中生成一個僅包含偶數的列表。
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 一樣，它們接受另一個函式作為引數；使用它們進行無點操作突出了這種 “函式的函式” 方面。
列表推導
[edit | edit source]列表推導是某些常見列表操作的語法糖，例如過濾。例如，我們可以像這樣寫 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 作為生成新列表時要附加的元素。相反，我們可以在豎線之前放置任何表示式 (當然，如果它與列表的型別相容)。例如，如果我們想要從每個偶數中減去 1，只需要
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，它們以這種方式工作。