# 数据类型与函数
## Haskell 类型系统特性
### 类型签名
一个类型签名将一个名称与一个类型绑定在一起，例如上一章最末定义的`add`函数：
```bash
Prelude>:type add
add :: (Int, Int) -> Int
```
### 强类型
Haskell具有强类型系统，具体体现在该类型系统会拒绝任何无意义的表达式，也不会自动地将值从一个类型转换为另一个类型。在Haskell中遵守类型规则的表达式被称为“良类型的”(well-typed)。
强类型的好处在于可以在代码真正引发问题之前捕获错误[[1]](#ref1)。
### 静态类型
静态类型指类型系统可以在编译的时候清楚每个值和表达式的类型，与之相对的是动态类型，其在运行时确定类型。
Haskell对强类型和静态类型的支持使得程序不可能发生运行时的错误，但作为代价，需要更多的努力来满足这些特性对程序代码的苛刻要求[[1]](#ref1)。
### 类型推导
Haskell编译器可以自动推断出程序中近乎所有表达式的类型（偶尔需要人为提供额外的信息），这个过程被称为类型推导[[1]](#ref1)。
### 纯度
如果一个函数在引用上是透明的，即不依赖于其参数以外的任何事物，则称其为纯函数或者无副作用的。纯函数对应于数学意义上的函数，在任何时间上使用相同的参数将导致相同的结果 [[2]](#ref2) 。与之相对的是非纯函数或者有副作用的函数，例如含有输入输出的函数。
## 常用数据类型
Haskell中内置了许多基础且有用的类型，下面给出了部分常用的数据类型。
### 布尔类型（Bool）
布尔类型是一个只有`True`和`False`两个值的数据类型，Haskell为布尔类型提供了与`&&`,或`||`,非`not`三种逻辑运算。
```bash
Prelude> :type True
True :: Bool
Prelude> True || False
True
Prelude> True && False
False
Prelude> not False
True
```
### 字符类型（Char）
字符类型是有单引号包裹的字符的类型，字符类型支持ASCII码中的所有字符，对于键盘上没有的字符可以使用反斜杠加数字表示。
```bash
Prelude> :type 'a'
'a' :: Char
Prelude> '\100' -- 十进制表示
'd'
Prelude> '\o144' -- 八进制表示
'd'
Prelude> '\x64' -- 十六进制表示
'd'
```
部分特殊的ASCII码需要用反斜杠转义表达，常用的转义字符有:
| | |
| ---- | ---- |
| \b | 退格符 |
| \n | 换行符 |
| \t | 制表符 |
| \& | 空格符 |
| \\ | 反斜杠 |
| \" | 双引号 |
| \' | 单引号 |
除ASCII码外，Haskell也支持汉字或其他语言的字符，GHCi会返回相应的Unicode码。
```bash
Prelude> '你'
'\20329'
```
### 有符号整型（Int）
对于64位系统，有符号整型值的范围为`$ -2^{63} \sim 2^{63} - 1 $`。
```bash
Prelude> 2 ^ 63 - 1 :: Int
9223372036854775807
Prelude> 2 ^ 63 :: Int
-9223372036854775808
Prelude> 2 ^ 64 :: Int
0
```
可以看到当声明的`Int`类型值超出范围后，得到的取值是错误的。
### 无符号整型（Word）
对于64位系统，无符号整型值的范围为`$ 0 \sim 2^{64} - 1 $`。
```bash
Prelude> 2 ^ 64 - 1 :: Word
18446744073709551615
Prelude> 2 ^ 64 :: Word
18446744073709551616
Prelude> 2 ^ 65 :: Word
0
```
当声明的`Word`类型超出范围后，也会得到错误的值。
### 任意精度整数类型（Integer）
与Int不同，任意精度整数类型理论上可以表示任意大小的整数，在实际的计算机上，只有内存是限制其范围的因素。
```bash
Prelude> 2 ^ 100
1267650600228229401496703205376
Prelude> 2 ^ 1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
```
### 浮点数类型（Float,Double）
Haskell中有单精度浮点数类型和双精度浮点数类型，这与其他语言无大差异。
### 有理数类型（Rational）
有理数类型是由两个任意精度的整数表示的（根据定义，有理数可以表示为两个整数相除）。
```bash
Prelude> 1/3 :: Rational
1 % 3
Prelude> 3.14 :: Rational
157 % 50
```
### 元组（Tuple）
元组是具有固定大小的一组值的集合，每个值允许有不同的类型。
```bash
Prelude> :type (1,'a') :: (Int,Char)
(1,'a') :: (Int,Char) :: (Int, Char)
Prelude> :type (1,2,'c') :: (Int,Float,Char)
(1,2,'c') :: (Int,Float,Char) :: (Int, Float, Char)
```
Haskell还内置了两个函数`fst`和`snd`分别用于提取二元组的两个元素。
```bash
Prelude> fst (1,'a')
1
Prelude> snd (1,'a')
'a'
```
### 列表（List）
列表是Haskell中非常常见的数据类型，可以容纳若干相同类型的数据。
```bash
Prelude> :type []
[] :: [a]
Prelude> :type ['h','e','l','l','o']
['h','e','l','l','o'] :: [Char]
Prelude> :type [1..5] :: [Int]
[1..5] :: [Int] :: [Int]
```
> 好奇的读者可能发现最后一个表达式如果不添加显式声明的类型，其显式的类型签名是`[1..5] :: (Num a, Enum a) => [a]`，这涉及到类型类的知识，将在后续章节展开。
### 字符串类型 （String）
字符串类型是由若干字符组成，实际上字符串是一种特殊的列表，因此`String`和`[Char]`表述的是同一种类型，`String`只是`[Char]`的别名。
```bash
Prelude> ['h','e','l','l','o']
"hello"
Prelude>:type "hello"
"hello" :: String
```
## 定义数据类型
### 代数数据类型(Algebraic Data Type)
代数数据类型指由其他类型通过代数操作组合而成的类型，这里的代数操作指：
- 和（Sum）: 假设值`x`的类型为`A`类型与`B`类型的和`A | B`，则`x`的类型要么是`A`类型，要么是`B`类型，但不能同时为`A`和`B`类型
- 积（Product）:假设值`x`的类型为`A`类型与`B`类型的积`A B`,则`x`是由`A`类型的值和`B`类型的值组成
我们定义一个平面图形类型，包含了若干类别（如圆形，长方形，三角形等）。一个圆形可以由半径确定；一个长方形可以由长和宽确定；一个三角形需要给出三条边的长度才能确定。因此我们给出的定义如下：
```haskell
-- code1.hs
data Figure =
Circle Double
| Rectangle Double Double
| Triangle Double Double Double
deriving (Show)
```
根据代数数据类型的定义，我们可以看到，对于一个类型为`Figure`的值，它必然是圆形，长方形和三角形中之一，并由若干浮点数类型的积组成。
在上述的定义中，`Figure`作为类型，被称 ***类型构造器(Type Constructor)*** ; 而`Circle`,`Rectangle`,`Triangle`用于构造实际的值，被称为 ***数据构造器(Data Constructor)*** 或者 ***值构造器(Value Constructor)***[[3]](#ref3)。
尝试构造一些值：
```bash
Prelude> :load code1.hs
[1 of 2] Compiling Main ( code1.hs, interpreted )
Ok, one module loaded.
Prelude> Circle 1
Circle 1.0
Prelude> Rectangle 3 4
Rectangle 3.0 4.0
Prelude> :type (Triangle 3 4 5)
(Triangle 3 4 5) :: Figure
```
> 读者可能注意到在定义的末端使用了`deriving`派生语法，这里的作用是为了便于将值打印出来,读者可以尝试看看删去`deriving (Show)`后会发生什么
### 定义别名
有的时候，我们希望类型可以表达更多的信息。例如圆形中包含了类型为浮点数的直径，但从`Circle Double`中我们可能并不能非常直观地看出`Double`到底指的什么。类似地，长方形和三角形也造成了同样的疑惑。
基于此，我们构造类型的别名，也称 ***上下文别名(Context Alias)*** [[4]](#ref4)。
```haskell
-- code1.hs
-- 圆形直径
type Diameter = Double
-- 长方形长宽
type Length = Double
type Width = Double
-- 三角形三条边长
type Side1 = Double
type Side2 = Double
type Side3 = Double
```
这样我们就可以定义一个新的`Figure'`类型，新的定义为我们提供更多的信息。
```haskell
-- code1.hs
data Figure' =
Circle' Diameter
| Rectangle' Length Width
| Triangle' Side1 Side2 Side3
deriving (Show)
```
### 记录语法
通过`Figure`和`Figure'`类型定义，我们可以很容易地构造一个值，相反地，我们还希望能够从这个值里解构想要的成分。使用 ***记录语法(Record Syntax)*** ，定义中每个 ***域(field)*** 都绑定了相应解构的函数。
```haskell
-- code1.hs
data Figure'' =
Circle'' { getDiameter :: Diameter}
| Rectangle'' { getLength :: Length, getWidth :: Width}
| Triangle'' {
getSide1 :: Side1,
getSide2 :: Side2,
getSide3 :: Side3
} deriving (Show)
```
尝试验证这一点：
```bash
Prelude> getLength (Rectangle'' 3 4)
3.0
Prelude> getSide1 Triangle'' { getSide1 = 3 , getSide2 = 4 , getSide3 = 5}
3.0
```
### 新类型
***新类型(Newtype)*** `newtype`的创建方法与`data`声明类型的方法大致相同，但比较受限，只有当类型由一个构造函数且只有一个字段时，才可以使用`newtype`。
```haskell
-- code1.hs
newtype NewInt = NewInt Int
newtype NewInt' = NewInt' { getInt :: Int }
```
> 看起来`newtype`并不如`data`好用，但对于编译器来说却有帮助，`newtype`的限制实际上意味着新类型与原类型是同构的，这样在编译时检查类型后，在运行时这两个类型被视为相同的[[5]](#ref5)。
### 定义递归类型
Haskell允许以递归地形式定义数据类型，一个最典型的例子就是自然数的定义：
```haskell
-- code1.hs
data Nat = Zero | Succ Nat deriving (Show)
```
一个自然数要么为零，要么为另一个自然数的后继，对于后者，定义中调用了类型本身。
通过上述递归定义，我们就可以构造自然数了：
```bash
Prelude> Zero -- 0
Zero
Prelude> Succ (Succ Nat) -- 2
Succ (Succ Nat)
```
## 变量，函数与柯里化
### 变量？
在Haskell中，变量有两种指代，一种是函数中的形参，另一种则是主流编程语言中所指的变量。对于后者，Haskell中的变量徒有其名（不如称其为常量），因为一旦给定变量以值（如`x = 2`），该变量就不会在运行时改变[[6]](#ref6)。
### 函数与柯里化
Haskell中的函数非常贴近数学意义上的函数，它将一个（或者一组）类型的值映射到另一个（或者一组）类型的值。
> 补充：关于一组类型的映射需要用到类型类，将在后面讲解，这里可以认为由一个类型到另一个类型的映射
在前面已经给过一个函数的例子--整数加法：
```haskell
-- code1.hs
add :: (Int, Int) -> Int
add (a,b) = a + b
```
然而在Haskell中这样的函数并不常见，通常我们使用 ***柯里化(Currying)*** 的函数。柯里化是将一个函数转化为另一个函数的过程，具体为将参数元组拆分，形成新的函数，该函数可以依次接受对应于原函数元组对应位置的参数[[7]](#ref7)，也就是说每次接受一个参数。
整数加法的函数柯里化后：
```haskell
-- code1.hs
add' :: Int -> Int -> Int
add' a b = a + b
```
柯里化后的函数使用起来更加方便，因为这使得 ***部分应用(Partial Application)*** 变得轻而易举，例如：
```haskell
-- code1.hs
addone :: Int -> Int
addone = add' 1
-- addone = add' 1 ? = 1 + ?
```
我们通过将`add'`函数应用到数字1上，得到了一个新的函数（新的函数称为部分函数或者偏函数），这个函数对参数增加一。
另外，不难发现，柯里化的函数类型中箭头是右结合的，即`add'`函数的类型是`Int -> (Int -> Int)`。
## 匿名函数
***匿名函数(Anonymous function)*** 是一个不带有名字的函数，在某些情况下我们使用匿名函数更为方便（我们将在后续章节中大量使用匿名函数）。
匿名函数是一个 ***`$ \lambda $`抽象(Lambda Abstraction)*** [[8]](#ref8)，书写模式类似`\ 参数1 参数2 ... -> 表达式`。
> 提示： 读者可以查阅lambda演算资料了解更多
将上面的加法用匿名函数重写：
```haskell
-- code1.hs
add' :: Int -> Int -> Int
add' = \ x y -> x + y
addone' :: Int -> Int
addone' = (\x y -> x + y) 1
-- 等同于
addone'' :: Int -> Int
addone'' = \y -> 1 + y
```
## 运算符
虽然我们很容易地定义了加法，但这与我们在平时使用的加法符号还有些差距。首先，它不是中缀的；其次它是由字母组成的而非符号。
对于前者，Haskell提供了一种将二元函数两边添加反单引号的方式，这将二元函数解析为中缀的。
```bash
Prelude> 1 `add'` 2
3
```
使用中缀表达可以提高程序的可读性，但有时为了方便，我们还会定义运算符。从原理上，运算符就是函数，但增加了一些规则--优先级(Precedence)、结合性(associativity)、位置(Fixity)。
在Haskell中，运算符优先级由`$ 0 \sim 9 $`十个整数组成,结合性分为左结合性、右结合性、无结合性，位置分为前缀和中缀（这里着重讲中缀）。
我们定义一个运算符`|+|`用于计算加法：
```haskell
-- code1.hs
(|+|) :: Int -> Int -> Int
(|+|) x y = x + y
infixl 6 |+|
```
上述代码中，定义了加法是左结合的中缀运算符，优先级为6。
类似地，再定义一个运算符`|*|`用于计算乘法：
```haskell
-- code1.hs
(|*|) :: Int -> Int -> Int
x |*| y = x * y
infixl 7 |*|
```
乘法也是左结合的，但优先级为7，比加法结合地更紧密。
```bash
Prelude> 1 |+| 2
3
Prelude> 1 |*| 2
2
Prelude> 1 |+| 2 |*| 2
5
```
>提示：前面讲到运算符实际上就是函数，因此它当然可以以前缀的方式使用，如`(|+|) 1 2`
### 节（Section）
对于中缀运算符，Haskell提供了一种构造部分函数的简洁方法-- ***节(Section)*** 。
考虑前面的“增一”函数，我们已经有了`addone`,`adone'`和`addone''`三个版本的写法，实际上使用节将比上述方法更简洁。
```haskell
-- code1.hs
addone''' :: Int -> Int
addone''' = (1+)
```
从本质上来说，节相当于给中缀运算符提供其中的一个参数，得到一个函数，该函数接受一个参数放到中缀运算符缺失的位置上[[9]](#ref9)。
> 提示：实际上，节对具有中缀特性的表达都有效，比如`` 1 `add'` ``也是一个合法的表达式。
## 多态
通俗来讲，***多态性(PolyMorphism)*** 就是指类型中支持变量的特性。一般地，Haskell大多数多态都属于两类之一：***参数多态性(Parametric PolyMorphism)*** 和 ***临时多态性(Ad-hoc PolyMorphism)*** [[10]](#ref10)。这里主要讨论前者，而将后者放到类型类的部分讲解。
参数多态性中类型中的变量是任意类型，因此也就可以被任意实际的类型替代。我们将从类型多态性和函数多态性分别讲解参数多态性。
### 类型多态性
类型多态性，顾名思义就是类型中含有变量，在前面的讲解中，我们已经或多或少接触到了具有多态性的类型，一个非常熟悉的例子就是列表类型。
列表是Haskell的内置类型，我们通过GHCi输入`:info []`即可查看列表的定义。
```haskell
data [] a = [] | a : [a]
```
这是一个递归定义的类型，它定义了两种情形：
- `[]`: 空列表，列表中不包含任何元素
- `a : [a]`: 非空列表，则必然表达为一个元素附加到另一个同类型列表的头部
这里面`a`就是一个类型变量，当我们用特定类型的值构造一个列表时，变量`a`就被赋予了所对应的类型。
```bash
Prelude> :type []
[] :: [a]
Prelude> :type ['a','b','c']
['a','b','c'] :: [Char]
Prelude> :type [1,2,3] :: [Int]
[1,2,3] :: [Int] :: [Int]
```
> 提示：
> 1.根据定义，我们当然可以使用值构造器构造想要的列表（比如`1:2:3:[]`），这在Haskell中是理所当然的，而使用`[1,2,3]`的写法则是内置的 ***语法糖(syntactic sugar)***
> 2.在列表的定义中，`:`作为值构造器实际上还是运算符，在GHCi中使用`:info (:)`命令可以看到`infixr 5 :`，也就是说这个构造器是右结合的中缀运算符，这也解释了为什么`1:2:3:[]`不用使用括号来避免歧义
> 补充：看起来值构造器`:`就像一个函数，在GHCi中也可以查看到它的类型为`a -> [a] -> [a]`，但实际上两者还是有差异的，具体表现在函数无法进行模式匹配上（后面章节会讲解）
另一个内置且常用的多态类型是`Maybe`类型，`Maybe`类型常常用于可能存在无意义输出的情形下，其定义如下：
```haskell
data Maybe a = Nothing | Just a
```
`Maybe`类型包含两种情形，第一种是`Nothing`表示无意义，第二种是`Just a`表示有意义并包含了实际的结果。
给定两个整数，计算两个数整除的结果，就是一个典型应用`Maybe`类型的例子，当除数为0时，我们可以让其返回`Nothing`，而当除数非0时，使用`Just`包含得到的商。
```haskell
-- code1.hs
divide :: Int -> Int -> Maybe Int
divide a b = if b == 0 then Nothing else Just (a `div` b)
```
> 提示： 这里使用了`if-then-else`表达式，在下一章“表达式”将会着重讲解。
### 函数多态性
函数多态性，即函数的类型中含有变量，这些变量可以被实际的任意类型替代。这里我们以`id`和`(.)`两个基础的函数作为例子。
`id`函数称为身份函数或单位映射，这个函数非常简单但是看起来“没什么意义”。`id`函数接受任意类型的值，并返回值本身。
```haskell
id :: a -> a
id x = x
```
> 提示：实际上，“没什么意义”却有意义，在函数作为一等公民的语言中，身份函数就像0和1对其他语言一种重要
`(.)`函数是一个复合运算的运算符，可以将若干的函数复合起来，形成新的函数。
```haskell
(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)
infixr 9 .
```
不难发现，将复合运算作为一个二元运算，则`id`函数与任意函数的复合都是函数本身; 另外，复合运算对于函数还满足结合律，即`f . g . h`和`(f . g) . h`是相等的，这一点可以通过推导二者的类型得到。
## 惰性
惰性或者 ***惰性求值(Lazy Evaluation)*** 指的是当表达式绑定到变量时， 不会立刻进行计算，而是会延迟直到其他计算需要时才会计算结果[[11]](#ref11)。
在Haskell中，惰性求值是默认的，我们可以验证这一点：
- 示例1：
```bash
Prelude> x = [1..]
Prelude> head x
1
```
我们可以给变量`x`赋值一个无穷列表`[1..]`,这是一个自然数数列`{1,2,...}`，对于严格求值的语言来说，这是不可能实现的，因为无穷的自然数将会耗尽计算机的存储资源进而宕机；然而对于Haskell来说，计算无穷列表并不是必要的，因此赋值过程并没有对无穷列表求值，可以非常顺利地进行；接下来我们使用`head`函数获取`x`中的第一个元素，`head`函数首先会分析`x`为非空列表，根据定义必然可以表示为`1 : [2..]`，而`1`即为所求，直接返回`1`即可，`[2..]`因为无需计算而没有被求值。
> 补充：`[1..]` 也是一种语法糖，称为列表推导式，其他的例子如`[0.5..3.5]`表示`[0.5,1.5,2.5,3.5]`,另外也可以用字符作为元素如`['a'..'c']`表示`"abc"`。
- 示例2：
```bash
Prelude> z = 1 : z
Prelude> head z
1
```
示例2定义了一个无限循环的列表`[1,1,...]`,类似地，我们也可以借助惰性求值的特性获得列表的头部元素。
- 示例3：
```bash
Prelude> y = [1,2,undefined]
Prelude> head y
1
```
示例3中，`y`被赋予了含有未定义的元素，由于惰性求值的特性，赋值过程和`head y`并没有因为未定义的元素而产生错误。
由此可以看到惰性下的延迟计算带来了很多优点，这种语义允许人们绕过未定义的值或者处理无穷的数据[[11]](#ref11)。
> 补充：然而惰性并不是完全没有代价的，因为不立即求值，所以必须要保留未计算的表达式，这也会导致内存的使用变得难以预测[[11]](#ref11)
-------------------------------
[1] O’Sullivan, B., Goerzen, J., & Stewart, D. (2008). Real World Haskell (1st ed.). O’Reilly Media, Inc.
[2] Pure. (2021, November 5). HaskellWiki, . Retrieved 11:54, March 8, 2024 from https://wiki.haskell.org/index.php?title=Pure&oldid=64830.
[3] Algebraic data type. (2023, May 22). HaskellWiki, . Retrieved 11:12, March 10, 2024 from https://wiki.haskell.org/index.php?title=Algebraic_data_type&oldid=65617.
[4] Context alias. (2021, July 24). HaskellWiki, . Retrieved 11:31, March 10, 2024 from https://wiki.haskell.org/index.php?title=Context_alias&oldid=64617.
[5] Newtype. (2016, May 22). HaskellWiki, . Retrieved 12:55, March 10, 2024 from https://wiki.haskell.org/index.php?title=Newtype&oldid=60788.
[6] Variable. (2006, October 11). HaskellWiki, . Retrieved 14:05, March 10, 2024 from https://wiki.haskell.org/index.php?title=Variable&oldid=6880.
[7] Currying. (2023, November 3). HaskellWiki, . Retrieved 14:53, March 10, 2024 from https://wiki.haskell.org/index.php?title=Currying&oldid=66401.
[8] Anonymous function. (2021, April 12). HaskellWiki, . Retrieved 02:09, March 11, 2024 from https://wiki.haskell.org/index.php?title=Anonymous_function&oldid=64188.
[9] Section of an infix operator. (2017, March 31). HaskellWiki, . Retrieved 03:54, March 11, 2024 from https://wiki.haskell.org/index.php?title=Section_of_an_infix_operator&oldid=61678.
[10] Polymorphism. (2015, January 21). HaskellWiki, . Retrieved 08:40, March 11, 2024 from https://wiki.haskell.org/index.php?title=Polymorphism&oldid=59216.
[11] Lazy evaluation. (2021, February 6). HaskellWiki, . Retrieved 13:33, March 11, 2024 from https://wiki.haskell.org/index.php?title=Lazy_evaluation&oldid=63958.