Haskell/列表 II
之前我們瞭解到 Haskell 使用 cons 運算子 (:) 和空列表 [] 來構建列表。我們看到了如何使用遞迴和模式匹配來逐個處理列表。在本章和下一章中，我們將深入探討列表處理的更深入技術，並發現一些新的符號。我們將初次接觸 Haskell 的一些特性，如無限列表、列表推導式和高階函式。
注意
在本章中，您將閱讀和編寫函式，這些函式會對列表中的元素進行求和、減法和乘法運算。為簡單起見，我們將假設列表元素的型別為 Integer。但是，正如您從關於 型別基礎 II 的討論中所記得的那樣，Num 型別類中存在許多不同的型別。作為一種練習，您可以計算出如果我們使這些函式多型，允許列表元素具有 Num 類中的任何型別，那麼這些函式的型別簽名將是什麼。要檢查您的簽名，只需暫時省略它們，將函式載入到 GHCi 中，使用 :t 並讓型別推斷來指導您。
這是一個將整數列表中每個元素加倍的函式
doubleList :: [Integer] -> [Integer]
doubleList [] = []
doubleList (n:ns) = (2 * n) : doubleList ns
在這裡，基本情況為空列表，它計算為空列表。在遞迴情況下，doubleList 構建一個新的列表，使用 (:)。這個新列表的第一個元素是引數頭部元素的兩倍，我們透過遞迴呼叫 doubleList 對引數尾部進行操作來獲得其餘結果。當尾部變為空列表時，將呼叫基本情況，遞迴將停止。[1]
讓我們研究一個示例表示式的求值過程
doubleList [1,2,3,4]
我們可以透過將引數代入函式定義來手動進行計算，就像教科書中的代數一樣
doubleList 1:[2,3,4] = (1*2) : doubleList (2 : [3,4])
= (1*2) : (2*2) : doubleList (3 : [4])
= (1*2) : (2*2) : (3*2) : doubleList (4 : [])
= (1*2) : (2*2) : (3*2) : (4*2) : doubleList []
= (1*2) : (2*2) : (3*2) : (4*2) : []
= 2 : 4 : 6 : 8 : []
= [2, 4, 6, 8]
因此，我們重建了原始列表，將每個元素替換為其兩倍。
在這個手動求值練習中，我們選擇何時計算乘法的 時機 不會影響結果。我們也可以在每次遞迴呼叫 doubleList 之後立即計算倍數。[2]
Haskell 在一些重要方面利用了這種對求值順序的靈活性。作為一種 純 函數語言程式設計語言，編譯器會做出大部分關於何時實際計算內容的決定。作為一種 惰性 語言，Haskell 通常會延遲求值，直到需要最終值（有時可能永遠不會出現）。[3] 從程式設計師的角度來看，求值順序很少重要。[4]
要將列表中每個元素乘以 3，我們可以使用與 doubleList 相同的策略
tripleList :: [Integer] -> [Integer]
tripleList [] = []
tripleList (n:ns) = (3 * n) : tripleList ns
但我們不想為每個不同的乘數編寫一個新的列表乘法函式（例如，將列表中的元素乘以 4、8、17 等）。因此，讓我們建立一個通用函式，允許使用 任何 數字進行乘法。我們的新函式將接受兩個引數：被乘數以及要乘以的 Integer 列表
multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList _ [] = []
multiplyList m (n:ns) = (m * n) : multiplyList m ns
此示例使用 _ 作為“無關緊要”的模式。被乘數在基本情況下未使用，因此我們忽略該引數，而不是給它一個名稱（如 m、n 或 ns）。
我們可以測試 multiplyList，以確保它按預期工作
Prelude> multiplyList 17 [1,2,3,4] [17,34,51,68]
| 練習 |
|---|
|
編寫以下函式並測試它們。不要忘記型別簽名。
take、drop 和 sum。 |
在本章中，我們從一個受限於將元素乘以 2 的函式開始。然後，我們認識到，我們可以透過建立 multiplyList 來避免為每個乘數硬編碼一個新函式，這樣就可以輕鬆地使用任何 Integer。現在，如果我們想要使用其他運算子（如加法）或計算每個元素的平方，該怎麼辦？
我們可以使用 Haskell 的關鍵功能進一步泛化。但是，由於解決方案可能令人意外，我們將以一種迂迴的方式來解決這個問題。考慮 multiplyList 的型別簽名
multiplyList :: Integer -> [Integer] -> [Integer]
首先要了解的是，型別簽名中的 -> 箭頭是 右結合 的。這意味著我們可以將此簽名理解為
multiplyList :: Integer -> ([Integer] -> [Integer])
我們應該如何理解它？它告訴我們 multiplyList 是一個函式，它接受一個 Integer 引數並計算出另一個函式。因此，返回的函式接受一個 Integer 列表並返回另一個 Integer 列表。
考慮我們以前使用 multiplyList 重新定義的 doubleList 函式
doubleList :: [Integer] -> [Integer]
doubleList xs = multiplyList 2 xs
以這種方式編寫，我們可以清楚地消去 `xs`
doubleList = multiplyList 2
這種定義風格（沒有引數變數）被稱為 無點 風格。我們的定義現在表明，對 multiplyList 應用一個引數不會導致求值失敗，而是會得到一個更具體的函式，其型別為 [Integer] -> [Integer]，而不是以最終的 [Integer] 值結束。
我們現在看到，Haskell 中的函式的行為與任何其他值非常相似。函式可以返回其他函式，函式可以作為物件獨立存在，而無需提及它們的論據。函式似乎幾乎與普通常量一樣。我們甚至可以將函式本身用作 引數 嗎？可以，這就是泛化 multiplyList 的下一步的關鍵。我們需要一個函式，它接受任何其他合適的函式並將給定的函式應用於列表中的元素
applyToIntegers :: (Integer -> Integer) -> [Integer] -> [Integer]
applyToIntegers _ [] = []
applyToIntegers f (n:ns) = (f n) : applyToIntegers f ns
使用 applyToIntegers，我們可以接受 任何 Integer -> Integer 函式並將其應用於 Integer 列表中的元素。因此，我們可以使用此通用函式重新定義 multiplyList
multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList m = applyToIntegers ((*) m)
這將使用 (*) 函式，並使用單個初始引數建立一個新的函式，該函式準備接受另一個引數（在本用例中，將來自給定列表中的數字）。
如果所有這些抽象概念讓您感到困惑，請考慮一個具體的例子：當我們在 Haskell 中進行 5 * 7 的乘法時，(*) 函式不會同時接受兩個引數，而實際上它會首先接受 5 並返回一個新的 5* 函式；然後，該函式 再 接受第二個引數，並將其乘以 5。因此，在我們的示例中，我們將 7 作為 5* 函式的引數，然後 該函式 返回最終的計算結果（35）。
因此，Haskell 中的所有函式實際上只接受一個引數。但是，當我們知道為了得到最終結果將生成多少箇中間函式時，我們可以將函式 視為 接受多個引數。我們通常所說的函式接受的引數個數實際上是在第一個引數和最終的非函式結果值之間生成的單引數函式的個數。
在將引數輸入複雜函式時建立中間函式的過程稱為 柯里化（以 Haskell Curry 的名字命名，也是 Haskell 程式語言的同名人物）。
雖然 applyToIntegers 的型別為 (Integer -> Integer) -> [Integer] -> [Integer]，但定義本身不包含任何特定於整數的內容。要使用相同邏輯處理其他型別的列表，我們可以定義諸如 applyToChars、applyToStrings 等版本。它們將具有相同的定義，但型別簽名不同。我們可以使用泛化的最後一步來避免所有這些冗餘：建立一個完全多型的版本，其簽名為 (a -> b) -> [a] -> [b]。Prelude 已經有了這個函式，它被稱為 map
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
使用 map，我們可以輕鬆地實現各種不同的函式，例如...
multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList m = map ((*) m)
...以及...
heads :: [[a]] -> [a]
heads = map head
Prelude> heads [[1,2,3,4],[4,3,2,1],[5,10,15]] [1,4,5]
map 是將函式應用於列表中每個元素的通用解決方案。我們最初的 doubleList 問題只是 map 的一個特例。像 map 這樣的接受其他函式作為引數的函式稱為 *高階函式*。在下一章中，我們將學習更多關於列表處理的高階函式。
| 練習 |
|---|
|
提示和技巧
[edit | edit source]關於 Haskell 中列表的一些雜項說明
點點表示法
[edit | edit source]Haskell 有一種方便的簡寫方式來編寫等間距整數的有序列表。以下是一些示例來說明它
Code Result
---- ------
[1..10] [1,2,3,4,5,6,7,8,9,10]
[2,4..10] [2,4,6,8,10]
[5,4..1] [5,4,3,2,1]
[1,3..10] [1,3,5,7,9]
相同的表示法適用於字元，甚至適用於浮點數。不幸的是，由於舍入誤差，浮點數存在問題。試試這個
[0,0.1 .. 1]
無限列表
[edit | edit source]由於惰性求值，Haskell 列表可以是 *無限* 的。例如，以下程式碼生成從 1 開始的無限整數列表
[1..]
(如果你在 GHCi 中嘗試這個，請記住你可以在 Ctrl-c 中停止求值)。
相同的效果可以透過遞迴函式來實現
intsFrom n = n : intsFrom (n + 1) -- note there is no base case!
positiveInts = intsFrom 1
無限列表在實踐中很有用，因為 Haskell 的惰性求值在任何給定時刻實際上只求值它需要的部分。在大多數情況下，我們可以將無限列表視為普通的列表。程式只有在求值需要列表中的所有值時才會進入無限迴圈。因此，我們無法對無限列表進行排序或列印，但是
evens = doubleList [1..]
將定義 "evens" 為無限列表 [2,4,6,8..]，然後我們可以將 "evens" 傳遞給其他函式，這些函式只需要求值列表的一部分即可獲得其 *最終* 結果。Haskell 會知道只使用最終需要的無限列表的部分。
與硬編碼一個長的有限列表相比，定義一個無限列表，然後取前幾個專案通常更方便。無限列表也可以成為互動式程式頂層傳統無限迴圈的便捷替代方案。
關於 head 和 tail 的說明
[edit | edit source]在使用 ( : ) 模式或 head/tail 來拆分列表時，模式匹配幾乎總是更可取的。使用 head 和 tail 可能很誘人，因為它們簡單且簡潔，但很容易忘記它們在空列表上會失敗（執行時崩潰永遠不好）。我們確實有一個 Prelude 函式，null :: [a] -> Bool，它對空列表返回 True，對其他列表返回 False，因此這提供了一種安全的方式來檢查空列表，而無需模式匹配；但匹配空列表往往比使用 null 的對應 if-then-else 表示式更乾淨、更清晰。
| 練習 |
|---|
|