另一個 Haskell 教程/型別基礎

Haskell 使用一個 _靜態型別檢查_ 系統。這意味著每個 Haskell 表示式都被分配一個 _型別_。例如 'a' 的型別是 Char，表示“字元”。然後，如果你有一個函式，它期望一個特定型別的引數，而你給它錯誤的型別，就會在編譯時生成錯誤（也就是說，你無法編譯程式）。這大大減少了可能潛入你程式的錯誤數量。

此外，Haskell 使用一個 _型別推斷_ 系統。這意味著你甚至不需要指定表示式的型別。相比之下，在 C 中，當你定義一個變數時，你需要指定它的型別（例如，int、char 等）。在 Haskell 中，你不需要這樣做——型別將從上下文中推斷出來。

注意

如果你想，你當然可以顯式地指定表示式的型別；這通常有助於除錯。實際上，顯式地指定最外層函式的型別有時被認為是一種好的風格。

Hugs 和 GHCi 都允許你對錶達式應用型別推斷以找到它的型別。這是透過使用 :t 命令完成的。例如，啟動你最喜歡的 shell 並嘗試以下操作

示例

Prelude> :t 'c'
'c' :: Char

這告訴我們表示式 'c' 的型別是 Char（雙冒號 :: 在整個 Haskell 中用於指定型別）。

簡單型別

有許多內建型別，包括 Int（用於整數，包括正數和負數）、Double（用於浮點數）、Char（用於單個字元）、String（用於字串）等等。我們已經看到過一個 Char 型別的表示式；讓我們檢查一個 String 型別的表示式

示例

Prelude> :t "Hello"
"Hello" :: String

你也可以輸入更復雜的表示式，例如，一個相等性測試

示例

Prelude> :t 'a' == 'b'
'a' == 'b' :: Bool

你應該注意，即使這個表示式是假的，它仍然有一個型別，即 Bool 型別。

注意

Bool 是 Boolean（發音為“boo-lee-uhn”）的縮寫，它有兩個可能的值：True 和 False。

你可以透過嘗試讓 shell 為你提供一個型別錯誤表示式的型別來觀察型別檢查和型別推斷的過程。例如，相等運算子要求其兩個引數的型別相同。我們可以透過嘗試將一個字元與一個字串進行比較來看到 Char 和 String 是不同型別

示例

Prelude> :t 'a' == "a"
ERROR - Type error in application
*** Expression     : 'a' == "a"
*** Term           : 'a'
*** Type           : Char
*** Does not match : [Char]

錯誤的第一行（包含“Expression”的行）告訴我們發生型別錯誤的表示式。第二行告訴我們這個表示式中的哪一部分型別錯誤。第三行告訴我們該項的推斷型別，第四行告訴我們需要匹配的內容。在這種情況下，它說型別 Char 與型別 [Char] 不匹配（字元列表——Haskell 中的字串表示為字元列表）。

如前所述，你可以使用::運算子顯式地指定表示式的型別。例如，在前面的示例中，我們可以使用 ("a"::String) 而不是 "a"。在這種情況下，這沒有任何影響，因為 "a" 只有一個可能的解釋。但是，請考慮數字的情況。你可以嘗試

示例

Prelude> :t 5 :: Int
5 :: Int
Prelude> :t 5 :: Double
5 :: Double

在這裡，我們可以看到數字 5 可以例項化為 Int 或 Double。如果我們不指定型別呢？

示例

Prelude> :t 5
5 :: Num a => a

不是你預期的那樣？這意味著，簡而言之，如果某個型別 a 是 Num 類的 _例項_，那麼表示式 5 的型別可以是 a 型別。如果這沒有意義，現在不用擔心。在第 類 節中，我們將詳細討論型別類（這就是它）。然而，閱讀它的方式是說“a 是 Num 的例項意味著 a”。

練習
自己找出，然後驗證以下表達式的型別，如果它們有型別。還要注意表示式是否為型別錯誤 'h':'e':'l':'l':'o':[] [5,'a'] (5,'a') (5::Int) + 10 (5::Int) + (10::Double)

多型型別

Haskell 採用多型型別系統。這本質上意味著你可以擁有 _型別變數_，我們之前已經提到過。例如，請注意，像 tail 這樣的函式並不關心列表中的元素是什麼

示例

Prelude> tail [5,6,7,8,9]
[6,7,8,9]
Prelude> tail "hello"
"ello"
Prelude> tail ["the","man","is","happy"]
["man","is","happy"]

這是可能的，因為 tail 具有多型型別：[$\alpha$] -> [$\alpha$]。這意味著它可以接受 _任何_ 列表作為引數並返回一個相同型別的列表。

相同的分析可以解釋 fst 的型別

示例

Prelude> :t fst
fst :: (a,b) -> a

在這裡，GHCi 明確了型別值的 _泛化_。也就是說，它表示對於所有型別 a 和 b，fst 是從 (a,b) 到 a 的函式。

練習
自己找出，然後驗證以下表達式的型別，如果它們有型別。還要注意表示式是否為型別錯誤 snd head null head . tail head . head

型別類

上一節我們看到了一些與數字5相關的奇怪型別。在我們深入研究型別類主題之前，讓我們先退一步看看其中的動機。

動機

在許多語言（C++、Java 等）中，存在一種過載系統。也就是說，可以編寫一個函式，它可以接受不同型別的引數。例如，最典型的例子是相等性函式。如果我們想要比較兩個整數，我們應該使用整數比較；如果我們想要比較兩個浮點數，我們應該使用浮點數比較；如果我們想要比較兩個字元，我們應該使用字元比較。一般來說，如果我們想要比較兩個具有型別 $\alpha$ 的事物，我們想要使用 $\alpha -compare$ 。我們稱 $\alpha$ 為一個 *型別變數*，因為它是一個值是型別的變數。

注意

一般來說，型別變數將使用希臘字母表的第一部分來編寫： $\alpha ,\beta ,\gamma ,\delta ,...$ 。

不幸的是，這給靜態型別檢查帶來了一些問題，因為型別檢查器不知道某個操作（例如，相等性測試）將為哪些型別定義。這個問題的解決方案和靜態型別語言一樣多（這可能有點誇張，但不是特別誇張）。Haskell 選擇的解決方案是型別類系統。當然，這是否是“正確”的解決方案或“最佳”解決方案取決於您的應用領域。然而，這是我們現有的解決方案，所以你應該學會喜歡它。

相等性測試

回到相等性測試的問題，我們想要實現的是定義一個函式 == （相等性運算子），它接受兩個引數，每個引數都是相同的型別（稱為 $\alpha$ ），並返回一個布林值。但這個函式可能並非為 *所有* 型別定義；只為一些型別定義。因此，我們將這個函式 == 與一個型別類相關聯，我們稱之為Eq。如果一個特定型別 $\alpha$ 屬於某個型別類（也就是說，與該類關聯的所有函式都為 $\alpha$ 實現），我們說 $\alpha$ 是該類的 *例項* 。例如，Int是Eq的例項，因為相等性是在整數上定義的。

Num 類

除了過載像 == 這樣的運算子，Haskell 還過載了數字常量（即，1、2、3 等）。這樣做是為了當你輸入像 5 這樣的數字時，編譯器可以自由地將 5 視為一個整數或浮點數，因為它認為合適。它定義了Num類來包含所有這些數字以及對它們的某些最小操作（例如，加法）。基本數值型別（Int、Double）被定義為Num.

的例項。我們只是簡單地介紹了型別類的強大功能（和複雜性）。在 Classes 部分將對此進行更深入的討論，但在我們到達那裡之前，我們還需要一些背景知識。在我們這樣做之前，我們需要更多地談談函式。

Show 類

Haskell 中另一個標準類是 Show 類。屬於 Show 類的型別具有將該型別的值轉換為字串的函式。這個函式叫做 show 。例如，應用於整數 5 的 show 是字串 "5"；應用於字元 'a' 的 show 是三個字元的字串 "'a'"（第一個和最後一個字元是撇號）。應用於字串的 show 只是在它周圍加上引號。你可以在直譯器中測試它

示例

Prelude> show 5
"5"
Prelude> show 'a'
"'a'"
Prelude> show "Hello World"
"\"Hello World\""

注意

最後一行出現反斜槓的原因是內部引號被“轉義”，這意味著它們是字串的一部分，而不是直譯器列印值的的一部分。實際字串不包含反斜槓。

某些型別不是 Show 的例項；例如函式。如果你試圖顯示一個函式（比如 sqrt ），編譯器或直譯器會給你一些神秘的錯誤資訊，抱怨缺少例項宣告或非法類約束。

函式型別

在 Haskell 中，函式是 *一等值* ，這意味著就像 1 或 'c' 是具有型別的值一樣，square 或 ++ 這樣的函式也是如此。在我們過多地討論函式之前，我們需要做一個簡短的關於非常理論的計算機科學的旁白（別擔心，不會太痛苦），並談談 lambda 演算。

Lambda 演算

雖然“Lambda 演算”這個名字可能聽起來很嚇人，但它實際上描述了一種相當簡單的函式表示系統。在 Lambda 演算中，我們可以這樣寫一個平方函式：$\lambda x.x*x$，這意味著我們取一個值，我們稱之為 $x$（這就是 $\lambda x.$ 的含義），然後將它乘以它自身。 $\lambda$ 被稱為“Lambda 抽象”。一般來說，Lambda 表示式只能有一個引數。如果我們想要編寫一個接受兩個數字的函式，將第一個數字加倍並將其新增到第二個數字，我們可以這樣寫：$\lambda x\lambda y.2*x+y$。當我們將一個值應用到 Lambda 表示式時，我們會移除最外層的 $\lambda$ 並用該值替換 Lambda 變數的所有出現。例如，如果我們評估 $(\lambda x.x*x)5$，我們會移除 Lambda 並用 $5$ 替換 $x$ 的所有出現，得到 $(5*5)$，結果是 $25$。

事實上，Haskell 大部分基於 Lambda 演算的擴充套件，這兩個表示式可以直接在 Haskell 中編寫（我們只需將 $\lambda$ 替換為反斜槓 (\)，將 $.$ 替換為 (->)；此外，我們不需要重複 Lambda；當然，在 Haskell 中，如果我們正在定義函式，就必須為它們命名）。

square = \x -> x*x
f = \x y -> 2*x + y

你也可以在互動式 shell 中評估 Lambda 表示式

示例

Prelude> (\x -> x*x) 5
25
Prelude> (\x y -> 2*x + y) 5 4
14

我們可以從第二個例子中看到，我們需要為 Lambda 抽象提供兩個引數，一個對應於 x，另一個對應於 y。

高階型別

“高階型別”指的是那些元素是函式的型別。賦予函式的型別模仿了 Lambda 演算中函式的表示方法。例如，square 的定義為 $\lambda x.x*x$。要獲得它的型別，我們首先要問自己 x 的型別是什麼。假設我們決定 x 是一個 Int。然後，我們注意到函式 square 接受一個 Int 併產生一個值 x*x。我們知道，當我們將兩個 Int 相乘時，我們會得到另一個 Int，所以 square 結果的型別也是 Int。因此，我們說 square 的型別是 Int -> Int。

我們可以對上面的函式 f (\x y -> 2*x + y) 進行類似的分析。這個函式的值（記住，函式本身就是值）是接受一個值 x 併產生一個新值的函式，這個新函式接受一個值 y 併產生 2*x+y。例如，如果我們取 f 並且只向它應用一個數字，我們得到 $(\lambda x\lambda y.2x+y)5$，它將變為我們的新值 $\lambda y.2(5)+y$，其中 $x$ 的所有出現都被替換為應用的值，$5$。

我們知道 f 接受一個 Int 型別的值，併產生一個型別未知的值。但我們知道該值的型別是 $\lambda y.2(5)+y$ 的型別。我們應用上述分析，發現該表示式具有型別 Int -> Int。因此，f 接受一個 Int 型別的值，併產生一個具有型別 Int -> Int 的值。所以 f 的型別是 Int -> (Int -> Int)。

注意

括號不是必需的；在函式型別中，如果存在 $\alpha \rightarrow \beta \rightarrow \gamma$，則假定 $\beta \rightarrow \gamma$ 是分組的。如果你想要其他方式，使用 $\alpha \rightarrow \beta$ 分組，則需要將它們放在括號中。

這並不完全準確。正如我們之前所見，像 5 這樣的數字並不真正屬於型別 Int，它們屬於型別 Num a => a。

我們可以使用之前使用的 “:t” 輕鬆找出 Prelude 函式的型別。

示例

Prelude> :t head
head :: [a] -> a
Prelude> :t tail
tail :: [a] -> [a]
Prelude> :t null
null :: [a] -> Bool
Prelude> :t fst
fst :: (a,b) -> a
Prelude> :t snd
snd :: (a,b) -> b

我們將其解釋為：“head” 是一個函式，它接受一個包含型別為 “a” 的值的列表，並返回一個型別為 “a” 的值；“tail” 接受一個 “a” 的列表，並返回另一個 “a” 的列表；“null” 接受一個 “a” 的列表，並返回一個布林值；“fst” 接受一個型別為 “(a,b)” 的對，並返回一個型別為 “a” 的值，等等。

注意

說 fst 的型別是 (a,b) -> a 並不一定意味著它只返回第一個元素；它只是意味著它返回一個與第一個元素具有 *相同型別* 的值。

我們還可以獲取像 + 和 * 以及 ++ 和 : 這樣的運算子的型別；但是，要做到這一點，我們需要將它們放在括號中。一般來說，任何以 *中綴* 方式使用的函式（意味著它位於兩個引數的中間而不是它們前面）在獲取其型別時都必須放在括號中。

示例

Prelude> :t (+)
(+) :: Num a => a -> a -> a
Prelude> :t (*)
(*) :: Num a => a -> a -> a
Prelude> :t (++)
(++) :: [a] -> [a] -> [a]
Prelude> :t (:)
(:) :: a -> [a] -> [a]

+ 和 * 的型別相同，這意味著 + 是一個函式，對於某個型別為 a 的值（它是 Num 的例項），它接受一個型別為 a 的值，併產生另一個函式，該函式接受一個型別為 a 的值，併產生一個型別為 a 的值。簡而言之，我們可以說 + 接受兩個型別為 a 的值，併產生一個型別為 a 的值，但這不夠精確。

++ 的型別意味著，簡而言之，對於給定的型別 a，++ 接受兩個 a 的列表，併產生一個新的 a 的列表。類似地，: 接受一個型別為 a 的值和另一個型別為 [a]（a 的列表）的值，併產生另一個型別為 [a] 的值。

那個討厭的 IO 型別

你可能會想嘗試獲取像 putStrLn 這樣的函式的型別。

示例

Prelude> :t putStrLn
putStrLn :: String -> IO ()
Prelude> :t readFile
readFile :: FilePath -> IO String

世界上那個 IO 是什麼？它基本上是 Haskell 用於表示這些函式不是真正函式的方式。它們被稱為“IO 動作”（因此有 IO）。由此產生的直接問題是：好吧，那麼我如何擺脫 IO 呢？好吧，你不能在保持程式碼的純函式功能的同時使用具有諸如 IO String -> String 之類的型別的函式。Haskell 的純函式在應用於相同引數時總是給出相同的結果，就像數學中的情況一樣。另一方面，readFile 會在呼叫時返回檔案內容。假設在正在進行的 Haskell 程序中 x = "TABLE OF CONTENTS"，之後 x = "TABLE OF CONTENTS {新行} "Chapter One"。在使用可變變數的語言中這不會有問題，但在 Haskell 中，一旦將值賦給 x，更改該值可能會導致系統崩潰之前出現奇怪的行為。因此，在你能想到的幾乎所有用例中，使用具有 IO 型別的元素的方法是將它們與程式的純部分隔離，方法是將它們與其他函式結合起來。

例如，如果你使用 readFile 讀取檔案，那麼你可能想要對它返回的字串做些什麼（否則，為什麼要首先讀取檔案呢）。假設你有一個函式 f，它接受一個 String 型別的值併產生一個 Int 型別的值。你不能直接將 f 應用於 readFile 的結果，因為 f 的輸入是 String，而 readFile 的輸出是 IO String，它們不匹配。但是，你可以將它們結合起來，如下所示：

main = do
  s <- readFile "somefile"
  let i = f s
  putStrLn (show i)

在這裡，我們使用箭頭約定來“從 IO 動作中取出字串”，然後將 f 應用於字串（稱為 s）。然後，例如，我們將 i 列印到螢幕上。請注意，let這裡沒有對應的in。這是因為我們處於do塊中。還要注意，我們沒有編寫 i <- f s，因為 f 只是一個普通函式，而不是一個 IO 動作。注意：如果你想簡化 putStrLn (show i)，可以將其簡化為 print i。

顯式型別宣告

有時希望顯式指定某些元素或函式的型別，出於以下一個（或多個）原因

• 清晰度
• 速度
• 除錯

有些人認為，將所有頂級函式的型別都指定出來是良好的軟體工程實踐。如果沒有別的，如果你試圖編譯程式，並且遇到了你不理解的型別錯誤，如果你顯式聲明瞭部分函式的型別，那麼找到錯誤的位置可能會更容易。

型別宣告是與函式定義分開編寫的。例如，我們可以像以下程式碼一樣顯式指定函式 square 的型別（顯式宣告的型別稱為 *型別簽名*）。

square :: Num a => a -> a
square x = x*x

這兩行甚至不必挨在一起。但是，你指定的型別必須與函式定義的推斷型別匹配（或者更具體）。在此定義中，你可以將 square 應用於任何 Num 的例項：Int、Double 等。但是，如果你事先知道 square 將只應用於型別為 Int 的值，則可以將其型別 *細化* 為

square :: Int -> Int
square x = x*x

現在，你只能將 square 應用於型別為 Int 的值。此外，使用此定義，編譯器不必生成原始函式定義中指定的一般程式碼，因為它知道你將只將 square 應用於 Int，因此它可能能夠生成更快的程式碼。

如果你啟用了擴充套件（在 Hugs 中為 “-98”，在 GHC(i) 中為 “-fglasgow-exts”），你也可以為表示式新增型別簽名，而不僅僅是函式。例如，你可以寫

square (x :: Int) = x*x

它告訴編譯器 x 是一個 Int；但是，它讓編譯器自行推斷表示式的剩餘部分的型別。在此示例中，square 的型別是什麼？先猜一下，然後你可以透過將此程式碼輸入到檔案中並將其載入到你的直譯器中，或者透過詢問表示式的型別來驗證你的猜測。

示例

Prelude> :t (\(x :: Int) -> x*x)

因為這個 lambda 表示式等價於上面的函式宣告。

函式引數

在關於 列表 的部分中，我們看到了函式將其他函式作為引數的示例。例如，map 接收一個應用於列表中每個元素的函式，filter 接收一個告訴它保留列表中哪些元素的函式，而 foldl 接收一個告訴它如何將列表元素組合在一起的函式。與 Haskell 中的任何其他函式一樣，這些函式都是型別化的。

首先，讓我們考慮一下 map 函式。它的作用是接受一個元素列表，併產生另一個元素列表。這兩個列表的元素型別不必相同。因此，map 將接受一個型別為 [a] 的值，併產生一個型別為 [b] 的值。它是如何做到的？它使用使用者提供的函式進行轉換。為了將一個 a 轉換為一個 b，這個函式必須具有型別 a -> b。因此，map 的型別是 (a -> b) -> [a] -> [b]，你可以在你的直譯器中使用 “:t” 驗證這一點。

我們可以對 filter 應用相同的分析，並發現它的型別是 (a -> Bool) -> [a] -> [a]。正如我們介紹了 foldr 函式，你可能會傾向於給它型別 (a -> a -> a) -> a -> [a] -> a，這意味著你接受一個將兩個 a 合併成另一個的函式，一個型別為 a 的初始值，一個 a 的列表來產生一個型別為 a 的最終值。事實上，foldr 具有更通用的型別：(a -> b -> b) -> b -> [a] -> b。所以它接受一個將 a 和 b 轉換成 b 的函式，一個型別為 b 的初始值和一個 a 的列表。它產生一個 b。

為了看到這一點，我們可以編寫一個函式 count，它計算列表中滿足給定約束的成員數量。當然，你可以使用 filter 和 length 來做到這一點，但我們也會使用 foldr 來實現。

module Count
    where

import Char

count1 bTest list = length (filter bTest list)
count2 bTest list = foldr (\x cnt -> if bTest x then cnt+1 else cnt) 0 list

count1 的功能很簡單。它根據謂詞 bTest 過濾列表 list，然後獲取結果列表的長度。另一方面，count2 使用初始值（它是一個整數）來儲存當前計數。對於列表 list 中的每個元素，它應用顯示的 lambda 表示式。這將接受兩個引數，cnt 儲存當前計數，x 是我們正在檢視的列表中的當前元素。它檢查 bTest 是否對 x 成立。如果成立，它將返回新值 cnt+1，增加滿足謂詞的元素計數。如果它不成立，它只返回 cnt，舊計數。當 lambda 定義如上所示時，count2 Char.isLower "aBCde" 展開為 lambda 'a' (lambda 'B' (lambda 'C' (lambda 'd' (lambda 'e' 0))))。

練習
自己找出，然後驗證以下表達式的型別，如果它們有型別。還要注意表示式是否為型別錯誤 \x -> [x] \x y z -> (x,y:z:[]) \x -> x + 5 \x -> "hello, world" \x -> x 'a' \x -> x x \x -> x + x

資料型別

元組和列表是定義結構化值的不錯且常用的方法。然而，通常希望能夠定義我們自己的資料結構和它們上面的函式。所謂“資料型別”是使用data關鍵字定義的。

對

例如，一對元素的定義（類似於標準的內建對型別）可以是

data Pair a b = Pair a b

讓我們逐字分析這段程式碼。首先我們說“data”，意思是我們要定義一個數據型別。然後我們給出資料型別的名稱，在本例中是“Pair”。緊隨“Pair”之後的“a”和“b”是唯一的型別引數，就像“a”是函式 map 的型別一樣。所以直到這一點，我們已經說過我們要定義一個名為“Pair”的資料結構，它被引數化到兩種型別上，a 和 b。請注意，你不能有 Pair a a = Pair a a - 在這種情況下，編寫 Pair a = Pair a a。

在等號之後，我們指定了這種資料型別的建構函式。在本例中，有一個建構函式，“Pair”（它不一定與型別具有相同的名稱，但在只有一個建構函式的情況下，它似乎更有意義）。在這一對之後，我們再次編寫“a b”，這意味著為了構造一個 Pair，我們需要兩個值，一個是型別 a，一個是型別 b。

這個定義引入了函式 Pair :: a -> b -> Pair a b，你可以用它來構造 Pair。如果你將這段程式碼輸入到一個檔案中並載入它，你可以看到它們是如何構造的

示例

Datatypes> :t Pair
Pair :: a -> b -> Pair a b
Datatypes> :t Pair 'a'
Pair 'a' :: a -> Pair Char a
Datatypes> :t Pair 'a' "Hello"
Pair 'a' "Hello" :: Pair Char [Char]

因此，透過給 Pair 兩個值，我們已經完全構造了一個型別為 Pair 的值。我們可以編寫涉及對的函式，如下所示

pairFst (Pair x y) = x
pairSnd (Pair x y) = y

在這裡，我們使用了 Haskell 的模式匹配功能來檢視一個對並從中提取值。在 pairFst 的定義中，我們獲取一個完整的 Pair 並提取第一個元素；pairSnd 也是如此。我們將在關於模式匹配的部分中更詳細地討論模式匹配。

練習
編寫一個 Triple 資料型別宣告，它是一個包含三個元素的型別，所有元素的型別都不相同。編寫函式 tripleFst、tripleSnd 和 tripleThr 分別提取第一個、第二個和第三個元素。 編寫一個數據型別 Quadruple，它儲存四個元素。但是，前兩個元素必須是相同的型別，後兩個元素必須是相同的型別。編寫一個函式 firstTwo，它返回一個包含前兩個元素的列表，以及一個函式 lastTwo，它返回一個包含後兩個元素的列表。為這些函式編寫型別簽名。

多個建構函式

我們已經看到了一個具有一個建構函式的資料型別的示例：Pair。擁有多個建構函式也是可能的（而且非常有用）。

讓我們考慮一個簡單的函式，它在列表中搜索滿足給定謂詞的元素，然後返回滿足該謂詞的第一個元素。如果列表中的任何元素都不滿足謂詞，我們該怎麼辦？下面列出了幾個選項

• 引發錯誤
• 無限迴圈
• 編寫一個檢查函式
• 返回第一個元素
• $...$

引發錯誤當然是一個選項（請參閱關於異常的部分，以瞭解如何做到這一點）。問題是很難/不可能從這些錯誤中恢復。無限迴圈是可能的，但不是很實用。我們可以編寫一個姐妹函式，它檢查列表是否包含滿足謂詞的元素，並讓使用者始終先使用這個函式。我們可以返回第一個元素，但這非常臨時且難以記住；如果列表本身為空怎麼辦？

沒有基本的選項來簡單地解決這個問題，這意味著我們必須更多地思考它。我們試圖做什麼？我們試圖編寫一個可能成功也可能不成功的函式。此外，如果成功，它將返回某種值。讓我們編寫一個數據型別

data Maybe a = Nothing
             | Just a

這是 Haskell 中最常見的資料型別之一，並在 Prelude 中定義。

在這裡，我們說，建立型別為 Maybe a 的東西有兩種可能的方式。第一種是使用空元建構函式 Nothing，它不接受任何引數（這就是“空元”的含義）。第二種是使用建構函式 Just，以及一個型別為 a 的值。

Maybe 型別在各種情況下都很有用。例如，假設我們要編寫一個函式（像 head）返回給定列表的第一個元素。但是，我們不希望程式在給定列表為空時崩潰。我們可以用類似這樣的函式來實現這一點

firstElement :: [a] -> Maybe a
firstElement []     = Nothing
firstElement (x:xs) = Just x

這裡的型別簽名表示 firstElement 接受一個 a 的列表，併產生一個型別為 Maybe a 的東西。在程式碼的第一行，我們對空列表 [] 進行了匹配。如果這個匹配成功（即列表實際上是空的），我們就返回 Nothing。如果第一個匹配失敗，那麼我們嘗試匹配 x:xs，它必須成功。在這種情況下，我們返回 Just x。

對於我們的 findElement 函式，我們用值 Nothing 表示失敗，用值 a 表示成功，用 Just a 表示。我們的函式可能看起來像這樣

findElement :: (a -> Bool) -> [a] -> Maybe a
findElement p [] = Nothing
findElement p (x:xs) =
    if p x then Just x
    else findElement p xs

第一行在這裡給出函式的型別。在本例中，我們的第一個引數是謂詞（它接受一個型別為 a 的元素，並且當且僅當元素滿足謂詞時返回 True）；第二個引數是 a 的列表。我們的返回值是可能是 a。也就是說，如果函式成功，我們將返回 Just a，否則返回 Nothing。

另一個有用的資料型別是 Either 型別，定義為

data Either a b = Left a
                | Right b

這是一種表達選擇的途徑。也就是說，型別為 Either a b 的東西是要麼型別為 a 的值（使用 Left 建構函式），要麼型別為 b 的值（使用 Right 建構函式）。

練習
編寫一個數據型別 Tuple，它可以儲存一個、兩個、三個或四個元素，具體取決於建構函式（即，應該有四個建構函式，每個元素對應一個引數數量）。還提供函式 tuple1 到 tuple4，它們接受一個元組並返回 Just 該位置的值，或者如果數字無效則返回 Nothing（即，你要求 tuple4 在一個只儲存兩個元素的元組上）。 根據我們之前練習中對Tuple的定義，編寫一個函式，該函式接收一個Tuple並返回以下結果：如果它是一個單元組，則返回其值；如果它是一個二元組，則返回一個 Haskell 對（例如，('a',5)）；如果它是一個三元組，則返回一個 Haskell 三元組；如果它是一個四元組，則返回一個 Haskell 四元組。請記住：無法編寫一個返回不同型別的函式。您需要使用Either型別來表示這一點。

遞迴資料型別

我們還可以定義遞迴資料型別。這些資料型別的定義基於自身。例如，我們可以定義一個列表資料型別為

data List a = Nil
            | Cons a (List a)

在這個定義中，我們定義了List a型別的含義。我們說一個列表要麼是空的（Nil），要麼是Cons一個型別為a的值和另一個型別為List a的值。這幾乎與 Haskell 中列表資料型別的實際定義相同，只是使用特殊的語法，其中[]對應於Nil，:對應於Cons。我們可以為我們的列表編寫自己的length函式，如下所示

listLength Nil = 0
listLength (Cons x xs) = 1 + listLength xs

這個函式稍微複雜一些，並使用遞迴來計算List的長度。第一行表示空列表（Nil）的長度為 $0$。這是顯而易見的。第二行告訴我們如何計算非空列表的長度。非空列表必須是Cons x xs的形式，其中x和xs是某些值。我們知道xs是另一個列表，並且我們知道當前列表的長度無論是什麼，都是其尾部（xs的值）的長度加上一（為了考慮x）。因此，我們將listLength函式應用於xs並將結果加一。這給了我們整個列表的長度。

練習
編寫函式listHead、listTail、listFoldl和listFoldr，它們等效於它們的 Prelude 孿生兄弟，但 在我們的List資料型別上起作用。不要擔心前兩個的異常情況。

二叉樹

我們可以定義比列表更復雜的資料型別。假設我們想定義一個看起來像二叉樹的結構。二叉樹是一個結構，它有一個根節點；樹中的每個節點要麼是“葉子”，要麼是“分支”。如果是葉子，則它包含一個值；如果是分支，則它包含一個值以及一個左孩子和一個右孩子。這些孩子中的每一個都是另一個節點。我們可以定義這樣的資料型別，如下所示

data BinaryTree a
    = Leaf a
    | Branch (BinaryTree a) a (BinaryTree a)

在這個資料型別宣告中，我們說BinaryTree的a要麼是Leaf，它包含一個a，要麼是包含一個左孩子（它是一個BinaryTree的a）、一個節點值（它是一個a）和一個右孩子（它也是一個BinaryTree的a）的分支。簡單地修改listLength函式，使它不再計算列表的長度，而是計算BinaryTree中的節點數量。你能弄清楚怎麼做嗎？我們可以稱此函式為treeSize。解決方案如下所示

treeSize (Leaf x) = 1
treeSize (Branch left x right) =
  1 + treeSize left + treeSize right

這裡，我們說葉子的尺寸為 $1$，而分支的尺寸是其左孩子的尺寸加上其右孩子的尺寸，再加上一。

練習
編寫一個函式elements，它以自下而上、從左到右的方式返回BinaryTree中的元素（即，返回的第一個元素是最左邊的葉子，然後是其父節點的值，然後是另一個孩子的值，依此類推）。結果型別應該是一個正常的 Haskell 列表。 為BinaryTree編寫一個 foldr 函式treeFoldr，並用它重寫elements（將新函式命名為elements2）。treeFoldr的型別應為(a -> b -> b) -> b -> BinaryTree a -> b。 為BinaryTree編寫一個 foldl 函式treeFoldl，並用它重寫elements（將新函式命名為elements3）。

列舉集

您還可以使用資料型別來定義諸如列舉集之類的東西，例如，只能具有有限數量值的型別。我們可以定義一個顏色型別

data Color
    = Red
    | Orange
    | Yellow
    | Green
    | Blue
    | Purple
    | White
    | Black

這足以處理簡單的顏色。假設我們正在使用它來編寫一個繪圖程式，那麼我們可以編寫一個函式來在Color和 RGB 三元組之間轉換。我們可以編寫一個colorToRGB函式，如下所示

colorToRGB Red    = (255,0,0)
colorToRGB Orange = (255,128,0)
colorToRGB Yellow = (255,255,0)
colorToRGB Green  = (0,255,0)
colorToRGB Blue   = (0,0,255)
colorToRGB Purple = (255,0,255)
colorToRGB White  = (255,255,255)
colorToRGB Black  = (0,0,0)

如果我們還想讓使用者定義自己的自定義顏色，我們可以將Color資料型別更改為類似的東西

data Color
    = Red
    | Orange
    | Yellow
    | Green
    | Blue
    | Purple
    | White
    | Black
    | Custom Int Int Int -- R G B components

併為colorToRGB新增最終的定義

colorToRGB (Custom r g b) = (r,g,b)

單元型別

在 Haskell 中（來自 Prelude）定義的最後一個有用的資料型別是單元型別。它的定義是

data () = ()

此型別的唯一真值為()。這本質上與 C 或 Java 等語言中的void型別相同，當我們在本章Io中討論 IO 時將很有用。

我們將在模式匹配和資料型別部分中更深入地探討資料型別。

延續傳遞風格

有一種稱為“延續傳遞風格”（也簡稱為“CPS”）的函數語言程式設計風格。CPS 背後的理念是將下一步該做什麼作為函式引數傳遞。我將透過一個例子來解釋，這個例子過於複雜，無法在此時寫出來，然後給出一個真實的例子，儘管它缺乏動機。

考慮解析問題。這裡的理念是，我們有一系列標記（單詞、字母，等等），我們想賦予它們結構。將 Java 標記字串轉換為 Java 抽象語法樹的任務是解析問題的示例。解析英文句子也是如此（儘管後者非常困難，即使對於母語為英語的人來說，解析來自現實世界的句子也很困難）。

假設我們正在解析類似 C 或 Java 的東西，其中函式在括號中接受引數。但為了簡單起見，假設它們沒有用逗號分隔。也就是說，函式呼叫看起來像myFunction(x y z)。我們想將其轉換為類似於包含第一個字串“myFunction”和第二個包含三個字串元素的列表（“x”、“y”和“z”）的對。

解決這個問題的普遍方法是編寫一個函式來解析像這樣的函式呼叫。首先它會查詢識別符號（“myFunction”），然後查詢左括號，然後查詢零個或多個識別符號，然後查詢右括號。

一種方法是使用兩個函式

parseFunction   ::
    [Token] -> Maybe ((String, [String]), [Token])

parseIdentifier ::
    [Token] -> Maybe (String, [Token])

這裡的想法是，如果我們呼叫parseFunction，如果它沒有返回Nothing，那麼它會返回前面描述的對，以及解析函式後剩餘的任何內容。類似地，parseIdentifier將解析其中一個引數。如果它返回Nothing，那麼它不是引數；如果它返回Just，那麼那個Just就是與剩餘標記配對的引數。

parseFunction函式將做的是解析一個識別符號。如果失敗，它本身就會失敗。否則，它會繼續嘗試解析左括號。如果成功，它會重複呼叫parseIdentifier，直到失敗。然後它會嘗試解析右括號。如果成功，則完成。否則，它會失敗。

但是，還有另一種思考這個問題的方法。這種解決方案的優勢在於，函式不再需要返回剩餘的標記（這往往很醜陋）。與其使用上面的方法，我們編寫函式

parseFunction   ::
    [Token] -> ((String, [String]) -> [Token] -> a) ->
    ([Token] -> a) -> a

parseIdentifier ::
    [Token] -> (String -> [Token] -> a) ->
    ([Token] -> a) -> a

讓我們考慮 `parseIdentifier` 函式。它接受三個引數：一個 token 列表和兩個 *continuation*。第一個 continuation 用於成功時的操作，第二個 continuation 用於失敗時的操作。`parseIdentifier` 的作用就是嘗試讀取一個識別符號。如果成功，它將使用該識別符號和剩餘的 token 作為引數呼叫第一個 continuation。如果讀取識別符號失敗，它將使用所有 token 呼叫第二個 continuation。

現在考慮 `parseFunction` 函式。回顧一下，它想要讀取一個識別符號、一個左括號、零個或多個識別符號和一個右括號。因此，它首先呼叫 `parseIdentifier` 函式。它傳遞給 `parseIdentifier` 的第一個引數是 token 列表。第一個 continuation（即 `parseIdentifier` 成功時的操作）是一個函式，它將查詢左括號、零個或多個引數和一個右括號。第二個 continuation（失敗引數）將直接使用傳遞給 `parseFunction` 的失敗函式。

現在，我們只需要定義一個函式，它查詢左括號、零個或多個引數和一個右括號。這很簡單。我們編寫一個函式，它查詢左括號，然後呼叫 `parseIdentifier`，使用成功 continuation 來查詢更多識別符號，以及使用 "失敗" continuation 來查詢右括號（注意，這種失敗並不真正意味著失敗——它只是意味著沒有更多引數了）。

我知道這段討論很抽象。我樂於提供所有解析的程式碼，但這可能在目前過於複雜。相反，讓我們考慮在一個列表上摺疊的問題。我們可以編寫一個 CPS 風格的摺疊函式：

cfold' f z [] = z
cfold' f z (x:xs) = f x z (\y -> cfold' f y xs)

在這段程式碼中，`cfold'` 接收一個函式 `f`，它接受三個引數，與標準摺疊函式略有不同。第一個是當前列表元素 `x`，第二個是累積元素 `z`，第三個是 continuation：基本上，接下來要做什麼。

我們可以為 `cfold'` 編寫一個包裝函式，使其表現得更像一個正常的摺疊函式：

cfold f z l = cfold' (\x t g -> f x (g t)) z l

我們可以測試此函式是否按我們期望的方式執行：

示例

CPS> cfold (+) 0 [1,2,3,4]
10
CPS> cfold (:) [] [1,2,3]
[1,2,3]

用輔助函式 `cfold'` 來構建 `cfold` 函式的一大好處是，我們可以直接使用輔助函式。這使得我們可以非常輕鬆地改變摺疊的執行順序，例如：

示例

CPS> cfold' (\x t g -> (x : g t)) [] [1..10]
[1,2,3,4,5,6,7,8,9,10]
CPS> cfold' (\x t g -> g (x : t)) [] [1..10]
[10,9,8,7,6,5,4,3,2,1]

這些對 `cfold'` 的呼叫之間的唯一區別是，我們是在構造列表之前還是之後呼叫 continuation。事實證明，這種細微的差異將行為從類似 `foldr` 變成了類似 `foldl`。我們可以像下面這樣評估這兩個呼叫（設 `f` 是摺疊函式）：

     cfold' (\x t g -> (x : g t)) [] [1,2,3]
==>  cfold' f [] [1,2,3]
==>  f 1 [] (\y -> cfold' f y [2,3])
==>  1 : ((\y -> cfold' f y [2,3]) [])
==>  1 : (cfold' f [] [2,3])
==>  1 : (f 2 [] (\y -> cfold' f y [3]))
==>  1 : (2 : ((\y -> cfold' f y [3]) []))
==>  1 : (2 : (cfold' f [] [3]))
==>  1 : (2 : (f 3 [] (\y -> cfold' f y [])))
==>  1 : (2 : (3 : (cfold' f [] [])))
==>  1 : (2 : (3 : []))
==>  [1,2,3]

     cfold' (\x t g -> g (x:t)) [] [1,2,3]
==>  cfold' f [] [1,2,3]
==>  (\x t g -> g (x:t)) 1 [] (\y -> cfold' f y [2,3])
==>  (\g -> g [1]) (\y -> cfold' f y [2,3])
==>  (\y -> cfold' f y [2,3]) [1]
==>  cfold' f [1] [2,3]
==>  (\x t g -> g (x:t)) 2 [1] (\y -> cfold' f y [3])
==>  cfold' f (2:[1]) [3]
==>  cfold' f [2,1] [3]
==>  (\x t g -> g (x:t)) 3 [2,1] (\y -> cfold' f y [])
==>  cfold' f (3:[2,1]) []
==>  [3,2,1]

總的來說，continuation passing style 是一種非常強大的抽象，儘管它可能難以掌握。我們將在本書後面更深入地討論這個主題。

練習
測試 CPS 風格的摺疊是否模仿了 `foldr` 或 `foldl` 中的任何一個。如果不是，差異在哪裡？ 使用 continuation passing style 編寫 `map` 和 `filter` 函式。