第 3 章：类型与类（Types and classes）
原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 3。维护者已确认本书可翻译并发布用于学习研究。
本章介绍类型和类，它们是 Haskell 中两个最基础的概念。我们先解释什么是类型，以及类型在 Haskell 中如何使用；然后介绍若干基本类型，以及通过组合较小类型来构造较大类型的方式；接着更详细地讨论函数类型；最后介绍多态类型和类型类的概念。
3.1 基本概念（Basic concepts）
类型是一组相关值的集合。例如，类型 Bool 包含两个逻辑值 False 和 True，而类型 Bool -> Bool 包含所有把 Bool 类型参数映射为 Bool 类型结果的函数，例如逻辑取反函数 not。我们用记法 v :: T 表示 v 是类型 T 中的一个值，并说 v 具有类型 T。例如：
False :: Bool
True :: Bool
not :: Bool -> Bool
更一般地，符号 :: 也可以用于尚未求值的表达式。在这种情况下，记法 e :: T 表示对表达式 e 求值将产生一个类型为 T 的值。例如：
not False :: Bool
not True :: Bool
not (not False) :: Bool
在 Haskell 中，每个表达式都必须具有一个类型，这个类型会在表达式求值之前通过称为**类型推断（type inference）**的过程计算出来。这个过程的关键，是下面这条简单的函数应用类型规则：如果 f 是一个把类型 A 的参数映射为类型 B 的结果的函数，而 e 是类型为 A 的表达式，那么应用 f e 的类型就是 B：
f :: A -> B
e :: A
f e :: B
例如，根据 not :: Bool -> Bool 和 False :: Bool，可以用这条规则推断出 not False :: Bool。另一方面，表达式 not 3 无法根据上面的规则得到类型，因为这要求 3 :: Bool，而这是无效的：3 不是逻辑值。像 not 3 这样没有类型的表达式称为包含类型错误（type error），并被视为无效表达式。
因为类型推断发生在求值之前，所以 Haskell 程序是**类型安全（type safe）**的，也就是说，类型错误永远不会在求值期间发生。在实践中，类型推断能检测出大量程序错误，是 Haskell 最有用的特性之一。不过请注意，使用类型推断并不意味着求值期间不会出现其他种类的错误。例如，表达式 1 `div` 0 类型正确，但求值时会产生错误，因为除以零的结果没有定义。
类型安全的代价是：某些能够成功求值的表达式，会因为类型原因而被拒绝。例如，条件表达式 if True then 1 else False 会求值得到数字 1，但它包含类型错误，因此被视为无效表达式。具体来说，条件表达式的类型规则要求两个可能结果具有相同类型；而在这个例子中，第一个结果 1 是数字，第二个结果 False 是逻辑值。不过在实践中，程序员会很快学会在类型系统的边界内工作，并避免这类问题。
在 GHCi 中，可以在表达式前加上命令 :type 来显示任意表达式的类型。例如：
> :type not
not :: Bool -> Bool
> :type False
False :: Bool
> :type not False
not False :: Bool
3.2 基本类型（Basic types）
Haskell 提供了若干内置于语言的基本类型，其中最常用的类型如下。
Bool：逻辑值（logical values）
这个类型包含两个逻辑值 False 和 True。
Char：单个字符（single characters）
这个类型包含 Unicode 系统中的所有单个字符。Unicode 是表示文本信息的国际标准。例如，它包含普通英文键盘上的所有字符，例如 'a'、'A'、'3' 和 '_'，也包含一些具有特殊效果的控制字符，例如 '\n'（移动到新的一行）和 '\t'（移动到下一个制表位）。与大多数编程语言一样，单个字符必须写在一对单引号 ' ' 中。
String：字符串（strings of characters）
这个类型包含所有字符序列，例如 "abc"、"1+2=3"，以及空字符串 ""。同样，与大多数编程语言中的标准做法一样，字符串必须写在一对双引号 " " 中。
Int：固定精度整数（fixed-precision integers）
这个类型包含整数，例如 -100、0 和 999，并使用固定数量的内存进行存储。例如，GHC 系统中 Int 类型的取值范围是从 -2^63 到 2^63 - 1。超出这个范围可能会得到意外结果。例如，对 2^63 :: Int 求值会得到一个负数，这是不正确的。（这里使用 :: 是为了强制结果为 Int，而不是其他某种数字类型。）
Integer：任意精度整数（arbitrary-precision integers）
这个类型包含所有整数，并会根据需要使用足够多的内存进行存储，因此不会对数字范围施加上下限。例如，在任何 Haskell 系统中对 2^63 :: Integer 求值，都会产生正确结果。
除了 Int 与 Integer 在数字内存需求和精度上不同，选择哪一个类型还涉及性能问题。特别是，大多数计算机都有用于固定精度整数的内置硬件；而任意精度整数通常以数字序列的形式通过软件处理，因此速度较慢。
Float：单精度浮点数（single-precision floating-point numbers）
这个类型包含带小数点的数字，例如 -12.34、1.0 和 3.1415927，并使用固定数量的内存进行存储。“浮点（floating-point）”这个术语来自这样一个事实：小数点后允许的数字位数取决于数字的大小。例如，在 GHCi 中对 sqrt 2 :: Float 求值会得到 1.4142135（库函数 sqrt 用于计算浮点数的平方根），它在小数点后有七位数字；而 sqrt 99999 :: Float 会得到 316.2262，小数点后只有四位数字。
Double：双精度浮点数（double-precision floating-point numbers）
这个类型类似于 Float，但为了提高精度，会使用两倍内存存储这些数字。例如，对 sqrt 2 :: Double 求值会得到 1.4142135623730951。使用浮点数是一个专门主题，需要谨慎处理舍入误差，本书不会经常使用这类数字。
本节最后需要注意：同一个数字可以具有多个数字类型。例如，数字 3 可以具有类型 Int、Integer、Float 或 Double。这引出了一个有趣问题：在类型推断过程中，这类数字应该被赋予什么类型？本章稍后讨论类型类时会回答这个问题。
3.3 列表类型（List types）
列表是由相同类型元素组成的序列，元素写在方括号中，并用逗号分隔。我们用 [T] 表示所有元素类型为 T 的列表的类型。例如：
[False,True,False] :: [Bool]
['a','b','c','d'] :: [Char]
["One","Two","Three"] :: [String]
列表中元素的数量称为它的长度（length）。长度为零的列表 [] 称为空列表；长度为一的列表，例如 [False]、['a'] 和 [[]]，称为单元素列表。注意，[[]] 和 [] 是不同的列表，前者是一个以空列表为唯一元素的单元素列表，而后者只是没有任何元素的空列表。
关于列表类型，还需要注意三点。首先，列表的类型不包含关于列表长度的信息。例如，列表 [False,True] 和 [False,True,False] 都具有类型 [Bool]，尽管它们的长度不同。其次，列表元素的类型没有限制。由于目前除了基本类型之外，我们只介绍了列表类型，所以例子范围有限，但我们可以拥有列表的列表，例如：
[['a','b'],['c','d','e']] :: [[Char]]
最后，列表不要求具有有限长度。特别是，由于 Haskell 使用惰性求值，无限长度列表既自然又实用，我们将在第 15 章看到这一点。
3.4 元组类型（Tuple types）
元组是由有限个分量组成的序列，这些分量可以具有不同类型；分量写在圆括号中，并用逗号分隔。我们用 (T1,T2,...,Tn) 表示所有第 i 个分量具有类型 Ti（其中 i 的范围是 1 到 n）的元组的类型。例如：
(False,True) :: (Bool,Bool)
(False,'a',True) :: (Bool,Char,Bool)
("Yes",True,'a') :: (String,Bool,Char)
元组中分量的数量称为它的元数（arity）。元数为零的元组 () 称为空元组；元数为二的元组称为二元组或对（pair）；元数为三的元组称为三元组（triple），依此类推。元数为一的元组，例如 (False)，是不允许的，因为它会与用圆括号显式表示求值顺序的写法冲突，例如 (1+2)*3。
与列表类型类似，关于元组类型也需要注意三点。首先，元组的类型包含它的元数。例如，类型 (Bool,Char) 包含所有这样的二元组：第一个分量类型为 Bool，第二个分量类型为 Char。其次，元组分量的类型没有限制。例如，现在我们可以拥有元组的元组、列表的元组，以及元组的列表：
('a',(False,'b')) :: (Char,(Bool,Char))
(['a','b'],[False,True]) :: ([Char],[Bool])
[('a',False),('b',True)] :: [(Char,Bool)]
最后请注意，元组必须具有有限元数，以确保元组类型总是能在求值之前被推断出来。
3.5 函数类型（Function types）
函数是从一种类型的参数到另一种类型的结果的映射。我们用 T1 -> T2 表示所有把类型 T1 的参数映射为类型 T2 的结果的函数的类型。例如：
not :: Bool -> Bool
even :: Int -> Bool
（库函数 even 用于判断一个整数是否为偶数。）由于函数的参数类型和结果类型没有限制，单参数单结果函数这个简单概念已经足以处理多参数和多结果的情况：可以使用列表或元组来打包多个值。例如，可以定义一个函数 add 来计算一对整数之和，并定义一个函数 zeroto 来返回从零到给定上限的整数列表：
add :: (Int,Int) -> Int
add (x,y) = x+y
zeroto :: Int -> [Int]
zeroto n = [0..n]
在这些例子中，我们遵循 Haskell 的约定：在函数定义前写出函数类型，这可以作为有用的文档。用户手动提供的任何类型，都会被检查是否与类型推断自动计算出的类型一致。
请注意，函数不一定要在其参数类型上是全函数（total）。也就是说，可能存在某些参数，其结果没有定义。例如，库函数 head 用于选择列表的第一个元素，但如果列表为空，其结果没有定义：
> head []
*** Exception: Prelude.head: empty list
3.6 柯里化函数（Curried functions）
多参数函数还可以用另一种也许不那么明显的方式处理：利用函数可以自由返回函数作为结果这一事实。例如，考虑下面的定义：
add' :: Int -> (Int -> Int)
add' x y = x+y
这个类型说明，add' 是一个接收 Int 类型参数，并返回类型为 Int -> Int 的函数作为结果的函数。定义本身说明，add' 接收一个整数 x，随后接收一个整数 y，并返回结果 x+y。更准确地说，add' 接收一个整数 x 并返回一个函数，而这个函数再接收一个整数 y 并返回结果 x+y。
注意，函数 add' 与上一节中的函数 add 产生相同的最终结果。但 add 是同时接收两个打包为一个二元组的参数，而 add' 是一次接收一个参数；这一点体现在两个函数的不同类型中：
add :: (Int,Int) -> Int
add' :: Int -> (Int -> Int)
具有两个以上参数的函数也可以用同样技术处理：返回函数，再由这些函数继续返回函数，依此类推。例如，一个接收三个整数 x、y 和 z（一次一个），并返回它们乘积的函数 mult 可以定义如下：
mult :: Int -> (Int -> (Int -> Int))
mult x y z = x*y*z
这个定义说明，mult 接收一个整数 x 并返回一个函数；这个函数再接收一个整数 y 并返回另一个函数；最后这个函数接收一个整数 z 并返回结果 x*y*z。
像 add' 和 mult 这样一次接收一个参数的函数称为柯里化函数（curried functions）。除了本身很有意思之外，柯里化函数也比作用于元组的函数更灵活，因为通常可以通过用少于完整参数数量的参数部分应用一个柯里化函数，来构造有用的新函数。例如，给柯里化函数 add' 提供它两个参数中的一个，就可以得到一个递增整数的函数：add' 1 :: Int -> Int。
为了在使用柯里化函数时避免过多圆括号，Haskell 采用两个简单约定。首先，类型中的函数箭头 -> 默认向右结合。例如，类型：
Int -> Int -> Int -> Int
表示：
Int -> (Int -> (Int -> Int))
因此，用空格隐式表示的函数应用默认向左结合。例如，应用：
mult x y z
表示：
((mult x) y) z
除非明确需要元组化，在 Haskell 中所有具有多个参数的函数通常都定义为柯里化函数，并使用上面两个约定来减少所需圆括号数量。在第 4 章中，我们会看到如何用 lambda 表达式这个概念，以简单方式形式化柯里化函数定义的含义。
3.7 多态类型（Polymorphic types）
库函数 length 可以计算任意列表的长度，而不关心列表元素的类型。例如，它可以用于计算整数列表、字符串列表，甚至函数列表的长度：
> length [1,3,5,7]
4
> length ["Yes","No"]
2
> length [sin,cos,tan]
3
“length 可以应用到元素具有任意类型的列表”这个思想，通过在它的类型中包含**类型变量（type variable）**来精确表达。类型变量必须以小写字母开头，通常简单命名为 a、b、c 等等。例如，length 的类型如下：
length :: [a] -> Int
也就是说，对于任意类型 a，函数 length 都具有类型 [a] -> Int。包含一个或多个类型变量的类型称为**多态（polymorphic，“多种形式”）**类型，具有这种类型的表达式也称为多态表达式。因此，[a] -> Int 是一个多态类型，而 length 是一个多态函数。更一般地，标准 Prelude 中提供的许多函数都是多态的。例如：
fst :: (a,b) -> a
head :: [a] -> a
take :: Int -> [a] -> [a]
zip :: [a] -> [b] -> [(a,b)]
id :: a -> a
多态函数的类型通常会强烈暗示该函数的行为。例如，从类型 [a] -> [b] -> [(a,b)] 可以推断出，zip 会把两个列表中的元素配对起来，尽管仅凭类型本身并不能捕捉它究竟以什么精确方式完成这件事。
3.8 重载类型（Overloaded types）
算术操作符 + 可以计算任意两个相同数字类型的数字之和。例如，它可以用于计算两个整数之和，也可以用于计算两个浮点数之和：
> 1 + 2
3
> 1.0 + 2.0
3.0
“+ 可以应用到任意数字类型的数字”这个思想，通过在它的类型中包含**类约束（class constraint）**来精确表达。类约束写成 C a 的形式，其中 C 是类名，a 是类型变量。例如，加法操作符 + 的类型如下：
(+) :: Num a => a -> a -> a
也就是说，对于任何作为数字类型类 Num 的实例的类型 a，函数 (+) 都具有类型 a -> a -> a。（把一个操作符放在圆括号中会把它转换为柯里化函数，我们将在第 4 章看到这一点。）
包含一个或多个类约束的类型称为**重载（overloaded）**类型，具有这种类型的表达式也称为重载表达式。因此，Num a => a -> a -> a 是一个重载类型，而 (+) 是一个重载函数。更一般地，Prelude 中提供的大多数数字函数都是重载的。例如：
(*) :: Num a => a -> a -> a
negate :: Num a => a -> a
abs :: Num a => a -> a
数字本身也是重载的。例如，3 :: Num a => a 表示：对于任何数字类型 a，值 3 都具有类型 a。通过这种方式，值 3 可以是整数、浮点数，或者更一般地说，是任何数字类型的值，具体取决于它被使用的上下文。
3.9 基本类（Basic classes）
回忆一下，类型是一组相关值的集合。在此基础上，类（class）是一组支持某些重载操作的类型的集合，这些重载操作称为方法（methods）。Haskell 提供了若干内置于语言的基本类，其中最常用的类如下。（更高级的内置类会在本书第 II 部分讨论。）
Eq：相等类型（equality types）
这个类包含其值可以使用下面两个方法进行相等和不等比较的类型：
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
所有基本类型 Bool、Char、String、Int、Integer、Float 和 Double 都是 Eq 类的实例；列表类型和元组类型也是如此，前提是它们的元素类型和分量类型也是实例。例如：
> False == False
True
> 'a' == 'b'
False
> "abc" == "abc"
True
> [1,2] == [1,2,3]
False
> ('a',False) == ('a',False)
True
注意，函数类型通常不是 Eq 类的实例，因为一般来说，比较两个函数是否相等并不可行。
Ord：有序类型（ordered types）
这个类包含那些作为相等类 Eq 的实例，并且其值还具有全序（线性序）的类型。因此，这些值可以使用下面六个方法进行比较和处理：
(<) :: a -> a -> Bool
(<=) :: a -> a -> Bool
(>) :: a -> a -> Bool
(>=) :: a -> a -> Bool
min :: a -> a -> a
max :: a -> a -> a
所有基本类型 Bool、Char、String、Int、Integer、Float 和 Double 都是 Ord 类的实例；列表类型和元组类型也是如此，前提是它们的元素类型和分量类型也是实例。例如：
> False < True
True
> min 'a' 'b'
'a'
> "elegant" < "elephant"
True
> [1,2,3] < [1,2]
False
> ('a',2) < ('b',1)
True
> ('a',2) < ('a',1)
False
注意，字符串、列表和元组都按字典序（lexicographically）排序，也就是与字典中单词排序相同的方式。例如，两个相同类型的二元组，如果它们的第一分量有序，那么它们整体就有序，此时第二分量不会再被考虑；如果它们的第一分量相等，那么第二分量必须有序。
Show：可显示类型（showable types）
这个类包含其值可以使用下面方法转换为字符串的类型：
show :: a -> String
所有基本类型 Bool、Char、String、Int、Integer、Float 和 Double 都是 Show 类的实例；列表类型和元组类型也是如此，前提是它们的元素类型和分量类型也是实例。例如：
> show False
"False"
> show 'a'
"'a'"
> show 123
"123"
> show [1,2,3]
"[1,2,3]"
> show ('a',False)
"('a',False)"
Read：可读取类型（readable types）
这个类与 Show 对偶，包含其值可以使用下面方法从字符串转换而来的类型：
read :: String -> a
所有基本类型 Bool、Char、String、Int、Integer、Float 和 Double 都是 Read 类的实例；列表类型和元组类型也是如此，前提是它们的元素类型和分量类型也是实例。例如：
> read "False" :: Bool
False
> read "'a'" :: Char
'a'
> read "123" :: Int
123
> read "[1,2,3]" :: [Int]
[1,2,3]
> read "('a',False)" :: (Char,Bool)
('a',False)
这些例子中使用 :: 是为了确定结果类型；否则 GHCi 无法推断出结果类型。不过在实践中，所需类型信息通常可以从上下文自动推断出来。例如，表达式 not (read "False") 不需要显式类型信息，因为逻辑取反函数 not 的应用说明 read "False" 必须具有类型 Bool。
注意，如果 read 的参数在语法上无效，那么 read 的结果没有定义。例如，表达式 not (read "abc") 在求值时会产生错误，因为 "abc" 不能被读取为逻辑值：
> not (read "abc")
*** Exception: Prelude.read: no parse
Num：数字类型（numeric types）
这个类包含其值为数字的类型，因此可以使用下面六个方法处理：
(+) :: a -> a -> a
(-) :: a -> a -> a
(*) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
（方法 negate 返回一个数字的相反数，abs 返回绝对值，而 signum 返回符号。）基本类型 Int、Integer、Float 和 Double 是 Num 类的实例。例如：
> 1 + 2
3
> 1.0 + 2.0
3.0
> negate 3.0
-3.0
> abs (-3)
3
> signum (-3)
-1
如上所示，当负数作为函数参数使用时，必须写在圆括号中，以确保减号得到正确解释。例如，没有圆括号的 abs -3 表示 abs - 3，这既不是这里想表达的含义，也是一个类型不正确的表达式。
注意，Num 类不提供除法方法。不过正如下面所见，除法会通过两个特殊类分别处理：一个用于整数，另一个用于分数。
Integral：整数类型（integral types）
这个类包含那些作为数字类 Num 的实例，并且其值为整数的类型，因此支持整数除法和整数余数这两个方法：
div :: a -> a -> a
mod :: a -> a -> a
在实践中，这两个方法经常通过把名字写在一对反引号中，放在两个参数之间来使用。基本类型 Int 和 Integer 是 Integral 类的实例。例如：
> 7 `div` 2
3
> 7 `mod` 2
1
出于效率原因，许多同时涉及列表和整数的 Prelude 函数（例如 take 和 drop）被限制为使用有限精度整数类型 Int，而不是适用于 Integral 类的任意实例。不过，如果需要，这些函数的泛化版本可以在名为 Data.List 的附加库文件中找到。
Fractional：分数类型（fractional types）
这个类包含那些作为数字类 Num 的实例，并且其值不是整数的类型，因此支持分数除法和倒数这两个方法：
(/) :: a -> a -> a
recip :: a -> a
基本类型 Float 和 Double 是实例。例如：
> 7.0 / 2.0
3.5
> recip 2.0
0.5
3.10 章注（Chapter remarks）
逻辑值类型名 Bool 是为了纪念 George Boole 在符号逻辑方面的开创性工作；而“一次接收一个参数”的函数之所以称为 curried，是为了纪念 Haskell Curry 在这类函数方面的工作，Haskell 语言本身也以他的名字命名。多态函数的类型与其行为之间的关系在参考文献 [3] 中被形式化。关于类型系统的更详细说明可参见 Haskell Report [4]，类型系统的形式化描述可参见 [5]。
3.11 练习（Exercises）
- 下面这些值的类型是什么？
['a','b','c']
('a','b','c')
[(False,'O'),(True,'1')]
([False,True],['0','1'])
[tail, init, reverse]
- 写出具有下面类型的定义；只要类型正确，定义具体做什么并不重要。
bools :: [Bool]
nums :: [[Int]]
add :: Int -> Int -> Int -> Int
copy :: a -> (a,a)
apply :: (a -> b) -> a -> b
- 下面这些函数的类型是什么？
second xs = head (tail xs)
swap (x,y) = (y,x)
pair x y = (x,y)
double x = x*2
palindrome xs = reverse xs == xs
twice f x = f (f x)
提示：如果函数使用了重载操作符，请注意在类型中包含必要的类约束。
- 使用 GHCi 检查你对前三个问题的答案。
- 为什么一般来说，让函数类型成为
Eq类的实例并不可行？什么时候是可行的？提示：两个相同类型的函数相等，当且仅当它们对相等参数总是返回相等结果。
练习 1 和 2 的解答见附录 A。