第 8 章：声明类型与类（Declaring types and classes）
原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 8。维护者已确认本书可翻译并发布用于学习研究。
本章介绍在 Haskell 中声明新类型和新类的机制。我们先介绍三种声明类型的方法，然后讨论递归类型，说明如何声明类及其实例，最后开发一个重言式检查器和一台抽象机。
8.1 类型声明（Type declarations）
声明新类型最简单的方法，是使用 Haskell 的 type 机制，为已有类型引入一个新名字。例如，标准 Prelude 中的下面声明说明，类型 String 只是字符列表类型 [Char] 的同义词：
type String = [Char]
和这个例子一样，新类型的名字必须以大写字母开头。类型声明可以嵌套，也就是说，一个类型可以根据另一个类型来声明。例如，如果我们要定义一些转换坐标位置的函数，可以把位置声明为一对整数，并把变换声明为位置上的函数：
type Pos = (Int,Int)
type Trans = Pos -> Pos
不过，类型声明不能是递归的。例如，考虑下面这个树类型的递归声明：
type Tree = (Int,[Tree])
也就是说，树是一对值，由一个整数和一列子树组成。这个声明本身完全合理，其中空子树列表构成递归的基本情况，但 Haskell 不允许这种声明，因为它是递归的。如果需要，可以使用更强大的 data 机制来声明递归类型，下一节会介绍这种机制。
类型声明也可以用其他类型作为参数。例如，如果要定义一些操作同类型值对的函数，可以为这类值对声明一个同义词：
type Pair a = (a,a)
最后，类型声明也可以有多个参数。例如，把一种类型的键关联到另一种类型的值的查找表，可以声明为一列 (key,value) 对：
type Assoc k v = [(k,v)]
使用这个类型后，可以定义一个函数，返回表中与给定键关联的第一个值：
find :: Eq k => k -> Assoc k v -> v
find k t = head [v | (k',v) <- t, k == k']
8.2 数据声明（Data declarations）
与现有类型的同义词不同，一个全新的类型可以通过 Haskell 的 data 机制指定其值来声明。例如，标准 Prelude 中的下面声明说明，类型 Bool 由两个新值组成，分别命名为 False 和 True：
data Bool = False | True
在这类声明中，符号 | 读作“或”，而类型的新值称为构造子（constructors）。和新类型本身一样，新构造子的名字也必须以大写字母开头。此外，同一个构造子名不能在多个类型中使用。
注意，对 Haskell 系统来说，赋给新类型和构造子的名字本身没有内在含义。例如，上面的声明同样可以写成 data A = B | C，因为名字的具体细节并不重要，除了这些名字之前没有被使用过。像 Bool、False 和 True 这样的名字的含义，是程序员通过他们在新类型上定义的函数赋予的。
Haskell 中新类型的值可以用和内置类型的值完全相同的方式使用。特别是，它们可以自由地作为参数传给函数、作为函数结果返回、存储在数据结构中，以及用于模式。例如，给定声明：
data Move = North | South | East | West
那么可以定义如下函数：把一个移动应用到一个位置、把一列移动应用到一个位置、以及反转一个移动的方向：
move :: Move -> Pos -> Pos
move North (x,y) = (x,y+1)
move South (x,y) = (x,y-1)
move East (x,y) = (x+1,y)
move West (x,y) = (x-1,y)
moves :: [Move] -> Pos -> Pos
moves [] p = p
moves (m:ms) p = moves ms (move m p)
rev :: Move -> Move
rev North = South
rev South = North
rev East = West
rev West = East
如果你希望在 GHCi 中试验这类例子，需要在 data 声明末尾添加短语 deriving Show，以确保系统可以显示新类型的值。deriving 机制本身会在本章后面讨论类型类时介绍。
data 声明中的构造子也可以带参数。例如，由给定半径的圆和给定尺寸的矩形组成的形状类型，可以这样声明：
data Shape = Circle Float | Rect Float Float
也就是说，类型 Shape 的值可以是 Circle r 这种形式，其中 r 是浮点数；也可以是 Rect x y 这种形式，其中 x 和 y 是浮点数。然后，这些构造子可以用于定义作用于形状的函数，例如生成给定大小的正方形，以及计算形状面积：
square :: Float -> Shape
square n = Rect n n
area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect x y) = x * y
由于带有参数，构造子 Circle 和 Rect 实际上是构造子函数，它们从 Float 类型参数产生 Shape 类型结果。这可以用 GHCi 展示：
> :type Circle
Circle :: Float -> Shape
> :type Rect
Rect :: Float -> Float -> Shape
普通函数和构造子函数的区别在于，后者没有定义方程，纯粹用于构造数据。例如，表达式 negate 1.0 可以通过应用 negate 的定义求值得到 -1.0，而表达式 Circle 1.0 已经完全求值，不能继续简化，因为 Circle 没有定义方程。相反，表达式 Circle 1.0 只是一段数据，就像 1.0 本身只是数据一样。
毫不意外，data 声明本身也可以参数化。例如，标准 Prelude 声明了下面的类型：
data Maybe a = Nothing | Just a
也就是说，类型 Maybe a 的值要么是 Nothing，要么是 Just x 这种形式，其中 x 是某个类型为 a 的值。可以把 Maybe a 类型的值看作可能失败也可能成功的 a 类型值，其中 Nothing 表示失败，Just 表示成功。例如，使用这个类型可以定义库函数 div 和 head 的安全版本，它们在参数无效时返回 Nothing，而不是产生错误：
safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv m n = Just (m `div` n)
safehead :: [a] -> Maybe a
safehead [] = Nothing
safehead xs = Just (head xs)
8.3 newtype 声明（Newtype declarations）
如果一个新类型只有一个构造子，而这个构造子只有一个参数，那么也可以使用 newtype 机制来声明它。例如，自然数（非负整数）类型可以声明如下：
newtype Nat = N Int
在这个例子中，唯一构造子 N 接收一个类型为 Int 的参数，然后由程序员负责确保这个参数总是非负的。当然，很自然会问，上面使用 newtype 的声明，与下面分别使用 type 和 data 的替代版本相比有什么区别：
type Nat = Int
data Nat = N Int
首先，使用 newtype 而不是 type 意味着 Nat 和 Int 是不同类型，而不是同义词。因此，Haskell 的类型系统会确保它们不会在程序中被意外混用，例如在期望自然数的地方使用整数。其次，使用 newtype 而不是 data 带来效率好处，因为像 N 这样的 newtype 构造子在程序求值时不会产生任何开销，它们会在类型检查完成后由编译器自动移除。总之，使用 newtype 有助于提高类型安全性，同时不影响性能。
8.4 递归类型（Recursive types）
使用 data 和 newtype 机制声明的新类型也可以是递归的。作为第一个简单例子，前一节的自然数类型也可以用递归方式声明：
data Nat = Zero | Succ Nat
也就是说，类型 Nat 的值要么是 Zero，要么是 Succ n 这种形式，其中 n 是某个类型为 Nat 的值。因此，这个声明产生了一个无限值序列，从值 Zero 开始，并通过把构造子函数 Succ 应用于序列中的前一个值继续：
Zero
Succ Zero
Succ (Succ Zero)
Succ (Succ (Succ Zero))
...
通过这种方式，类型 Nat 的值对应自然数，其中 Zero 表示数字 0，Succ 表示后继函数 (+1)。例如，Succ (Succ (Succ Zero)) 表示 1 + (1 + (1 + 0)) = 3。更形式化地说，可以定义下面的转换函数：
nat2int :: Nat -> Int
nat2int Zero = 0
nat2int (Succ n) = 1 + nat2int n
int2nat :: Int -> Nat
int2nat 0 = Zero
int2nat n = Succ (int2nat (n-1))
例如，使用这些函数，可以通过先把两个自然数转换为整数、把这些整数相加、再把结果转换回自然数，来对两个自然数求和：
add :: Nat -> Nat -> Nat
add m n = int2nat (nat2int m + nat2int n)
不过，使用递归后，函数 add 可以重新定义，而不需要进行这些转换，因此效率更高：
add :: Nat -> Nat -> Nat
add Zero n = n
add (Succ m) n = Succ (add m n)
这个定义形式化了这样一个思想：两个自然数相加可以通过从第一个数复制 Succ 构造子直到它们耗尽来完成；此时，把末尾的 Zero 替换为第二个数。例如，证明 2 + 1 = 3 的过程如下：
add (Succ (Succ Zero)) (Succ Zero)
= { applying add }
Succ (add (Succ Zero) (Succ Zero))
= { applying add }
Succ (Succ (add Zero (Succ Zero)))
= { applying add }
Succ (Succ (Succ Zero))
作为另一个例子，可以使用 data 机制声明我们自己的内置列表类型版本，并用任意类型作为参数：
data List a = Nil | Cons a (List a)
也就是说，类型 List a 的值要么是 Nil，表示空列表；要么是 Cons x xs 这种形式，其中 x :: a 且 xs :: List a，表示非空列表。使用这个类型，也可以定义自己的列表库函数版本，例如计算列表长度：
len :: List a -> Int
len Nil = 0
len (Cons _ xs) = 1 + len xs
虽然列表是计算中最常用的数据结构之一，但用双向分支结构或二叉树存储数据也常常很有用。下面是一个示例树：
5
/ \
3 7
/ \ / \
1 4 6 9
在这个例子中，数字 1、4、6、9 出现在树的外部叶子上，而数字 5、3、7 出现在内部节点上。使用递归，可以声明一个适合表示这类树的类型：
data Tree a = Leaf a | Node (Tree a) a (Tree a)
上面画出的树可以表示如下：
t :: Tree Int
t = Node (Node (Leaf 1) 3 (Leaf 4)) 5
(Node (Leaf 6) 7 (Leaf 9))
现在考虑一些作用于这类树的函数。首先，定义一个函数，判断给定值是否出现在树中：
occurs :: Eq a => a -> Tree a -> Bool
occurs x (Leaf y) = x == y
occurs x (Node l y r) = x == y || occurs x l || occurs x r
也就是说，一个值出现在叶子中，当且仅当它与叶子上的值匹配；一个值出现在节点中，当且仅当它与节点上的值匹配，或出现在左子树中，或出现在右子树中。注意，在惰性求值下，如果节点情况中的前两个条件之一为 True，就会返回结果 True，而不需要对剩余条件求值。
不过在最坏情况下，函数 occurs 仍然可能遍历整棵树，尤其是给定值没有出现在树中时。现在考虑一个把树展平为列表的函数：
flatten :: Tree a -> [a]
flatten (Leaf x) = [x]
flatten (Node l x r) = flatten l ++ [x] ++ flatten r
如果把这个函数应用到一棵树后得到有序列表，那么这棵树称为搜索树。例如，我们的示例树就是一棵搜索树，因为：
flatten t = [1,3,4,5,6,7,9]
搜索树具有一个重要性质：当试图判断给定值是否出现在树中时，总能预先确定它可能出现在某个节点的哪棵子树中。具体来说，如果该值小于节点上的值，那么它只能出现在左子树中；如果大于这个值，那么它只能出现在右子树中。因此，对于搜索树，函数 occurs 可以重写如下：
occurs :: Ord a => a -> Tree a -> Bool
occurs x (Leaf y) = x == y
occurs x (Node l y r) | x == y = True
| x < y = occurs x l
| otherwise = occurs x r
这个定义比前一个版本更高效，因为它只沿着树中的一条路径向下遍历，而不是潜在地遍历整棵树。
本节最后注意，就像自然界中一样，计算中的树也有许多不同形式。例如，可以声明只在叶子中存储数据的树、只在节点中存储数据的树、叶子和节点中存储不同类型数据的树，或者带有子树列表的树：
data Tree a = Leaf a | Node (Tree a) (Tree a)
data Tree a = Leaf | Node (Tree a) a (Tree a)
data Tree a b = Leaf a | Node (Tree a b) b (Tree a b)
data Tree a = Node a [Tree a]
哪种树最合适取决于具体情况。注意，在最后一个例子中，没有叶子构造子，因为带有空子树列表的节点可以扮演叶子的角色。
8.5 类与实例声明（Class and instance declarations）
现在把注意力从类型转向类。在 Haskell 中，可以使用 class 机制声明新类。例如，标准 Prelude 中的相等类型类 Eq 声明如下：
class Eq a where
(==), (/=) :: a -> a -> Bool
x /= y = not (x == y)
这个声明说明，一个类型 a 要成为类 Eq 的实例，就必须支持指定类型的相等和不等操作符。事实上，因为已经为操作符 /= 包含了一个默认定义，所以声明实例时只需要为操作符 == 提供定义。例如，类型 Bool 可以这样成为相等类型：
instance Eq Bool where
False == False = True
True == True = True
_ == _ = False
只有使用 data 和 newtype 机制声明的类型才能成为类的实例。还要注意，如果愿意，实例声明可以覆盖默认定义。例如，对于某些相等类型，判断两个值是否不同，也许存在比简单检查它们不相等更高效或更合适的方法。
类也可以被扩展以形成新类。例如，值具有全序的类型类 Ord，在标准 Prelude 中声明为类 Eq 的扩展：
class Eq a => Ord a where
(<), (<=), (>), (>=) :: a -> a -> Bool
min, max :: a -> a -> a
min x y | x <= y = x
| otherwise = y
max x y | x <= y = y
| otherwise = x
也就是说，一个类型要成为 Ord 的实例，必须先是 Eq 的实例，并且支持六个额外操作符。因为 min 和 max 已经包含默认定义，所以把一个相等类型（例如 Bool）声明为有序类型，只需要定义四个比较操作符：
instance Ord Bool where
False < True = True
_ < _ = False
b <= c = (b < c) || (b == c)
b > c = c < b
b >= c = c <= b
派生实例（Derived instances）
声明新类型时，通常适合让它们成为若干内置类的实例。Haskell 提供了一个简单机制，可以自动让新类型成为 Eq、Ord、Show 和 Read 类的实例，这就是 deriving 机制。例如，类型 Bool 在标准 Prelude 中实际上声明如下：
data Bool = False | True
deriving (Eq, Ord, Show, Read)
因此，来自这四个派生类的所有成员函数都可以用于逻辑值。例如：
> False == False
True
> False < True
True
> show False
"False"
> read "False" :: Bool
False
最后一个例子中必须使用 :: 来解析结果类型，因为在这个上下文中，系统无法从函数的使用方式推断出结果类型。注意，对于派生有序类型类 Ord 的实例，某个类型构造子之间的顺序由它们在声明中的位置决定。因此，上面的 Bool 类型声明中，False 出现在 True 之前，这会得到顺序 False < True。
对于带参数的构造子，这些参数的类型也必须是任何派生类的实例。例如，回忆本章前面的两个声明：
data Shape = Circle Float | Rect Float Float
data Maybe a = Nothing | Just a
要把 Shape 派生为相等类型，要求类型 Float 也必须是相等类型，而事实确实如此。类似地，要把 Maybe a 派生为相等类型，要求类型 a 也必须是这类类型，而这会成为该参数上的类约束。和列表及元组一样，使用带参数构造子构造出来的值按字典序排序。例如，如果 Shape 也派生为有序类型，那么有：
> Rect 1.0 4.0 < Rect 2.0 3.0
True
> Rect 1.0 4.0 < Rect 1.0 3.0
False
8.6 重言式检查器（Tautology checker）
本章最后给出两个扩展编程示例。第一个例子中，我们开发一个函数，用于判断简单逻辑命题是否总为真。这类命题称为重言式（tautologies）。
考虑一种命题语言，它由基本值（False、True）和变量（A、B、...、Z）构成，并使用否定、合取、蕴含和括号组合起来。例如，下面都是命题：
A and not A
(A and B) implies A
A implies (A and B)
(A and (A implies B)) implies B
逻辑操作符的含义可以用真值表定义，真值表会给出每种参数值组合对应的结果值：
A not A
F T
T F
A B A and B
F F F
F T F
T F F
T T T
A B A implies B
F F T
F T T
T F F
T T T
为了在这类表格中节省空间，我们把基本值缩写为 F 和 T。例如，合取的真值表说明，A and B 在 A 和 B 都为 True 时返回 True，否则返回 False。使用这些定义，就可以构造任意命题的真值表。对于上面四个示例命题，结果表如下：
A A and not A
F F
T F
A B (A and B) implies A
F F T
F T T
T F T
T T T
A B A implies (A and B)
F F T
F T T
T F F
T T T
A B (A and (A implies B)) implies B
F F T
F T T
T F T
T T T
这些表说明第二个和第四个命题是重言式，因为它们的结果值总是 True；而第一个和第三个不是重言式，因为它们的结果在至少一种情况下为 False。
定义判断命题是否为重言式的函数，第一步是声明命题类型，并为命题可能具有的五种形式分别提供一个构造子：
data Prop = Const Bool
| Var Char
| Not Prop
| And Prop Prop
| Imply Prop Prop
注意，不需要显式提供括号构造子，因为可以使用 Haskell 自身的括号来表示分组。例如，上面的四个命题可以表示如下：
p1 :: Prop
p1 = And (Var 'A') (Not (Var 'A'))
p2 :: Prop
p2 = Imply (And (Var 'A') (Var 'B')) (Var 'A')
p3 :: Prop
p3 = Imply (Var 'A') (And (Var 'A') (Var 'B'))
p4 :: Prop
p4 = Imply (And (Var 'A') (Imply (Var 'A') (Var 'B'))) (Var 'B')
为了把命题求值为逻辑值，需要知道每个变量的值。为此，我们把替换（substitution）声明为一张查找表，它把变量名关联到逻辑值；这里使用本章开头引入的 Assoc 类型：
type Subst = Assoc Char Bool
例如，替换 [('A',False),('B',True)] 把变量 A 赋值为 False，把 B 赋值为 True。现在可以通过对命题可能具有的五种形式做模式匹配，定义一个函数，在给定变量替换的情况下对命题求值：
eval :: Subst -> Prop -> Bool
eval _ (Const b) = b
eval s (Var x) = find x s
eval s (Not p) = not (eval s p)
eval s (And p q) = eval s p && eval s q
eval s (Imply p q) = eval s p <= eval s q
例如，常量命题的值就是该常量本身；变量的值通过在替换中查找得到；合取的值通过取两个参数命题的值的合取得到。注意，逻辑蕴含操作符简单地由逻辑值上的 <= 顺序实现。
为了判断一个命题是否为重言式，我们会考虑它包含的变量的所有可能替换。首先，定义一个函数，返回命题中的所有变量列表：
vars :: Prop -> [Char]
vars (Const _) = []
vars (Var x) = [x]
vars (Not p) = vars p
vars (And p q) = vars p ++ vars q
vars (Imply p q) = vars p ++ vars q
例如，vars p2 = ['A','B','A']。注意，这个函数不会移除重复项，稍后会单独完成这件事。
生成替换的关键是产生给定长度的逻辑值列表。因此，我们希望定义函数 bools :: Int -> [[Bool]]，例如它会返回所有八个由三个逻辑值组成的列表：
> bools 3
[[False,False,False],
[False,False,True],
[False,True,False],
[False,True,True],
[True,False,False],
[True,False,True],
[True,True,False],
[True,True,True]]
实现这种行为的一种方式，是观察每个组件列表都可以通过把 False 和 True 分别解释为二进制数字 0 和 1，从而对应一个二进制数。例如，列表 [True,False,True] 对应二进制数 101。在这种解释下，可以把函数 bools 看作只是对适当范围内的数字进行二进制计数。
这个思想会导出下面的 bools 定义，它基于第 7 章中的函数 int2bin :: Int -> [Bit]，该函数把非负整数转换为表示为位列表的二进制数：
bools :: Int -> [[Bool]]
bools n = map (reverse . map conv . make n . int2bin) range
where
range = [0..(2^n)-1]
make n bs = take n (bs ++ repeat 0)
conv 0 = False
conv 1 = True
不过，通过思考结果列表的结构，可以得到一个更简单的 bools 定义。例如，可以观察到 bools 3 包含两份 bools 2：第一份中的每个列表前面都加上 False，第二份中的每个列表前面都加上 True：
False False False
False False True
False True False
False True True
True False False
True False True
True True False
True True True
这个观察导出了 bools 的递归定义。在基本情况 bools 0 中，我们返回所有由零个逻辑值组成的列表，这样的列表只有空列表一个。在递归情况 bools n 中，取 bools (n-1) 产生的列表的两份副本，在第一份的每个列表前加上 False，在第二份的每个列表前加上 True，再把结果连接起来：
bools :: Int -> [[Bool]]
bools 0 = [[]]
bools n = map (False:) bss ++ map (True:) bss
where
bss = bools (n-1)
使用 bools 后，现在可以直接定义一个函数，为某个命题生成所有可能替换：提取它的变量，移除这个列表中的重复项（使用第 7 章中的函数 rmdups），为这么多变量生成所有可能逻辑值列表，然后把变量列表与每个结果列表拉链配对：
substs :: Prop -> [Subst]
substs p = map (zip vs) (bools (length vs))
where
vs = rmdups (vars p)
例如：
> substs p2
[[('A',False),('B',False)],
[('A',False),('B',True)],
[('A',True),('B',False)],
[('A',True),('B',True)]]
最后，定义一个函数来判断命题是否为重言式：只需检查该命题在所有可能替换下的求值结果是否都为 True。
isTaut :: Prop -> Bool
isTaut p = and [eval s p | s <- substs p]
例如：
> isTaut p1
False
> isTaut p2
True
> isTaut p3
False
> isTaut p4
True
8.7 抽象机（Abstract machine）
第二个扩展示例考虑一种简单算术表达式类型，它由整数和加法操作符构成；同时给出一个函数，把这样的表达式求值为整数：
data Expr = Val Int | Add Expr Expr
value :: Expr -> Int
value (Val n) = n
value (Add x y) = value x + value y
例如，表达式 (2 + 3) + 4 的求值如下：
value (Add (Add (Val 2) (Val 3)) (Val 4))
= { applying value }
value (Add (Val 2) (Val 3)) + value (Val 4)
= { applying the first value }
(value (Val 2) + value (Val 3)) + value (Val 4)
= { applying the first value }
(2 + value (Val 3)) + value (Val 4)
= { applying the first value }
(2 + 3) + value (Val 4)
= { applying the first + }
5 + value (Val 4)
= { applying value }
5 + 4
= { applying + }
9
注意，函数 value 的定义并没有指定加法的左参数应该先于右参数求值，也没有更一般地指定每一点的下一步求值应该是什么。相反，求值顺序由 Haskell 决定。不过如果愿意，也可以通过为表达式定义抽象机来显式化这类控制信息，抽象机会指定表达式求值的逐步过程。
为此，首先为抽象机声明控制栈类型。控制栈由一列操作组成，这些操作将在当前求值完成后由机器执行：
type Cont = [Op]
data Op = EVAL Expr | ADD Int
两个操作的含义稍后解释。现在定义一个函数，在控制栈上下文中对表达式求值：
eval :: Expr -> Cont -> Int
eval (Val n) c = exec c n
eval (Add x y) c = eval x (EVAL y : c)
也就是说，如果表达式是整数，那么它已经完全求值，我们开始执行控制栈。如果表达式是加法，就对第一个参数 x 求值，并把操作 EVAL y 放到控制栈顶端，表示第一个参数求值完成后应该对第二个参数 y 求值。接着，定义一个函数，在整数参数上下文中执行控制栈：
exec :: Cont -> Int -> Int
exec [] n = n
exec (EVAL y : c) n = eval y (ADD n : c)
exec (ADD n : c) m = exec c (n+m)
也就是说，如果控制栈为空，就把整数参数作为执行结果返回。如果栈顶是操作 EVAL y，就对表达式 y 求值，并把操作 ADD n 放到剩余栈顶端，表示 y 求值完成后，应该把当前整数参数 n 与其求值结果相加。最后，如果栈顶是操作 ADD n，说明加法表达式两个参数的求值现在都已完成，于是在两个结果整数之和的上下文中执行剩余控制栈。
最后，定义一个函数，通过用给定表达式和空控制栈调用 eval，把表达式求值为整数：
value :: Expr -> Int
value e = eval e []
我们的抽象机使用两个相互递归的函数 eval 和 exec，这反映了它有两种运行模式，具体取决于当前是由表达式结构驱动，还是由控制栈驱动。为了说明这台机器，下面展示它如何求值 (2 + 3) + 4：
value (Add (Add (Val 2) (Val 3)) (Val 4))
= { applying value }
eval (Add (Add (Val 2) (Val 3)) (Val 4)) []
= { applying eval }
eval (Add (Val 2) (Val 3)) [EVAL (Val 4)]
= { applying eval }
eval (Val 2) [EVAL (Val 3), EVAL (Val 4)]
= { applying eval }
exec [EVAL (Val 3), EVAL (Val 4)] 2
= { applying exec }
eval (Val 3) [ADD 2, EVAL (Val 4)]
= { applying eval }
exec [ADD 2, EVAL (Val 4)] 3
= { applying exec }
exec [EVAL (Val 4)] 5
= { applying exec }
eval (Val 4) [ADD 5]
= { applying eval }
exec [ADD 5] 4
= { applying exec }
exec [] 9
= { applying exec }
9
注意，eval 如何向下走到表达式最左边的整数，同时在控制栈上维护一条待处理右侧表达式的轨迹。接着，exec 沿着这条轨迹向上推进，适时把控制交还给 eval 并执行加法。
8.8 章注（Chapter remarks）
抽象机示例源自文献 [11]，而本例中使用的控制栈类型，是用于遍历递归类型值的 zipper 数据结构 [12] 的一个特例。除了本章介绍的声明新类型和新类的基本机制之外，GHC 系统还支持若干更高级和实验性的类型特性；更多细节见 haskell.org/ghc。
8.9 练习（Exercises）
- 仿照函数
add，为自然数递归类型定义一个递归乘法函数mult :: Nat -> Nat -> Nat。提示：在定义中使用add。 - 虽然附录 B 中没有包含，但标准 Prelude 定义了：
data Ordering = LT | EQ | GT
以及函数：
compare :: Ord a => a -> a -> Ordering
该函数判断有序类型中的一个值是小于（LT）、等于（EQ），还是大于（GT）另一个值。使用这个函数，为搜索树重新定义函数 occurs :: Ord a => a -> Tree a -> Bool。为什么这个新定义比原始版本更高效？
- 考虑下面的二叉树类型：
data Tree a = Leaf a | Node (Tree a) (Tree a)
如果这类树的每个节点中，左子树和右子树的叶子数量最多相差一，并且叶子本身显然是平衡的，那么称这棵树是平衡的。定义函数 balanced :: Tree a -> Bool，判断一棵二叉树是否平衡。
提示：先定义一个返回树中叶子数量的函数。
- 定义函数
balance :: [a] -> Tree a，把非空列表转换为平衡树。提示：先定义一个函数，把列表分成两半，两半长度最多相差一。 - 给定类型声明：
data Expr = Val Int | Add Expr Expr
定义高阶函数：
folde :: (Int -> a) -> (a -> a -> a) -> Expr -> a
使得 folde f g 会把表达式中的每个 Val 构造子替换为函数 f，并把每个 Add 构造子替换为函数 g。
- 使用
folde，定义函数eval :: Expr -> Int，把表达式求值为整数；并定义函数size :: Expr -> Int，计算表达式中值的数量。 - 完成下面的实例声明：
instance Eq a => Eq (Maybe a) where
...
instance Eq a => Eq [a] where
...
- 扩展重言式检查器，使它支持命题中的逻辑析取和等价。
- 扩展抽象机，使它支持乘法。
练习 1-4 的解答见附录 A。