另一个 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 是布尔（发音为“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.

的实例。

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 并将$x$ 的每次出现替换为$5$，得到$(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]

+和*的类型相同，这意味着+是一个函数，对于某种类型为Num实例的a，它接受一个类型为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 {new line} "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 列表，以生成一个类型为 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的数据类型声明，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，如果数字无效（例如，你对仅包含两个元素的元组请求tuple4），则返回Nothing。 基于我们之前练习中对Tuple的定义，编写一个函数，该函数接收一个Tuple并返回其值（如果它是单元素元组），或者如果它是双元素元组则返回一个Haskell对（例如，('a',5)），或者如果它是三元素元组则返回一个Haskell三元组，或者如果它是四元素元组则返回一个Haskell四元组。请记住：无法编写一个返回不同类型的函数。你需要使用Either类型来表示这种情况。

递归数据类型

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

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

在这个定义中，我们定义了类型为List a的含义。我们说一个列表要么是空的（Nil），要么是类型为a的值和另一个类型为List a的值的Cons。这与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)

在这个数据类型声明中，我们说a类型的BinaryTree要么是一个包含a的Leaf，要么是一个分支，它包含一个左子节点（它是a类型的BinaryTree）、一个节点值（它是a）和一个右子节点（它也是a类型的BinaryTree）。修改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某个值，则该值是与剩余标记配对的参数。

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

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

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

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

让我们考虑一下parseIdentifier。它接受三个参数：一个标记列表和两个延续。第一个延续是在成功时要执行的操作。第二个延续是在失败时要执行的操作。然后，parseIdentifier的作用是尝试读取一个标识符。如果成功，它会将该标识符和剩余的标记作为参数调用第一个延续。如果读取标识符失败，它会将所有标记作为参数调用第二个延续。

现在考虑parseFunction。回想一下，它希望读取一个标识符、一个开括号、零个或多个标识符以及一个闭括号。因此，它首先执行的操作是调用parseIdentifier。它提供的第一个参数是标记列表。第一个延续（如果parseIdentifier成功应执行的操作）反过来是一个函数，它将查找一个开括号、零个或多个参数以及一个闭括号。第二个延续（失败参数）将只是传递给parseFunction的失败函数。

现在，我们只需要定义这个查找一个开括号、零个或多个参数以及一个闭括号的函数。这很容易。我们编写一个函数来查找开括号，然后调用parseIdentifier，其成功延续查找更多标识符，而“失败”延续查找闭括号（请注意，此失败并不真正意味着失败——它只是意味着没有更多参数了）。

我意识到这段讨论非常抽象。我愿意为所有这些解析提供代码，但目前可能过于复杂。相反，考虑跨列表折叠的问题。我们可以将CPS折叠写成

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

在此代码中，cfold'接受一个函数f，该函数接受三个参数，与标准折叠略有不同。第一个是当前列表元素x，第二个是累积元素z，第三个是延续：基本上是接下来要执行的操作。

我们可以为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'的这些调用的唯一区别是我们是在构建列表之前还是之后调用延续。事实证明，这种细微的差异会改变行为，从像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]

通常，延续传递风格是一种非常强大的抽象，尽管它可能难以掌握。我们将在本书的后面更全面地重新讨论这个主题。

练习
测试 CPS 风格的折叠是否模拟了foldr和foldl中的任何一个。如果不是，区别在哪里？ 使用延续传递风格编写map和filter。