Haskell/列表和元組

Haskell 使用兩種基本結構來管理多個值：列表和元組。它們都透過將多個值組合成一個單一組合值來工作。

列表

讓我們在 GHCi 中構建一些列表

Prelude> let numbers = [1,2,3,4]
Prelude> let truths  = [True, False, False]
Prelude> let strings = ["here", "are", "some", "strings"]

方括號界定列表，各個元素用逗號分隔。唯一的限制是，列表中的所有元素必須是相同型別。嘗試定義具有混合型別元素的列表會導致典型的型別錯誤

Prelude> let mixed = [True, "bonjour"]

<interactive>:1:19:
    Couldn't match `Bool' against `[Char]'
      Expected type: Bool
      Inferred type: [Char]
    In the list element: "bonjour"
    In the definition of `mixed': mixed = [True, "bonjour"]

構建列表

除了使用方括號和逗號一次性指定整個列表之外，還可以使用 (:) 運算子（發音為“cons”）逐個構建列表。這種構建列表的過程通常被稱為consing。這個術語來自 LISP 程式設計師，他們發明了動詞“cons”（“constructor”的助記符）來指代這種將元素追加到列表的特定任務。

示例： 將某些內容新增到列表中

Prelude> let numbers = [1,2,3,4]
Prelude> numbers
[1,2,3,4]
Prelude> 0:numbers
[0,1,2,3,4]

當您將某些內容新增到列表中 (something:someList) 時，您將獲得另一個列表。因此，您可以根據需要繼續 consing。請注意，cons 運算子從右到左計算。另一種（更一般的）理解方式是，它將左邊的第一個值和右邊的整個表示式取進來。

示例： 將許多內容新增到列表中

Prelude> 1:0:numbers
[1,0,1,2,3,4]
Prelude> 2:1:0:numbers
[2,1,0,1,2,3,4]
Prelude> 5:4:3:2:1:0:numbers
[5,4,3,2,1,0,1,2,3,4]

實際上，Haskell 透過將所有元素新增到空列表 [] 中來構建所有列表。逗號和括號符號只是語法糖。因此，[1,2,3,4,5] 等效於 1:2:3:4:5:[]

但是，您需要注意列表構造中可能出現的一個潛在陷阱。雖然 True:False:[] 是完全合法的 Haskell，但 True:False不是

示例： 哎呦！

Prelude> True:False

<interactive>:1:5:
    Couldn't match `[Bool]' against `Bool'
      Expected type: [Bool]
      Inferred type: Bool
    In the second argument of `(:)', namely `False'
    In the definition of `it': it = True : False

True:False 產生了一個看起來很熟悉的型別錯誤訊息。它告訴我們 cons 運算子 (:)（實際上只是一個函式）期望列表作為它的第二個引數，但我們給它傳遞了另一個 Bool。(:) 只知道如何將東西新增到列表中。

因此，在使用 cons 時，請記住

• 列表的元素必須具有相同的型別。
• 您只能將某些內容新增到列表中 ((:))，而不能反過來（您不能將列表新增到元素中）。因此，最右邊的專案必須是一個列表，而左邊的專案必須是獨立的元素，而不是列表。

練習
以下 Haskell 程式碼段是否有效：3:[True,False]？為什麼或者為什麼不？ 編寫一個函式 cons8，它接受一個列表作為引數，並將 8（在開頭）新增到該列表中。透過以下方式在以下列表上對其進行測試 cons8 [] cons8 [1,2,3] cons8 [True,False] let foo = cons8 [1,2,3] cons8 foo 以將 8 放在列表末尾的方式修改上述函式。（提示：回顧上一章中的連線運算子 ++。） 編寫一個函式，它接受兩個引數（一個列表和一個事物），並將事物新增到列表中。您可以從以下內容開始 let myCons list thing =

字串只是列表

正如我們在“型別基礎”模組中簡要提到的那樣，Haskell 中的字串只是字元列表。這意味著型別為 String 的值可以像任何其他列表一樣被操作。例如，可以使用 (:) 連線字元並以空列表結尾，或者使用逗號和括號表示法，而不是直接將字串輸入為用雙引號括起來的字元序列，而是可以透過一系列 Char 值來構造它們。

Prelude> "hey" == ['h','e','y']
True
Prelude> "hey" == 'h':'e':'y':[]
True

使用雙引號字串只是更具語法的糖。

列表的列表

列表可以包含任何東西——只要它們都是相同的型別。因為列表也是事物，所以列表可以包含其他列表！在直譯器中嘗試以下操作

示例： 列表可以包含列表

Prelude> let listOfLists = [[1,2],[3,4],[5,6]]
Prelude> listOfLists
[[1,2],[3,4],[5,6]]

列表的列表有時很棘手，因為事物的列表與事物本身的型別不同。型別 Int 與 [Int] 不同。讓我們透過一些練習來理清這些含義

練習
以下哪些是有效的 Haskell，哪些不是？用 cons 表示法重寫。 [1,2,3,[]] [1,[2,3],4] [[1,2,3],[]] 以下哪些是有效的 Haskell，哪些不是？用逗號和括號表示法重寫。 []:[[1,2,3],[4,5,6]] []:[] []:[]:[] [1]:[]:[] ["hi"]:[1]:[] Haskell 可以有列表的列表的列表嗎？為什麼或者為什麼不？ 為什麼以下列表在 Haskell 中無效？ [[1,2],3,[4,5]]

不同型別的元素的列表不能被 cons，但空列表可以被任何型別的列表 cons。例如，[]:[[1, 2], [1, 2, 3]] 是有效的，並將產生 [[], [1, 2], [1, 2, 3]]，而 [1]:[[1, 2], [1, 2, 3]] 是有效的，並將產生 [[1], [1, 2], [1, 2, 3]]，但 ['a']:[[1, 2], [1, 2, 3]] 將產生錯誤訊息。

列表的列表允許我們表達一些複雜的有結構資料（例如二維矩陣）。它們也是 Haskell 型別系統真正閃耀的地方之一。人類程式設計師（包括這本華夏公益教科書的合著者）在處理列表的列表時總是會感到困惑，而對型別的限制通常有助於克服潛在的混亂。

元組

一個不同的“許多”概念

元組提供了一種在單個值中儲存多個值的其他方式。元組和列表有兩個主要區別

• 元組具有固定數量的元素（不可變）；您不能對元組進行 consing。因此，當您事先知道要儲存多少個值時，使用元組是有意義的。例如，我們可能想要一種型別來儲存點的二維座標。我們確切地知道每個點需要多少個值（兩個 - x 和 y 座標），因此元組是適用的。

• 元組的元素不需要是相同的型別。例如，在電話簿應用程式中，我們可能想要透過將三個值壓縮成一個來處理條目：姓名、電話號碼和我們撥打電話的次數。在這種情況下，三個值不會具有相同的型別，因為姓名和電話號碼是字串，但聯絡人計數器將是一個數字，所以列表將不起作用。

元組用括號標記，元素用逗號分隔。讓我們看一些元組示例

示例： 一些元組

(True, 1)
("Hello world", False)
(4, 5, "Six", True, 'b')

第一個示例是一個包含兩個元素的元組：True 和 1。下一個示例又包含兩個元素：“Hello world” 和 False。第三個示例是一個包含五個元素的元組：4（一個數字）、5（另一個數字）、“Six”（一個字串）、True（一個布林值）和 'b'（一個字元）。

關於術語的快速說明：通常，您使用n 元組來表示大小為n 的元組。通常，我們將 2 元組（即包含 2 個元素的元組）稱為對，並將 3 元組稱為三元組。更大尺寸的元組實際上並不常見，但我們可以邏輯地將命名系統擴充套件為四元組、五元組等等。

練習
寫下第一個元素為 4、第二個元素為“hello”、第三個元素為 True 的 3 元組。 以下哪些是有效的元組？ (4, 4) (4, "hello") (True, "Blah", "foo") () 列表可以透過對它們進行 consing 新元素來構建。將數字 cons 到數字列表中，您將獲得一個數字列表。沒有這種構建元組的方式。 您認為這是為什麼？ 為了論證，假設存在這樣的函式。如果您對元組進行“consing”，您將得到什麼？

當您想從函式中返回多個值時，元組非常方便。在許多語言中，一次返回兩個或多個值通常需要將它們包裝在單一用途的資料結構中，也許只在該函式中使用。在 Haskell 中，我們將這些結果作為元組返回。

元組中的元組（和其他組合）

我們可以在關於將列表儲存在列表中的元組上應用相同的推理。元組也是事物，所以你可以在元組中儲存元組（在元組中，直到任意級別的複雜性）。同樣，你也可以擁有元組列表，元組列表，以及各種相關的組合。

示例：巢狀元組和列表

((2,3), True)
((2,3), [2,3])
[(1,2), (3,4), (5,6)]

元組的型別不僅由其大小定義，而且與列表一樣，由它包含的物件的型別定義。例如，元組("Hello",32)和(47,"World")從根本上是不同的。一個是(String,Int)型別，而另一個是(Int,String)型別。這對構建元組列表有影響。我們可以很容易地擁有像[("a",1),("b",9),("c",9)]這樣的列表，但是Haskell不能擁有像[("a",1),(2,"b"),(9,"c")]這樣的列表。

練習
這些中哪些是有效的Haskell，為什麼？ 1:(2,3) (2,4):(2,3) (2,4):[] [(2,4),(5,5),('a','b')] ([2,4],[2,2])

檢索值

為了使列表和元組有用，我們需要訪問它們包含的內部值。

讓我們從表示點(x, y)座標的對（即 2 元組）開始。想象你想要在棋盤上指定一個特定的方格。你可以從 1 到 8 給行和列貼標籤。然後，一對(2, 5)可以表示第 2 行第 5 列的方格。假設我們想要一個函式來查詢給定行中的所有棋子。我們可以從所有棋子的座標開始，然後檢視行部分，看看它是否等於我們要檢查的任何行。給定棋子的座標對(x, y)，我們的函式需要提取x（行座標）。為了達到這種目的，有兩個標準函式，fst和snd，它們分別檢索對中的第一個和第二個元素。讓我們看一些例子

示例：使用fst和snd

Prelude> fst (2, 5)
2
Prelude> fst (True, "boo")
True
Prelude> snd (5, "Hello")
"Hello"

請注意，根據定義，這些函式僅適用於對。

對於列表，函式head和tail大致類似於fst和snd。它們透過拆開(:)連線的部分來拆解列表。head計算列表的第一個元素，而tail給出列表的其餘部分。

示例：使用head和tail

Prelude> 2:[7,5,0]
[2,7,5,0]
Prelude> head [2,7,5,0]
2
Prelude> tail [2,7,5,0]
[7,5,0]

注意

不幸的是，head和tail有一個嚴重的問題。如果我們將它們中的任何一個應用於空列表...

Prelude> head []
*** Exception: Prelude.head: empty list

...它會爆炸，因為空列表沒有第一個元素，也沒有其他任何元素。在GHCi之外，嘗試在空列表上執行head或tail會使程式崩潰。

我們暫時會使用head和tail，但我們希望避免在實際程式碼中出現這種故障的任何風險，因此我們將在後面的章節中學習更好的選擇。有人可能會問“有什麼問題呢？如果我們小心，從不向它們傳遞空列表，或者我們以某種方式在呼叫它們之前測試列表是否為空，那麼使用head和tail就可以正常工作。”但那條路通向瘋狂。

隨著程式變得越來越大、越來越複雜，空列表最終被傳遞給head和tail的地方數量會迅速增加，我們可能會犯錯的地方數量也會隨之增加。作為經驗法則，你應該避免可能在沒有警告的情況下失敗的函式。隨著我們在本書中不斷前進，我們將學習更好的方法來避免這些風險。

待解決問題

這裡介紹的四個函式似乎並沒有完全解決我們開始這部分內容時遇到的問題。雖然fst和snd為對提供了一個令人滿意的解決方案，但對於有三個或更多元素的元組呢？對於列表，我們能做得比僅僅在第一個元素之後分解它們更好嗎？目前，我們必須將這些問題擱置。在我們完成一些必要的準備工作之後，我們將在未來關於列表操作的章節中回到這個主題。現在，請記住，分離列表的頭和尾將允許我們做任何我們想做的事情。

練習
使用fst和snd的組合從元組(("Hello", 4), True)中提取 4。 正常的象棋符號與我們的有點不同：它將行從 1-8 編號，列從 a-h 編號；並且通常首先給出列標籤。我們可以用字元和數字給特定點貼標籤，例如('a', 4)嗎？這說明了與列表有什麼重要的區別？ 編寫一個函式，該函式將列表的頭和尾作為元組的第一個和第二個元素返回。 使用head和tail編寫一個函式，該函式給出列表的第五個元素。然後，對其進行批評，指出你注意到的任何煩人和陷阱。

多型型別

回想一下，列表的型別取決於其元素的型別，並用方括號將其括起來表示

Prelude> :t [True, False]
[True, False] :: [Bool]
Prelude> :t ["hey", "my"]
["hey", "my"] :: [[Char]]

Bool的列表與[Char]的列表（與String的列表相同，因為[Char]和String是同義詞）是不同的型別。由於函式只接受函式型別中指定的型別的引數，這可能會導致一些複雜情況。例如，考慮head的情況。鑑於[Int]、[Bool]和[String]是不同的型別，我們似乎需要為每種情況分別建立函式——headInt :: [Int] -> Int、headBool :: [Bool] -> Bool、headString :: [String] -> String等等… 然而，這不僅非常煩人，而且毫無意義。畢竟，列表的組裝方式與它們包含的值的型別無關，因此我們期望獲取列表第一個元素的過程在所有情況下都保持一致。

幸運的是，我們確實有一個適用於所有列表的單一函式head

Prelude> head [True, False]
True
Prelude> head ["hey", "my"]
"hey"

這怎麼可能呢？像往常一樣，檢查head的型別會提供一個很好的提示

示例：我們的第一個多型型別

Prelude> :t head
head :: [a] -> a

簽名中的a不是型別——記住型別名稱總是以大寫字母開頭。相反，它是一個型別變數。當Haskell看到一個型別變數時，它允許任何型別代替它的位置。在型別論（數學的一個分支）中，這被稱為多型性：只有單一型別的函式或值被稱為單態的，而使用型別變數來承認多種型別的東西則被稱為多型的。例如，head的型別告訴我們它接受一個任意型別（a）的列表（[a]），並返回該相同型別（a）的值。

請注意，在單個型別簽名中，同一個型別變數的所有情況必須是相同型別。例如，

f :: a -> a

表示f接受任何型別的引數，並返回與引數相同型別的結果，而不是

f :: a -> b

表示f接受任何型別的引數，並返回任何型別的結果，該結果可能或可能不與我們為a提供的型別匹配。不同的型別變數沒有指定型別必須不同，它只是說它們可以不同。

示例：fst和snd

正如我們所見，你可以使用fst和snd函式來提取對的一部分。到目前為止，你應該已經養成了習慣，即對於你遇到的每一個函式，都要問“這是什麼型別？”。讓我們考慮fst和snd的情況。這兩個函式以對作為引數，並返回該對的一個元素。與列表一樣，對的型別取決於其元素的型別，因此函式需要是多型的。還要記住，對（以及一般意義上的元組）不需要在內部型別方面是同質的。因此，如果我們要說

fst :: (a, a) -> a

那意味著fst只有在給定作為輸入的對的第一個和第二個部分具有相同型別的情況下才能工作。因此，正確的型別是

示例：fst和snd的型別

fst :: (a, b) -> a
snd :: (a, b) -> b

如果你除了型別簽名之外對fst和snd一無所知，你仍然可能會猜測它們分別返回對的第一個和第二個部分。雖然這是正確的，但其他函式也可能具有相同的型別簽名。所有簽名都表明的是，它們只需要返回與對的第一個和第二個部分相同型別的東西。

練習
為以下函式給出型別簽名 前一部分的第三個練習的解決方案（“...返回列表的頭和尾作為元組的第一個和第二個元素的函式”）。 前一部分的第四個練習的解決方案（“...給出列表的第五個元素的函式”）。 h x y z = chr (x - 2)（記住我們在上一章中討論了 chr）。

總結

本章介紹了列表和元組。它們之間的關鍵相似之處和區別在於

1. 列表由方括號和逗號定義：[1,2,3]。
   • 只要列表的所有元素都是相同型別，列表就可以包含任何東西。
   • 列表也可以透過 cons 運算子(:)構建，但你只能將東西 cons 到列表上。
2. 元組由圓括號和逗號定義：("Bob",32)
   • 元組可以包含任何東西，即使是不同型別的東西。
   • 元組的長度在其型別中編碼；不同長度的元組將具有不同的型別。
3. 列表和元組可以以多種方式組合：列表中包含列表，元組中包含列表，等等，但它們的標準必須仍然滿足才能使組合有效。