数据类型与函数

Haskell 类型系统特性

类型签名

一个类型签名将一个名称与一个类型绑定在一起，例如上一章最末定义的add函数：

Prelude>:type add
add :: (Int, Int) -> Int

强类型

Haskell具有强类型系统，具体体现在该类型系统会拒绝任何无意义的表达式，也不会自动地将值从一个类型转换为另一个类型。在Haskell中遵守类型规则的表达式被称为“良类型的”(well-typed)。

强类型的好处在于可以在代码真正引发问题之前捕获错误[1]。

静态类型

静态类型指类型系统可以在编译的时候清楚每个值和表达式的类型，与之相对的是动态类型，其在运行时确定类型。

Haskell对强类型和静态类型的支持使得程序不可能发生运行时的错误，但作为代价，需要更多的努力来满足这些特性对程序代码的苛刻要求[1]。

类型推导

Haskell编译器可以自动推断出程序中近乎所有表达式的类型（偶尔需要人为提供额外的信息），这个过程被称为类型推导[1]。

纯度

如果一个函数在引用上是透明的，即不依赖于其参数以外的任何事物，则称其为纯函数或者无副作用的。纯函数对应于数学意义上的函数，在任何时间上使用相同的参数将导致相同的结果 [2] 。与之相对的是非纯函数或者有副作用的函数，例如含有输入输出的函数。

常用数据类型

Haskell中内置了许多基础且有用的类型，下面给出了部分常用的数据类型。

布尔类型（Bool）

布尔类型是一个只有True和False两个值的数据类型，Haskell为布尔类型提供了与&&,或||,非not三种逻辑运算。

Prelude> :type True 
True :: Bool 
Prelude> True || False 
True 
Prelude> True && False 
False
Prelude> not False
True

字符类型（Char）

字符类型是有单引号包裹的字符的类型，字符类型支持ASCII码中的所有字符，对于键盘上没有的字符可以使用反斜杠加数字表示。

Prelude> :type 'a'
'a' :: Char
Prelude> '\100' -- 十进制表示
'd'
Prelude> '\o144' -- 八进制表示
'd'
Prelude> '\x64' -- 十六进制表示
'd'

部分特殊的ASCII码需要用反斜杠转义表达，常用的转义字符有:


\b	退格符
\n	换行符
\t	制表符
\&	空格符
\	反斜杠
\"	双引号
\'	单引号

除ASCII码外，Haskell也支持汉字或其他语言的字符，GHCi会返回相应的Unicode码。

Prelude> '你'
'\20329'

有符号整型（Int）

对于64位系统，有符号整型值的范围为\( -2^{63} \sim 2^{63} - 1 \)。

Prelude> 2 ^ 63 - 1 :: Int
9223372036854775807
Prelude> 2 ^ 63 :: Int
-9223372036854775808
Prelude> 2 ^ 64 :: Int 
0

可以看到当声明的Int类型值超出范围后，得到的取值是错误的。

无符号整型（Word）

对于64位系统，无符号整型值的范围为\( 0 \sim 2^{64} - 1 \)。

Prelude> 2 ^ 64 - 1 :: Word
18446744073709551615
Prelude> 2 ^ 64 :: Word
18446744073709551616
Prelude> 2 ^ 65 :: Word 
0

当声明的Word类型超出范围后，也会得到错误的值。

任意精度整数类型（Integer）

与Int不同，任意精度整数类型理论上可以表示任意大小的整数，在实际的计算机上，只有内存是限制其范围的因素。

Prelude> 2 ^ 100
1267650600228229401496703205376
Prelude> 2 ^ 1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

浮点数类型（Float,Double）

Haskell中有单精度浮点数类型和双精度浮点数类型，这与其他语言无大差异。

有理数类型（Rational）

有理数类型是由两个任意精度的整数表示的（根据定义，有理数可以表示为两个整数相除）。

Prelude> 1/3 :: Rational
1 % 3 
Prelude> 3.14 :: Rational
157 % 50

元组（Tuple）

元组是具有固定大小的一组值的集合，每个值允许有不同的类型。

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分别用于提取二元组的两个元素。

Prelude> fst (1,'a')
1
Prelude> snd (1,'a')
'a'

列表（List）

列表是Haskell中非常常见的数据类型，可以容纳若干相同类型的数据。

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]的别名。

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类型的值组成

我们定义一个平面图形类型，包含了若干类别（如圆形，长方形，三角形等）。一个圆形可以由半径确定；一个长方形可以由长和宽确定；一个三角形需要给出三条边的长度才能确定。因此我们给出的定义如下：

-- 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]。

尝试构造一些值：

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]。

-- code1.hs
-- 圆形直径
type Diameter = Double
-- 长方形长宽
type Length = Double
type Width = Double
-- 三角形三条边长
type Side1 = Double
type Side2 = Double
type Side3 = Double

这样我们就可以定义一个新的Figure'类型，新的定义为我们提供更多的信息。

-- code1.hs
data Figure' = 
  Circle' Diameter
  | Rectangle' Length Width
  | Triangle' Side1 Side2 Side3
  deriving (Show)

记录语法

通过Figure和Figure'类型定义，我们可以很容易地构造一个值，相反地，我们还希望能够从这个值里解构想要的成分。使用 记录语法(Record Syntax) ，定义中每个 域(field) 都绑定了相应解构的函数。

-- code1.hs
data Figure'' = 
  Circle'' { getDiameter :: Diameter}
  | Rectangle'' { getLength :: Length, getWidth :: Width}
  | Triangle'' {
    getSide1 :: Side1,
    getSide2 :: Side2,
    getSide3 :: Side3
  } deriving (Show)

尝试验证这一点：

Prelude> getLength (Rectangle'' 3 4) 
3.0
Prelude> getSide1 Triangle'' { getSide1 = 3 , getSide2 = 4 , getSide3 = 5}
3.0

新类型

新类型(Newtype) newtype的创建方法与data声明类型的方法大致相同，但比较受限，只有当类型由一个构造函数且只有一个字段时，才可以使用newtype。

-- code1.hs
newtype NewInt = NewInt Int 
newtype NewInt' = NewInt' { getInt :: Int }

看起来newtype并不如data好用，但对于编译器来说却有帮助，newtype的限制实际上意味着新类型与原类型是同构的，这样在编译时检查类型后，在运行时这两个类型被视为相同的[5]。

定义递归类型

Haskell允许以递归地形式定义数据类型，一个最典型的例子就是自然数的定义：

-- code1.hs
data Nat = Zero | Succ Nat deriving (Show)

一个自然数要么为零，要么为另一个自然数的后继，对于后者，定义中调用了类型本身。

通过上述递归定义，我们就可以构造自然数了：

Prelude> Zero -- 0
Zero
Prelude> Succ (Succ Nat) -- 2
Succ (Succ Nat) 

变量，函数与柯里化

变量？

在Haskell中，变量有两种指代，一种是函数中的形参，另一种则是主流编程语言中所指的变量。对于后者，Haskell中的变量徒有其名（不如称其为常量），因为一旦给定变量以值（如x = 2），该变量就不会在运行时改变[6]。

函数与柯里化

Haskell中的函数非常贴近数学意义上的函数，它将一个（或者一组）类型的值映射到另一个（或者一组）类型的值。

补充：关于一组类型的映射需要用到类型类，将在后面讲解，这里可以认为由一个类型到另一个类型的映射

在前面已经给过一个函数的例子–整数加法：

-- code1.hs
add :: (Int, Int) -> Int
add (a,b) = a + b 

然而在Haskell中这样的函数并不常见，通常我们使用 柯里化(Currying) 的函数。柯里化是将一个函数转化为另一个函数的过程，具体为将参数元组拆分，形成新的函数，该函数可以依次接受对应于原函数元组对应位置的参数[7]，也就是说每次接受一个参数。

整数加法的函数柯里化后：

-- code1.hs
add' :: Int -> Int -> Int 
add' a b = a + b

柯里化后的函数使用起来更加方便，因为这使得 部分应用(Partial Application) 变得轻而易举，例如：

-- code1.hs
addone :: Int -> Int
addone = add' 1
-- addone = add' 1 ? = 1 + ?

我们通过将add'函数应用到数字1上，得到了一个新的函数（新的函数称为部分函数或者偏函数），这个函数对参数增加一。

另外，不难发现，柯里化的函数类型中箭头是右结合的，即add'函数的类型是Int -> (Int -> Int)。

匿名函数

匿名函数(Anonymous function) 是一个不带有名字的函数，在某些情况下我们使用匿名函数更为方便（我们将在后续章节中大量使用匿名函数）。

匿名函数是一个 \( \lambda \)抽象(Lambda Abstraction) [8]，书写模式类似\ 参数1 参数2 ... -> 表达式。

提示：读者可以查阅lambda演算资料了解更多

将上面的加法用匿名函数重写：

-- 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提供了一种将二元函数两边添加反单引号的方式，这将二元函数解析为中缀的。

Prelude> 1 `add'` 2
3

使用中缀表达可以提高程序的可读性，但有时为了方便，我们还会定义运算符。从原理上，运算符就是函数，但增加了一些规则–优先级(Precedence)、结合性(associativity)、位置(Fixity)。

在Haskell中，运算符优先级由\( 0 \sim 9 \)十个整数组成,结合性分为左结合性、右结合性、无结合性，位置分为前缀和中缀（这里着重讲中缀）。

我们定义一个运算符|+|用于计算加法：

-- code1.hs
(|+|) :: Int -> Int -> Int 
(|+|) x y = x + y

infixl 6 |+|

上述代码中，定义了加法是左结合的中缀运算符，优先级为6。

类似地，再定义一个运算符|*|用于计算乘法：

-- code1.hs
(|*|) :: Int -> Int -> Int 
x |*| y = x * y

infixl 7 |*|

乘法也是左结合的，但优先级为7，比加法结合地更紧密。

Prelude> 1 |+| 2
3
Prelude> 1 |*| 2
2
Prelude> 1 |+| 2 |*| 2
5

提示：前面讲到运算符实际上就是函数，因此它当然可以以前缀的方式使用，如(|+|) 1 2

节（Section）

对于中缀运算符，Haskell提供了一种构造部分函数的简洁方法– 节(Section) 。

考虑前面的“增一”函数，我们已经有了addone,adone'和addone''三个版本的写法，实际上使用节将比上述方法更简洁。

-- code1.hs
addone''' :: Int -> Int 
addone''' = (1+)

从本质上来说，节相当于给中缀运算符提供其中的一个参数，得到一个函数，该函数接受一个参数放到中缀运算符缺失的位置上[9]。

提示：实际上，节对具有中缀特性的表达都有效，比如1 `add'`也是一个合法的表达式。

多态

通俗来讲，多态性(PolyMorphism) 就是指类型中支持变量的特性。一般地，Haskell大多数多态都属于两类之一：参数多态性(Parametric PolyMorphism) 和 临时多态性(Ad-hoc PolyMorphism) [10]。这里主要讨论前者，而将后者放到类型类的部分讲解。

参数多态性中类型中的变量是任意类型，因此也就可以被任意实际的类型替代。我们将从类型多态性和函数多态性分别讲解参数多态性。

类型多态性

类型多态性，顾名思义就是类型中含有变量，在前面的讲解中，我们已经或多或少接触到了具有多态性的类型，一个非常熟悉的例子就是列表类型。

列表是Haskell的内置类型，我们通过GHCi输入:info []即可查看列表的定义。

data [] a = [] | a : [a]

这是一个递归定义的类型，它定义了两种情形：

[]: 空列表，列表中不包含任何元素
a : [a]: 非空列表，则必然表达为一个元素附加到另一个同类型列表的头部

这里面a就是一个类型变量，当我们用特定类型的值构造一个列表时，变量a就被赋予了所对应的类型。

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类型常常用于可能存在无意义输出的情形下，其定义如下：

data Maybe a = Nothing | Just a

Maybe类型包含两种情形，第一种是Nothing表示无意义，第二种是Just a表示有意义并包含了实际的结果。

给定两个整数，计算两个数整除的结果，就是一个典型应用Maybe类型的例子，当除数为0时，我们可以让其返回Nothing，而当除数非0时，使用Just包含得到的商。

-- 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函数接受任意类型的值，并返回值本身。

id :: a -> a 
id x = x

提示：实际上，“没什么意义”却有意义，在函数作为一等公民的语言中，身份函数就像0和1对其他语言一种重要

(.)函数是一个复合运算的运算符，可以将若干的函数复合起来，形成新的函数。

(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) x = f (g x)

infixr 9 .

不难发现，将复合运算作为一个二元运算，则id函数与任意函数的复合都是函数本身; 另外，复合运算对于函数还满足结合律，即f . g . h和(f . g) . h是相等的，这一点可以通过推导二者的类型得到。

惰性

惰性或者 惰性求值(Lazy Evaluation) 指的是当表达式绑定到变量时，不会立刻进行计算，而是会延迟直到其他计算需要时才会计算结果[11]。

在Haskell中，惰性求值是默认的，我们可以验证这一点：

示例1：

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：

Prelude> z = 1 : z
Prelude> head z
1

示例2定义了一个无限循环的列表[1,1,...],类似地，我们也可以借助惰性求值的特性获得列表的头部元素。

示例3：

Prelude> y = [1,2,undefined]
Prelude> head y
1

示例3中，y被赋予了含有未定义的元素，由于惰性求值的特性，赋值过程和head y并没有因为未定义的元素而产生错误。

由此可以看到惰性下的延迟计算带来了很多优点，这种语义允许人们绕过未定义的值或者处理无穷的数据[11]。

补充：然而惰性并不是完全没有代价的，因为不立即求值，所以必须要保留未计算的表达式，这也会导致内存的使用变得难以预测[11]

[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.