另一个 Haskell 教程/类型基础

Haskell 使用一个 _静态类型检查_ 系统。这意味着每个 Haskell 表达式都被分配一个 _类型_。例如 'a' 的类型是 Char，表示“字符”。然后，如果你有一个函数，它期望一个特定类型的参数，而你给它错误的类型，就会在编译时生成错误（也就是说，你无法编译程序）。这大大减少了可能潜入你程序的错误数量。

此外，Haskell 使用一个 _类型推断_ 系统。这意味着你甚至不需要指定表达式的类型。相比之下，在 C 中，当你定义一个变量时，你需要指定它的类型（例如，int、char 等）。在 Haskell 中，你不需要这样做——类型将从上下文中推断出来。

注意

如果你想，你当然可以显式地指定表达式的类型；这通常有助于调试。实际上，显式地指定最外层函数的类型有时被认为是一种好的风格。

Hugs 和 GHCi 都允许你对表达式应用类型推断以找到它的类型。这是通过使用 :t 命令完成的。例如，启动你最喜欢的 shell 并尝试以下操作

示例

Prelude> :t 'c'
'c' :: Char

这告诉我们表达式 'c' 的类型是 Char（双冒号 :: 在整个 Haskell 中用于指定类型）。

简单类型

有许多内置类型，包括 Int（用于整数，包括正数和负数）、Double（用于浮点数）、Char（用于单个字符）、String（用于字符串）等等。我们已经看到过一个 Char 类型的表达式；让我们检查一个 String 类型的表达式

示例

Prelude> :t "Hello"
"Hello" :: String

你也可以输入更复杂的表达式，例如，一个相等性测试

示例

Prelude> :t 'a' == 'b'
'a' == 'b' :: Bool

你应该注意，即使这个表达式是假的，它仍然有一个类型，即 Bool 类型。

注意

Bool 是 Boolean（发音为“boo-lee-uhn”）的缩写，它有两个可能的值：True 和 False。

你可以通过尝试让 shell 为你提供一个类型错误表达式的类型来观察类型检查和类型推断的过程。例如，相等运算符要求其两个参数的类型相同。我们可以通过尝试将一个字符与一个字符串进行比较来看到 Char 和 String 是不同类型

示例

Prelude> :t 'a' == "a"
ERROR - Type error in application
*** Expression     : 'a' == "a"
*** Term           : 'a'
*** Type           : Char
*** Does not match : [Char]

错误的第一行（包含“Expression”的行）告诉我们发生类型错误的表达式。第二行告诉我们这个表达式中的哪一部分类型错误。第三行告诉我们该项的推断类型，第四行告诉我们需要匹配的内容。在这种情况下，它说类型 Char 与类型 [Char] 不匹配（字符列表——Haskell 中的字符串表示为字符列表）。

如前所述，你可以使用::运算符显式地指定表达式的类型。例如，在前面的示例中，我们可以使用 ("a"::String) 而不是 "a"。在这种情况下，这没有任何影响，因为 "a" 只有一个可能的解释。但是，请考虑数字的情况。你可以尝试

示例

Prelude> :t 5 :: Int
5 :: Int
Prelude> :t 5 :: Double
5 :: Double

在这里，我们可以看到数字 5 可以实例化为 Int 或 Double。如果我们不指定类型呢？

示例

Prelude> :t 5
5 :: Num a => a

不是你预期的那样？这意味着，简而言之，如果某个类型 a 是 Num 类的 _实例_，那么表达式 5 的类型可以是 a 类型。如果这没有意义，现在不用担心。在第 类 节中，我们将详细讨论类型类（这就是它）。然而，阅读它的方式是说“a 是 Num 的实例意味着 a”。

练习
自己找出，然后验证以下表达式的类型，如果它们有类型。还要注意表达式是否为类型错误 'h':'e':'l':'l':'o':[] [5,'a'] (5,'a') (5::Int) + 10 (5::Int) + (10::Double)

多态类型

Haskell 采用多态类型系统。这本质上意味着你可以拥有 _类型变量_，我们之前已经提到过。例如，请注意，像 tail 这样的函数并不关心列表中的元素是什么

示例

Prelude> tail [5,6,7,8,9]
[6,7,8,9]
Prelude> tail "hello"
"ello"
Prelude> tail ["the","man","is","happy"]
["man","is","happy"]

这是可能的，因为 tail 具有多态类型：[$\alpha$] -> [$\alpha$]。这意味着它可以接受 _任何_ 列表作为参数并返回一个相同类型的列表。

相同的分析可以解释 fst 的类型

示例

Prelude> :t fst
fst :: (a,b) -> a

在这里，GHCi 明确了类型值的 _泛化_。也就是说，它表示对于所有类型 a 和 b，fst 是从 (a,b) 到 a 的函数。

练习
自己找出，然后验证以下表达式的类型，如果它们有类型。还要注意表达式是否为类型错误 snd head null head . tail head . head

类型类

上一节我们看到了一些与数字5相关的奇怪类型。在我们深入研究类型类主题之前，让我们先退一步看看其中的动机。

动机

在许多语言（C++、Java 等）中，存在一种重载系统。也就是说，可以编写一个函数，它可以接受不同类型的参数。例如，最典型的例子是相等性函数。如果我们想要比较两个整数，我们应该使用整数比较；如果我们想要比较两个浮点数，我们应该使用浮点数比较；如果我们想要比较两个字符，我们应该使用字符比较。一般来说，如果我们想要比较两个具有类型 $\alpha$ 的事物，我们想要使用 $\alpha -compare$ 。我们称 $\alpha$ 为一个 *类型变量*，因为它是一个值是类型的变量。

注意

一般来说，类型变量将使用希腊字母表的第一部分来编写： $\alpha ,\beta ,\gamma ,\delta ,...$ 。

不幸的是，这给静态类型检查带来了一些问题，因为类型检查器不知道某个操作（例如，相等性测试）将为哪些类型定义。这个问题的解决方案和静态类型语言一样多（这可能有点夸张，但不是特别夸张）。Haskell 选择的解决方案是类型类系统。当然，这是否是“正确”的解决方案或“最佳”解决方案取决于您的应用领域。然而，这是我们现有的解决方案，所以你应该学会喜欢它。

相等性测试

回到相等性测试的问题，我们想要实现的是定义一个函数 == （相等性运算符），它接受两个参数，每个参数都是相同的类型（称为 $\alpha$ ），并返回一个布尔值。但这个函数可能并非为 *所有* 类型定义；只为一些类型定义。因此，我们将这个函数 == 与一个类型类相关联，我们称之为Eq。如果一个特定类型 $\alpha$ 属于某个类型类（也就是说，与该类关联的所有函数都为 $\alpha$ 实现），我们说 $\alpha$ 是该类的 *实例* 。例如，Int是Eq的实例，因为相等性是在整数上定义的。

Num 类

除了重载像 == 这样的运算符，Haskell 还重载了数字常量（即，1、2、3 等）。这样做是为了当你输入像 5 这样的数字时，编译器可以自由地将 5 视为一个整数或浮点数，因为它认为合适。它定义了Num类来包含所有这些数字以及对它们的某些最小操作（例如，加法）。基本数值类型（Int、Double）被定义为Num.

的实例。我们只是简单地介绍了类型类的强大功能（和复杂性）。在 Classes 部分将对此进行更深入的讨论，但在我们到达那里之前，我们还需要一些背景知识。在我们这样做之前，我们需要更多地谈谈函数。

Show 类

Haskell 中另一个标准类是 Show 类。属于 Show 类的类型具有将该类型的值转换为字符串的函数。这个函数叫做 show 。例如，应用于整数 5 的 show 是字符串 "5"；应用于字符 'a' 的 show 是三个字符的字符串 "'a'"（第一个和最后一个字符是撇号）。应用于字符串的 show 只是在它周围加上引号。你可以在解释器中测试它

示例

Prelude> show 5
"5"
Prelude> show 'a'
"'a'"
Prelude> show "Hello World"
"\"Hello World\""

注意

最后一行出现反斜杠的原因是内部引号被“转义”，这意味着它们是字符串的一部分，而不是解释器打印值的的一部分。实际字符串不包含反斜杠。

某些类型不是 Show 的实例；例如函数。如果你试图显示一个函数（比如 sqrt ），编译器或解释器会给你一些神秘的错误信息，抱怨缺少实例声明或非法类约束。

函数类型

在 Haskell 中，函数是 *一等值* ，这意味着就像 1 或 'c' 是具有类型的值一样，square 或 ++ 这样的函数也是如此。在我们过多地讨论函数之前，我们需要做一个简短的关于非常理论的计算机科学的旁白（别担心，不会太痛苦），并谈谈 lambda 演算。

Lambda 演算

虽然“Lambda 演算”这个名字可能听起来很吓人，但它实际上描述了一种相当简单的函数表示系统。在 Lambda 演算中，我们可以这样写一个平方函数：$\lambda x.x*x$，这意味着我们取一个值，我们称之为 $x$（这就是 $\lambda x.$ 的含义），然后将它乘以它自身。 $\lambda$ 被称为“Lambda 抽象”。一般来说，Lambda 表达式只能有一个参数。如果我们想要编写一个接受两个数字的函数，将第一个数字加倍并将其添加到第二个数字，我们可以这样写：$\lambda x\lambda y.2*x+y$。当我们将一个值应用到 Lambda 表达式时，我们会移除最外层的 $\lambda$ 并用该值替换 Lambda 变量的所有出现。例如，如果我们评估 $(\lambda x.x*x)5$，我们会移除 Lambda 并用 $5$ 替换 $x$ 的所有出现，得到 $(5*5)$，结果是 $25$。

事实上，Haskell 大部分基于 Lambda 演算的扩展，这两个表达式可以直接在 Haskell 中编写（我们只需将 $\lambda$ 替换为反斜杠 (\)，将 $.$ 替换为 (->)；此外，我们不需要重复 Lambda；当然，在 Haskell 中，如果我们正在定义函数，就必须为它们命名）。

square = \x -> x*x
f = \x y -> 2*x + y

你也可以在交互式 shell 中评估 Lambda 表达式

示例

Prelude> (\x -> x*x) 5
25
Prelude> (\x y -> 2*x + y) 5 4
14

我们可以从第二个例子中看到，我们需要为 Lambda 抽象提供两个参数，一个对应于 x，另一个对应于 y。

高阶类型

“高阶类型”指的是那些元素是函数的类型。赋予函数的类型模仿了 Lambda 演算中函数的表示方法。例如，square 的定义为 $\lambda x.x*x$。要获得它的类型，我们首先要问自己 x 的类型是什么。假设我们决定 x 是一个 Int。然后，我们注意到函数 square 接受一个 Int 并产生一个值 x*x。我们知道，当我们将两个 Int 相乘时，我们会得到另一个 Int，所以 square 结果的类型也是 Int。因此，我们说 square 的类型是 Int -> Int。

我们可以对上面的函数 f (\x y -> 2*x + y) 进行类似的分析。这个函数的值（记住，函数本身就是值）是接受一个值 x 并产生一个新值的函数，这个新函数接受一个值 y 并产生 2*x+y。例如，如果我们取 f 并且只向它应用一个数字，我们得到 $(\lambda x\lambda y.2x+y)5$，它将变为我们的新值 $\lambda y.2(5)+y$，其中 $x$ 的所有出现都被替换为应用的值，$5$。

我们知道 f 接受一个 Int 类型的值，并产生一个类型未知的值。但我们知道该值的类型是 $\lambda y.2(5)+y$ 的类型。我们应用上述分析，发现该表达式具有类型 Int -> Int。因此，f 接受一个 Int 类型的值，并产生一个具有类型 Int -> Int 的值。所以 f 的类型是 Int -> (Int -> Int)。

注意

括号不是必需的；在函数类型中，如果存在 $\alpha \rightarrow \beta \rightarrow \gamma$，则假定 $\beta \rightarrow \gamma$ 是分组的。如果你想要其他方式，使用 $\alpha \rightarrow \beta$ 分组，则需要将它们放在括号中。

这并不完全准确。正如我们之前所见，像 5 这样的数字并不真正属于类型 Int，它们属于类型 Num a => a。

我们可以使用之前使用的 “:t” 轻松找出 Prelude 函数的类型。

示例

Prelude> :t head
head :: [a] -> a
Prelude> :t tail
tail :: [a] -> [a]
Prelude> :t null
null :: [a] -> Bool
Prelude> :t fst
fst :: (a,b) -> a
Prelude> :t snd
snd :: (a,b) -> b

我们将其解释为：“head” 是一个函数，它接受一个包含类型为 “a” 的值的列表，并返回一个类型为 “a” 的值；“tail” 接受一个 “a” 的列表，并返回另一个 “a” 的列表；“null” 接受一个 “a” 的列表，并返回一个布尔值；“fst” 接受一个类型为 “(a,b)” 的对，并返回一个类型为 “a” 的值，等等。

注意

说 fst 的类型是 (a,b) -> a 并不一定意味着它只返回第一个元素；它只是意味着它返回一个与第一个元素具有 *相同类型* 的值。

我们还可以获取像 + 和 * 以及 ++ 和 : 这样的运算符的类型；但是，要做到这一点，我们需要将它们放在括号中。一般来说，任何以 *中缀* 方式使用的函数（意味着它位于两个参数的中间而不是它们前面）在获取其类型时都必须放在括号中。

示例

Prelude> :t (+)
(+) :: Num a => a -> a -> a
Prelude> :t (*)
(*) :: Num a => a -> a -> a
Prelude> :t (++)
(++) :: [a] -> [a] -> [a]
Prelude> :t (:)
(:) :: a -> [a] -> [a]

+ 和 * 的类型相同，这意味着 + 是一个函数，对于某个类型为 a 的值（它是 Num 的实例），它接受一个类型为 a 的值，并产生另一个函数，该函数接受一个类型为 a 的值，并产生一个类型为 a 的值。简而言之，我们可以说 + 接受两个类型为 a 的值，并产生一个类型为 a 的值，但这不够精确。

++ 的类型意味着，简而言之，对于给定的类型 a，++ 接受两个 a 的列表，并产生一个新的 a 的列表。类似地，: 接受一个类型为 a 的值和另一个类型为 [a]（a 的列表）的值，并产生另一个类型为 [a] 的值。

那个讨厌的 IO 类型

你可能会想尝试获取像 putStrLn 这样的函数的类型。

示例

Prelude> :t putStrLn
putStrLn :: String -> IO ()
Prelude> :t readFile
readFile :: FilePath -> IO String

世界上那个 IO 是什么？它基本上是 Haskell 用于表示这些函数不是真正函数的方式。它们被称为“IO 动作”（因此有 IO）。由此产生的直接问题是：好吧，那么我如何摆脱 IO 呢？好吧，你不能在保持代码的纯函数功能的同时使用具有诸如 IO String -> String 之类的类型的函数。Haskell 的纯函数在应用于相同参数时总是给出相同的结果，就像数学中的情况一样。另一方面，readFile 会在调用时返回文件内容。假设在正在进行的 Haskell 进程中 x = "TABLE OF CONTENTS"，之后 x = "TABLE OF CONTENTS {新行} "Chapter One"。在使用可变变量的语言中这不会有问题，但在 Haskell 中，一旦将值赋给 x，更改该值可能会导致系统崩溃之前出现奇怪的行为。因此，在你能想到的几乎所有用例中，使用具有 IO 类型的元素的方法是将它们与程序的纯部分隔离，方法是将它们与其他函数结合起来。

例如，如果你使用 readFile 读取文件，那么你可能想要对它返回的字符串做些什么（否则，为什么要首先读取文件呢）。假设你有一个函数 f，它接受一个 String 类型的值并产生一个 Int 类型的值。你不能直接将 f 应用于 readFile 的结果，因为 f 的输入是 String，而 readFile 的输出是 IO String，它们不匹配。但是，你可以将它们结合起来，如下所示：

main = do
  s <- readFile "somefile"
  let i = f s
  putStrLn (show i)

在这里，我们使用箭头约定来“从 IO 动作中取出字符串”，然后将 f 应用于字符串（称为 s）。然后，例如，我们将 i 打印到屏幕上。请注意，let这里没有对应的in。这是因为我们处于do块中。还要注意，我们没有编写 i <- f s，因为 f 只是一个普通函数，而不是一个 IO 动作。注意：如果你想简化 putStrLn (show i)，可以将其简化为 print i。

显式类型声明

有时希望显式指定某些元素或函数的类型，出于以下一个（或多个）原因

• 清晰度
• 速度
• 调试

有些人认为，将所有顶级函数的类型都指定出来是良好的软件工程实践。如果没有别的，如果你试图编译程序，并且遇到了你不理解的类型错误，如果你显式声明了部分函数的类型，那么找到错误的位置可能会更容易。

类型声明是与函数定义分开编写的。例如，我们可以像以下代码一样显式指定函数 square 的类型（显式声明的类型称为 *类型签名*）。

square :: Num a => a -> a
square x = x*x

这两行甚至不必挨在一起。但是，你指定的类型必须与函数定义的推断类型匹配（或者更具体）。在此定义中，你可以将 square 应用于任何 Num 的实例：Int、Double 等。但是，如果你事先知道 square 将只应用于类型为 Int 的值，则可以将其类型 *细化* 为

square :: Int -> Int
square x = x*x

现在，你只能将 square 应用于类型为 Int 的值。此外，使用此定义，编译器不必生成原始函数定义中指定的一般代码，因为它知道你将只将 square 应用于 Int，因此它可能能够生成更快的代码。

如果你启用了扩展（在 Hugs 中为 “-98”，在 GHC(i) 中为 “-fglasgow-exts”），你也可以为表达式添加类型签名，而不仅仅是函数。例如，你可以写

square (x :: Int) = x*x

它告诉编译器 x 是一个 Int；但是，它让编译器自行推断表达式的剩余部分的类型。在此示例中，square 的类型是什么？先猜一下，然后你可以通过将此代码输入到文件中并将其加载到你的解释器中，或者通过询问表达式的类型来验证你的猜测。

示例

Prelude> :t (\(x :: Int) -> x*x)

因为这个 lambda 表达式等价于上面的函数声明。

函数参数

在关于 列表 的部分中，我们看到了函数将其他函数作为参数的示例。例如，map 接收一个应用于列表中每个元素的函数，filter 接收一个告诉它保留列表中哪些元素的函数，而 foldl 接收一个告诉它如何将列表元素组合在一起的函数。与 Haskell 中的任何其他函数一样，这些函数都是类型化的。

首先，让我们考虑一下 map 函数。它的作用是接受一个元素列表，并产生另一个元素列表。这两个列表的元素类型不必相同。因此，map 将接受一个类型为 [a] 的值，并产生一个类型为 [b] 的值。它是如何做到的？它使用用户提供的函数进行转换。为了将一个 a 转换为一个 b，这个函数必须具有类型 a -> b。因此，map 的类型是 (a -> b) -> [a] -> [b]，你可以在你的解释器中使用 “:t” 验证这一点。

我们可以对 filter 应用相同的分析，并发现它的类型是 (a -> Bool) -> [a] -> [a]。正如我们介绍了 foldr 函数，你可能会倾向于给它类型 (a -> a -> a) -> a -> [a] -> a，这意味着你接受一个将两个 a 合并成另一个的函数，一个类型为 a 的初始值，一个 a 的列表来产生一个类型为 a 的最终值。事实上，foldr 具有更通用的类型：(a -> b -> b) -> b -> [a] -> b。所以它接受一个将 a 和 b 转换成 b 的函数，一个类型为 b 的初始值和一个 a 的列表。它产生一个 b。

为了看到这一点，我们可以编写一个函数 count，它计算列表中满足给定约束的成员数量。当然，你可以使用 filter 和 length 来做到这一点，但我们也会使用 foldr 来实现。

module Count
    where

import Char

count1 bTest list = length (filter bTest list)
count2 bTest list = foldr (\x cnt -> if bTest x then cnt+1 else cnt) 0 list

count1 的功能很简单。它根据谓词 bTest 过滤列表 list，然后获取结果列表的长度。另一方面，count2 使用初始值（它是一个整数）来保存当前计数。对于列表 list 中的每个元素，它应用显示的 lambda 表达式。这将接受两个参数，cnt 保存当前计数，x 是我们正在查看的列表中的当前元素。它检查 bTest 是否对 x 成立。如果成立，它将返回新值 cnt+1，增加满足谓词的元素计数。如果它不成立，它只返回 cnt，旧计数。当 lambda 定义如上所示时，count2 Char.isLower "aBCde" 展开为 lambda 'a' (lambda 'B' (lambda 'C' (lambda 'd' (lambda 'e' 0))))。

练习
自己找出，然后验证以下表达式的类型，如果它们有类型。还要注意表达式是否为类型错误 \x -> [x] \x y z -> (x,y:z:[]) \x -> x + 5 \x -> "hello, world" \x -> x 'a' \x -> x x \x -> x + x

数据类型

元组和列表是定义结构化值的不错且常用的方法。然而，通常希望能够定义我们自己的数据结构和它们上面的函数。所谓“数据类型”是使用data关键字定义的。

对

例如，一对元素的定义（类似于标准的内置对类型）可以是

data Pair a b = Pair a b

让我们逐字分析这段代码。首先我们说“data”，意思是我们要定义一个数据类型。然后我们给出数据类型的名称，在本例中是“Pair”。紧随“Pair”之后的“a”和“b”是唯一的类型参数，就像“a”是函数 map 的类型一样。所以直到这一点，我们已经说过我们要定义一个名为“Pair”的数据结构，它被参数化到两种类型上，a 和 b。请注意，你不能有 Pair a a = Pair a a - 在这种情况下，编写 Pair a = Pair a a。

在等号之后，我们指定了这种数据类型的构造函数。在本例中，有一个构造函数，“Pair”（它不一定与类型具有相同的名称，但在只有一个构造函数的情况下，它似乎更有意义）。在这一对之后，我们再次编写“a b”，这意味着为了构造一个 Pair，我们需要两个值，一个是类型 a，一个是类型 b。

这个定义引入了函数 Pair :: a -> b -> Pair a b，你可以用它来构造 Pair。如果你将这段代码输入到一个文件中并加载它，你可以看到它们是如何构造的

示例

Datatypes> :t Pair
Pair :: a -> b -> Pair a b
Datatypes> :t Pair 'a'
Pair 'a' :: a -> Pair Char a
Datatypes> :t Pair 'a' "Hello"
Pair 'a' "Hello" :: Pair Char [Char]

因此，通过给 Pair 两个值，我们已经完全构造了一个类型为 Pair 的值。我们可以编写涉及对的函数，如下所示

pairFst (Pair x y) = x
pairSnd (Pair x y) = y

在这里，我们使用了 Haskell 的模式匹配功能来查看一个对并从中提取值。在 pairFst 的定义中，我们获取一个完整的 Pair 并提取第一个元素；pairSnd 也是如此。我们将在关于模式匹配的部分中更详细地讨论模式匹配。

练习
编写一个 Triple 数据类型声明，它是一个包含三个元素的类型，所有元素的类型都不相同。编写函数 tripleFst、tripleSnd 和 tripleThr 分别提取第一个、第二个和第三个元素。 编写一个数据类型 Quadruple，它保存四个元素。但是，前两个元素必须是相同的类型，后两个元素必须是相同的类型。编写一个函数 firstTwo，它返回一个包含前两个元素的列表，以及一个函数 lastTwo，它返回一个包含后两个元素的列表。为这些函数编写类型签名。

多个构造函数

我们已经看到了一个具有一个构造函数的数据类型的示例：Pair。拥有多个构造函数也是可能的（而且非常有用）。

让我们考虑一个简单的函数，它在列表中搜索满足给定谓词的元素，然后返回满足该谓词的第一个元素。如果列表中的任何元素都不满足谓词，我们该怎么办？下面列出了几个选项

• 引发错误
• 无限循环
• 编写一个检查函数
• 返回第一个元素
• $...$

引发错误当然是一个选项（请参阅关于异常的部分，以了解如何做到这一点）。问题是很难/不可能从这些错误中恢复。无限循环是可能的，但不是很实用。我们可以编写一个姐妹函数，它检查列表是否包含满足谓词的元素，并让用户始终先使用这个函数。我们可以返回第一个元素，但这非常临时且难以记住；如果列表本身为空怎么办？

没有基本的选项来简单地解决这个问题，这意味着我们必须更多地思考它。我们试图做什么？我们试图编写一个可能成功也可能不成功的函数。此外，如果成功，它将返回某种值。让我们编写一个数据类型

data Maybe a = Nothing
             | Just a

这是 Haskell 中最常见的数据类型之一，并在 Prelude 中定义。

在这里，我们说，创建类型为 Maybe a 的东西有两种可能的方式。第一种是使用空元构造函数 Nothing，它不接受任何参数（这就是“空元”的含义）。第二种是使用构造函数 Just，以及一个类型为 a 的值。

Maybe 类型在各种情况下都很有用。例如，假设我们要编写一个函数（像 head）返回给定列表的第一个元素。但是，我们不希望程序在给定列表为空时崩溃。我们可以用类似这样的函数来实现这一点

firstElement :: [a] -> Maybe a
firstElement []     = Nothing
firstElement (x:xs) = Just x

这里的类型签名表示 firstElement 接受一个 a 的列表，并产生一个类型为 Maybe a 的东西。在代码的第一行，我们对空列表 [] 进行了匹配。如果这个匹配成功（即列表实际上是空的），我们就返回 Nothing。如果第一个匹配失败，那么我们尝试匹配 x:xs，它必须成功。在这种情况下，我们返回 Just x。

对于我们的 findElement 函数，我们用值 Nothing 表示失败，用值 a 表示成功，用 Just a 表示。我们的函数可能看起来像这样

findElement :: (a -> Bool) -> [a] -> Maybe a
findElement p [] = Nothing
findElement p (x:xs) =
    if p x then Just x
    else findElement p xs

第一行在这里给出函数的类型。在本例中，我们的第一个参数是谓词（它接受一个类型为 a 的元素，并且当且仅当元素满足谓词时返回 True）；第二个参数是 a 的列表。我们的返回值是可能是 a。也就是说，如果函数成功，我们将返回 Just a，否则返回 Nothing。

另一个有用的数据类型是 Either 类型，定义为

data Either a b = Left a
                | Right b

这是一种表达选择的途径。也就是说，类型为 Either a b 的东西是要么类型为 a 的值（使用 Left 构造函数），要么类型为 b 的值（使用 Right 构造函数）。

练习
编写一个数据类型 Tuple，它可以保存一个、两个、三个或四个元素，具体取决于构造函数（即，应该有四个构造函数，每个元素对应一个参数数量）。还提供函数 tuple1 到 tuple4，它们接受一个元组并返回 Just 该位置的值，或者如果数字无效则返回 Nothing（即，你要求 tuple4 在一个只保存两个元素的元组上）。 根据我们之前练习中对Tuple的定义，编写一个函数，该函数接收一个Tuple并返回以下结果：如果它是一个单元组，则返回其值；如果它是一个二元组，则返回一个 Haskell 对（例如，('a',5)）；如果它是一个三元组，则返回一个 Haskell 三元组；如果它是一个四元组，则返回一个 Haskell 四元组。请记住：无法编写一个返回不同类型的函数。您需要使用Either类型来表示这一点。

递归数据类型

我们还可以定义递归数据类型。这些数据类型的定义基于自身。例如，我们可以定义一个列表数据类型为

data List a = Nil
            | Cons a (List a)

在这个定义中，我们定义了List a类型的含义。我们说一个列表要么是空的（Nil），要么是Cons一个类型为a的值和另一个类型为List a的值。这几乎与 Haskell 中列表数据类型的实际定义相同，只是使用特殊的语法，其中[]对应于Nil，:对应于Cons。我们可以为我们的列表编写自己的length函数，如下所示

listLength Nil = 0
listLength (Cons x xs) = 1 + listLength xs

这个函数稍微复杂一些，并使用递归来计算List的长度。第一行表示空列表（Nil）的长度为 $0$。这是显而易见的。第二行告诉我们如何计算非空列表的长度。非空列表必须是Cons x xs的形式，其中x和xs是某些值。我们知道xs是另一个列表，并且我们知道当前列表的长度无论是什么，都是其尾部（xs的值）的长度加上一（为了考虑x）。因此，我们将listLength函数应用于xs并将结果加一。这给了我们整个列表的长度。

练习
编写函数listHead、listTail、listFoldl和listFoldr，它们等效于它们的 Prelude 孪生兄弟，但 在我们的List数据类型上起作用。不要担心前两个的异常情况。

二叉树

我们可以定义比列表更复杂的数据类型。假设我们想定义一个看起来像二叉树的结构。二叉树是一个结构，它有一个根节点；树中的每个节点要么是“叶子”，要么是“分支”。如果是叶子，则它包含一个值；如果是分支，则它包含一个值以及一个左孩子和一个右孩子。这些孩子中的每一个都是另一个节点。我们可以定义这样的数据类型，如下所示

data BinaryTree a
    = Leaf a
    | Branch (BinaryTree a) a (BinaryTree a)

在这个数据类型声明中，我们说BinaryTree的a要么是Leaf，它包含一个a，要么是包含一个左孩子（它是一个BinaryTree的a）、一个节点值（它是一个a）和一个右孩子（它也是一个BinaryTree的a）的分支。简单地修改listLength函数，使它不再计算列表的长度，而是计算BinaryTree中的节点数量。你能弄清楚怎么做吗？我们可以称此函数为treeSize。解决方案如下所示

treeSize (Leaf x) = 1
treeSize (Branch left x right) =
  1 + treeSize left + treeSize right

这里，我们说叶子的尺寸为 $1$，而分支的尺寸是其左孩子的尺寸加上其右孩子的尺寸，再加上一。

练习
编写一个函数elements，它以自下而上、从左到右的方式返回BinaryTree中的元素（即，返回的第一个元素是最左边的叶子，然后是其父节点的值，然后是另一个孩子的值，依此类推）。结果类型应该是一个正常的 Haskell 列表。 为BinaryTree编写一个 foldr 函数treeFoldr，并用它重写elements（将新函数命名为elements2）。treeFoldr的类型应为(a -> b -> b) -> b -> BinaryTree a -> b。 为BinaryTree编写一个 foldl 函数treeFoldl，并用它重写elements（将新函数命名为elements3）。

枚举集

您还可以使用数据类型来定义诸如枚举集之类的东西，例如，只能具有有限数量值的类型。我们可以定义一个颜色类型

data Color
    = Red
    | Orange
    | Yellow
    | Green
    | Blue
    | Purple
    | White
    | Black

这足以处理简单的颜色。假设我们正在使用它来编写一个绘图程序，那么我们可以编写一个函数来在Color和 RGB 三元组之间转换。我们可以编写一个colorToRGB函数，如下所示

colorToRGB Red    = (255,0,0)
colorToRGB Orange = (255,128,0)
colorToRGB Yellow = (255,255,0)
colorToRGB Green  = (0,255,0)
colorToRGB Blue   = (0,0,255)
colorToRGB Purple = (255,0,255)
colorToRGB White  = (255,255,255)
colorToRGB Black  = (0,0,0)

如果我们还想让用户定义自己的自定义颜色，我们可以将Color数据类型更改为类似的东西

data Color
    = Red
    | Orange
    | Yellow
    | Green
    | Blue
    | Purple
    | White
    | Black
    | Custom Int Int Int -- R G B components

并为colorToRGB添加最终的定义

colorToRGB (Custom r g b) = (r,g,b)

单元类型

在 Haskell 中（来自 Prelude）定义的最后一个有用的数据类型是单元类型。它的定义是

data () = ()

此类型的唯一真值为()。这本质上与 C 或 Java 等语言中的void类型相同，当我们在本章Io中讨论 IO 时将很有用。

我们将在模式匹配和数据类型部分中更深入地探讨数据类型。

延续传递风格

有一种称为“延续传递风格”（也简称为“CPS”）的函数式编程风格。CPS 背后的理念是将下一步该做什么作为函数参数传递。我将通过一个例子来解释，这个例子过于复杂，无法在此时写出来，然后给出一个真实的例子，尽管它缺乏动机。

考虑解析问题。这里的理念是，我们有一系列标记（单词、字母，等等），我们想赋予它们结构。将 Java 标记字符串转换为 Java 抽象语法树的任务是解析问题的示例。解析英文句子也是如此（尽管后者非常困难，即使对于母语为英语的人来说，解析来自现实世界的句子也很困难）。

假设我们正在解析类似 C 或 Java 的东西，其中函数在括号中接受参数。但为了简单起见，假设它们没有用逗号分隔。也就是说，函数调用看起来像myFunction(x y z)。我们想将其转换为类似于包含第一个字符串“myFunction”和第二个包含三个字符串元素的列表（“x”、“y”和“z”）的对。

解决这个问题的普遍方法是编写一个函数来解析像这样的函数调用。首先它会查找标识符（“myFunction”），然后查找左括号，然后查找零个或多个标识符，然后查找右括号。

一种方法是使用两个函数

parseFunction   ::
    [Token] -> Maybe ((String, [String]), [Token])

parseIdentifier ::
    [Token] -> Maybe (String, [Token])

这里的想法是，如果我们调用parseFunction，如果它没有返回Nothing，那么它会返回前面描述的对，以及解析函数后剩余的任何内容。类似地，parseIdentifier将解析其中一个参数。如果它返回Nothing，那么它不是参数；如果它返回Just，那么那个Just就是与剩余标记配对的参数。

parseFunction函数将做的是解析一个标识符。如果失败，它本身就会失败。否则，它会继续尝试解析左括号。如果成功，它会重复调用parseIdentifier，直到失败。然后它会尝试解析右括号。如果成功，则完成。否则，它会失败。

但是，还有另一种思考这个问题的方法。这种解决方案的优势在于，函数不再需要返回剩余的标记（这往往很丑陋）。与其使用上面的方法，我们编写函数

parseFunction   ::
    [Token] -> ((String, [String]) -> [Token] -> a) ->
    ([Token] -> a) -> a

parseIdentifier ::
    [Token] -> (String -> [Token] -> a) ->
    ([Token] -> a) -> a

让我们考虑 `parseIdentifier` 函数。它接受三个参数：一个 token 列表和两个 *continuation*。第一个 continuation 用于成功时的操作，第二个 continuation 用于失败时的操作。`parseIdentifier` 的作用就是尝试读取一个标识符。如果成功，它将使用该标识符和剩余的 token 作为参数调用第一个 continuation。如果读取标识符失败，它将使用所有 token 调用第二个 continuation。

现在考虑 `parseFunction` 函数。回顾一下，它想要读取一个标识符、一个左括号、零个或多个标识符和一个右括号。因此，它首先调用 `parseIdentifier` 函数。它传递给 `parseIdentifier` 的第一个参数是 token 列表。第一个 continuation（即 `parseIdentifier` 成功时的操作）是一个函数，它将查找左括号、零个或多个参数和一个右括号。第二个 continuation（失败参数）将直接使用传递给 `parseFunction` 的失败函数。

现在，我们只需要定义一个函数，它查找左括号、零个或多个参数和一个右括号。这很简单。我们编写一个函数，它查找左括号，然后调用 `parseIdentifier`，使用成功 continuation 来查找更多标识符，以及使用 "失败" continuation 来查找右括号（注意，这种失败并不真正意味着失败——它只是意味着没有更多参数了）。

我知道这段讨论很抽象。我乐于提供所有解析的代码，但这可能在目前过于复杂。相反，让我们考虑在一个列表上折叠的问题。我们可以编写一个 CPS 风格的折叠函数：

cfold' f z [] = z
cfold' f z (x:xs) = f x z (\y -> cfold' f y xs)

在这段代码中，`cfold'` 接收一个函数 `f`，它接受三个参数，与标准折叠函数略有不同。第一个是当前列表元素 `x`，第二个是累积元素 `z`，第三个是 continuation：基本上，接下来要做什么。

我们可以为 `cfold'` 编写一个包装函数，使其表现得更像一个正常的折叠函数：

cfold f z l = cfold' (\x t g -> f x (g t)) z l

我们可以测试此函数是否按我们期望的方式执行：

示例

CPS> cfold (+) 0 [1,2,3,4]
10
CPS> cfold (:) [] [1,2,3]
[1,2,3]

用辅助函数 `cfold'` 来构建 `cfold` 函数的一大好处是，我们可以直接使用辅助函数。这使得我们可以非常轻松地改变折叠的执行顺序，例如：

示例

CPS> cfold' (\x t g -> (x : g t)) [] [1..10]
[1,2,3,4,5,6,7,8,9,10]
CPS> cfold' (\x t g -> g (x : t)) [] [1..10]
[10,9,8,7,6,5,4,3,2,1]

这些对 `cfold'` 的调用之间的唯一区别是，我们是在构造列表之前还是之后调用 continuation。事实证明，这种细微的差异将行为从类似 `foldr` 变成了类似 `foldl`。我们可以像下面这样评估这两个调用（设 `f` 是折叠函数）：

     cfold' (\x t g -> (x : g t)) [] [1,2,3]
==>  cfold' f [] [1,2,3]
==>  f 1 [] (\y -> cfold' f y [2,3])
==>  1 : ((\y -> cfold' f y [2,3]) [])
==>  1 : (cfold' f [] [2,3])
==>  1 : (f 2 [] (\y -> cfold' f y [3]))
==>  1 : (2 : ((\y -> cfold' f y [3]) []))
==>  1 : (2 : (cfold' f [] [3]))
==>  1 : (2 : (f 3 [] (\y -> cfold' f y [])))
==>  1 : (2 : (3 : (cfold' f [] [])))
==>  1 : (2 : (3 : []))
==>  [1,2,3]

     cfold' (\x t g -> g (x:t)) [] [1,2,3]
==>  cfold' f [] [1,2,3]
==>  (\x t g -> g (x:t)) 1 [] (\y -> cfold' f y [2,3])
==>  (\g -> g [1]) (\y -> cfold' f y [2,3])
==>  (\y -> cfold' f y [2,3]) [1]
==>  cfold' f [1] [2,3]
==>  (\x t g -> g (x:t)) 2 [1] (\y -> cfold' f y [3])
==>  cfold' f (2:[1]) [3]
==>  cfold' f [2,1] [3]
==>  (\x t g -> g (x:t)) 3 [2,1] (\y -> cfold' f y [])
==>  cfold' f (3:[2,1]) []
==>  [3,2,1]

总的来说，continuation passing style 是一种非常强大的抽象，尽管它可能难以掌握。我们将在本书后面更深入地讨论这个主题。

练习
测试 CPS 风格的折叠是否模仿了 `foldr` 或 `foldl` 中的任何一个。如果不是，差异在哪里？ 使用 continuation passing style 编写 `map` 和 `filter` 函数。