另一個 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 是布林（發音為“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.

的例項。

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 並將$x$ 的每次出現替換為$5$，得到$(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]

+和*的型別相同，這意味著+是一個函式，對於某種型別為Num例項的a，它接受一個型別為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 {new line} "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 列表，以生成一個型別為 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的資料型別宣告，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，如果數字無效（例如，你對僅包含兩個元素的元組請求tuple4），則返回Nothing。 基於我們之前練習中對Tuple的定義，編寫一個函式，該函式接收一個Tuple並返回其值（如果它是單元素元組），或者如果它是雙元素元組則返回一個Haskell對（例如，('a',5)），或者如果它是三元素元組則返回一個Haskell三元組，或者如果它是四元素元組則返回一個Haskell四元組。請記住：無法編寫一個返回不同型別的函式。你需要使用Either型別來表示這種情況。

遞迴資料型別

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

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

在這個定義中，我們定義了型別為List a的含義。我們說一個列表要麼是空的（Nil），要麼是型別為a的值和另一個型別為List a的值的Cons。這與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)

在這個資料型別宣告中，我們說a型別的BinaryTree要麼是一個包含a的Leaf，要麼是一個分支，它包含一個左子節點（它是a型別的BinaryTree）、一個節點值（它是a）和一個右子節點（它也是a型別的BinaryTree）。修改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某個值，則該值是與剩餘標記配對的引數。

parseFunction函式的作用是解析一個識別符號。如果失敗，它本身也會失敗。否則，它繼續並嘗試解析一個開括號。如果成功，它會重複呼叫parseIdentifier，直到失敗。然後它嘗試解析一個閉括號。如果成功，則完成。否則，失敗。

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

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

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

讓我們考慮一下parseIdentifier。它接受三個引數：一個標記列表和兩個延續。第一個延續是在成功時要執行的操作。第二個延續是在失敗時要執行的操作。然後，parseIdentifier的作用是嘗試讀取一個識別符號。如果成功，它會將該識別符號和剩餘的標記作為引數呼叫第一個延續。如果讀取識別符號失敗，它會將所有標記作為引數呼叫第二個延續。

現在考慮parseFunction。回想一下，它希望讀取一個識別符號、一個開括號、零個或多個識別符號以及一個閉括號。因此，它首先執行的操作是呼叫parseIdentifier。它提供的第一個引數是標記列表。第一個延續（如果parseIdentifier成功應執行的操作）反過來是一個函式，它將查詢一個開括號、零個或多個引數以及一個閉括號。第二個延續（失敗引數）將只是傳遞給parseFunction的失敗函式。

現在，我們只需要定義這個查詢一個開括號、零個或多個引數以及一個閉括號的函式。這很容易。我們編寫一個函式來查詢開括號，然後呼叫parseIdentifier，其成功延續查詢更多識別符號，而“失敗”延續查詢閉括號（請注意，此失敗並不真正意味著失敗——它只是意味著沒有更多引數了）。

我意識到這段討論非常抽象。我願意為所有這些解析提供程式碼，但目前可能過於複雜。相反，考慮跨列表摺疊的問題。我們可以將CPS摺疊寫成

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

在此程式碼中，cfold'接受一個函式f，該函式接受三個引數，與標準摺疊略有不同。第一個是當前列表元素x，第二個是累積元素z，第三個是延續：基本上是接下來要執行的操作。

我們可以為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'的這些呼叫的唯一區別是我們是在構建列表之前還是之後呼叫延續。事實證明，這種細微的差異會改變行為，從像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]

通常，延續傳遞風格是一種非常強大的抽象，儘管它可能難以掌握。我們將在本書的後面更全面地重新討論這個主題。

練習
測試 CPS 風格的摺疊是否模擬了foldr和foldl中的任何一個。如果不是，區別在哪裡？ 使用延續傳遞風格編寫map和filter。