June 30, 2020 8 min to read

CIS 194 02 Algebraic Data Types 代數數據類型

Source: 02-ADTs

▌Algebraic Data Types 代數數據類型

CIS 194 第 2 週

2013 年 1 月 21 日

建議閱讀：

Real World Haskell，第2章和第3章

▌Enumeration types 枚舉類型

與許多編程語言一樣，Haskell 允許程序員創建自己的枚舉類型。這是一個簡單的例子：

data Thing = Shoe 
           | Ship 
           | SealingWax 
           | Cabbage 
           | King
    deriving Show

聲明了一個新的類型稱為 Thing ，具有五個 data constructors Shoe ， Ship … 等，這是 Thing 類型唯一的值。（ deriving Show 是一個神奇的咒語，它告訴 GHC 自動生成用於將 Thing s 轉換為 String s 的默認代碼。這是 ghci 在打印 Thing 類型的表達式的值時所使用的）

shoe :: Thing
shoe = Shoe

listO'Things :: [Thing]
listO'Things = [Shoe, SealingWax, King, Cabbage, King]

我們可以透過 模式匹配 (pattern-matching) 在 Thing 上編寫函數

isSmall :: Thing -> Bool
isSmall Shoe       = True
isSmall Ship       = False
isSmall SealingWax = True
isSmall Cabbage    = True
isSmall King       = False

回顧一下如何按從上到下的順序嘗試函數子句，我們還可以使 isSmall 的定義簡短一些，如下所示：

isSmall2 :: Thing -> Bool
isSmall2 Ship = False
isSmall2 King = False
isSmall2 _    = True

▌Beyond enumerations 不只是/除了枚舉

Thing 是 枚舉類型 ，類似於其他語言（例如 Java/C++）提供的類型。但是，枚舉實際上只是 Haskell 更通用的 代數數據類型 的特例。作為不只是枚舉的數據類型的第一個示例，請考慮 FailableDouble 的定義：

data FailableDouble = Failure
                    | OK Double
    deriving Show

這表示該 FailableDouble 類型具有兩個數據構造函數。第一個 Failure 沒有參數，因此 Failure 它本身就是 type 的值 FailableDouble 。第二個 OK 參數接受 type 的參數 Double。因此 OK 本身不是類型的值 FailableDouble; 我們需要給它一個 Double 。例如，OK 3.4 是 type 的值 FailableDouble

ex01 = Failure
ex02 = OK 3.4

思想練習：OK 是什麼類型？

safeDiv :: Double -> Double -> FailableDouble
safeDiv _ 0 = Failure
safeDiv x y = OK (x / y)

更多模式匹配！請注意，在 OK 的函數子句，我們如何命名附帶的 Double 參數

failureToZero :: FailableDouble -> Double
failureToZero Failure = 0
failureToZero (OK d)  = d

數據構造函數可以有多過一個的參數

-- Store a person's name, age, and favourite Thing.
data Person = Person String Int Thing
    deriving Show

brent :: Person
brent = Person "Brent" 31 SealingWax

stan :: Person
stan  = Person "Stan" 94 Cabbage

getAge :: Person -> Int
getAge (Person _ a _) = a

請注意，類型構造函數和數據構造函數都是命名為 Person ，但是它們使用不同的名稱空間，並且是不同的東西。這種習慣（為一個構造函數的類型和數據構造函數賦予相同的名稱）是很常見的，但是在習慣之前會引起混淆。

▌Algebraic data types in general 一般的代數數據類型

通常，代數數據類型具有一個或多個數據構造函數，每個數據構造函數可以具有零個或多個參數。

data AlgDataType = Constr1 Type11 Type12
                 | Constr2 Type21
                 | Constr3 Type31 Type32 Type33
                 | Constr4

這指定類型的值 AlgDataType 可以以四種方式之一來構造：使用 Constr1 ， Constr2 ， Constr3，或 Constr4 。根據所使用的構造函數，一個 AlgDataType 值可能包含其他一些值。例如，如果使用構造它 Constr1，則它帶有兩個值，一個是 type Type11 ，另一個是 type Type12 。

最後一點：類型和數據構造函數名稱必須以大寫字母開頭。變量（包括函數名稱）必須以小寫字母開頭。（否則 Haskell 解析器將很難確定哪個名稱表示變量，哪個名稱表示構造函數）。

▌Pattern-matching 模式匹配

我們已經在一些特定案例下看到了模式匹配，但讓我們看看模式匹配通常是如何工作的。從根本上講，模式匹配是通過找出使用哪個構造函數來分解一個值。這些信息可以用作決定做什麼的基礎 —— 實際上，在 Haskell 中，這是做出決定的唯一方法。

難以翻譯，原文在這裏：

We’ve seen pattern-matching in a few specific cases, but let’s see how pattern-matching works in general. Fundamentally, pattern-matching is about taking apart a value by finding out which constructor it was built with. This information can be used as the basis for deciding what to do—indeed, in Haskell, this is the only way to make a decision.

例如，要決定如何處理 AlgDataType 類型的值（在上一節中定義），我們可以編寫類似

foo (Constr1 a b)   = ...
foo (Constr2 a)     = ...
foo (Constr3 a b c) = ...
foo Constr4         = ...

注意我們如何給每個構造函數附帶的值命名。另外，如果構造函數的參數多於一個，括號需要包圍著參數

這是模式背後的主要思想，但還有一些事情要注意

下劃線 _ 可以用作匹配任何內容的 “通配符模式”
x@pat 形式的模式可以將值與模式 pat 進行匹配，但也可以將名稱 x 賦予要匹配的整個值

難以翻譯，原文在這裏：

A pattern of the form x@pat can be used to match a value against the pattern pat, but also give the name x to the entire value being matched. For example:
```
baz :: Person -> String
baz p@(Person n _ _) = "The name field of (" ++ show p ++ ") is " ++ n
   
*Main> baz brent
"The name field of (Person \"Brent\" 31 SealingWax) is Brent"
```

模式可以 嵌套(nested) ：

checkFav :: Person -> String
checkFav (Person n _ SealingWax) = n ++ ", you're my kind of person!"
checkFav (Person n _ _)          = n ++ ", your favorite thing is lame."
   
*Main> checkFav brent
"Brent, you're my kind of person!"
*Main> checkFav stan
"Stan, your favorite thing is lame."

注意如何將模式 SealingWax 嵌套在 Person 的模式中

一般來說，以下語法定義了什麽可以作為模式

pat ::= _
     |  var
     |  var @ ( pat )
     |  ( Constructor pat1 pat2 ... patn )

第一行說下劃線是一種模式。第二行說變量本身是一個模式：這種模式匹配任何東西，並將給定的變量名 “綁定” 到匹配的值。第三行指定 @-patterns。最後一行說，構造函數名稱後跟隨一個序列是一個模式：如果該值是使用給定的構造函數構造的，則該模式將與該值匹配，且 pat1 至 patn 匹配該構造函數所包含的值，遞歸地。

難以翻譯，原文在這裏：

The first line says that an underscore is a pattern. The second line says that a variable by itself is a pattern: such a pattern matches anything, and “binds” the given variable name to the matched value. The third line specifies @-patterns. The last line says that a constructor name followed by a sequence of patterns is itself a pattern: such a pattern matches a value if that value was constructed using the given constructor, and pat1 through patn all match the values contained by the constructor, recursively.

（實際上，模式的完整語法包含了更多功能，但是其餘的功能會將我們帶到了很遠的地方）

請注意，像 2 或一樣的文字值 'c' 可以認為是沒有參數的構造函數。就像類型 Int 和 Char 定義一樣

data Int  = 0 | 1 | -1 | 2 | -2 | ...
data Char = 'a' | 'b' | 'c' | ...

這意味著我們可以對文字值(literal values)進行模式匹配。（當然，Int 和 Char 實際上 不是通過這種方式定義）

▌Case expressions 案例表達式

在 Haskell 中進行模式匹配的基本結構是 case 表達式。通常，case 表達式看起來像

case exp of
  pat1 -> exp1
  pat2 -> exp2
  ...

當評估時，表達 exp 被針對每個圖案的匹配 pat1，pat2 … 反過來。選擇第一個匹配模式，然後整個 case 表達式計算為與匹配模式相對應的表達式。例如：

ex03 = case "Hello" of
           []      -> 3
           ('H':s) -> length s
           _       -> 7

計算結果為 4（第二個模式被選擇。當然，第三個模式也匹配，但從未達到）

實際上，我們看到的用於定義函數的語法只是用於定義 case 表達式的語法糖。例如，先前的 failureToZero 的定義可以等效地寫為

failureToZero :: FailableDouble -> Double
failureToZero x = case x of
                    Failure -> 0
                    OK d    -> d

▌Recursive data types 遞歸數據類型

數據類型可以遞歸，即根據自身定義。實際上，我們已經看到了遞歸類型 —— 列表類型。列表為空，或為單個元素，後跟剩餘列表。我們可以這樣定義自己的列表類型：

data IntList = Empty | Cons Int IntList

Haskell 自己的內置列表非常相似。他們只是使用特殊的內置語法（ [] 和 : ）。（當然，它們也適用於任何類型的元素，而不僅僅是 Ints，下週將繼續介紹）

我們經常使用遞歸函數來處理遞歸數據類型：

intListProd :: IntList -> Int
intListProd Empty      = 1
intListProd (Cons x l) = x * intListProd l

作為另一個簡單的示例，我們可以定義一種二叉樹的類型，其 Int 值存儲在每個內部節點上，而值 Char 存儲在每個葉上：

data Tree = Leaf Char
          | Node Tree Int Tree
deriving Show

（不要問我您將把這樣的樹用於什麼；這是一個示例，好嗎？）例如：

tree :: Tree
tree = Node (Leaf 'x') 1 (Node (Leaf 'y') 2 (Leaf 'z'))

CWKSC's 翻譯文章