第 2 章：类型与函数（Types and Functions）

原文：Bartosz Milewski, Category Theory for Programmers, Scala Edition, Chapter 2. 原书 PDF、.tex 源文件及相关图像采用 CC BY-SA 4.0；本译文按同一许可发布。

类型与函数构成的范畴在编程中扮演重要角色，所以我们来谈谈类型是什么，以及为什么需要它们。

2.1 谁需要类型？（Who Needs Types?）

关于静态类型与动态类型、强类型与弱类型的优劣，似乎一直存在争议。让我用一个思想实验来说明这些选择。想象有几百万只猴子坐在计算机键盘前，开心地随机敲击按键，生成程序、编译并运行它们。

在机器语言中，猴子产生的任意字节组合都会被接受并运行。但在更高层语言中，我们会欣赏编译器能够检测词法错误和语法错误这一事实。许多猴子会因此得不到香蕉，但剩下的程序更可能有用。类型检查又为无意义程序设置了一道屏障。进一步说，在动态类型语言中，类型不匹配会在运行时被发现；而在强类型、静态检查语言中，类型不匹配会在编译时被发现，从而在许多错误程序有机会运行之前就消除它们。

所以问题是：我们想让猴子开心，还是想生成正确的程序？

打字猴子的思想实验通常以产出莎士比亚全集为目标。如果在过程中加入拼写检查器和语法检查器，成功概率会大幅增加。类型检查器的类比还能走得更远：它会确保一旦 Romeo 被声明为人类，他就不会突然长出叶子，也不会在强大的引力场中困住光子。

2.2 类型关乎可组合性（Types Are About Composability）

范畴论研究的是箭头的组合。但并不是任意两个箭头都能组合。一个箭头的目标对象必须与下一个箭头的源对象相同。在编程中，我们把一个函数的结果传给另一个函数。如果目标函数无法正确解释源函数产生的数据，程序就无法工作。为了让组合成立，两端必须契合。语言的类型系统越强，就越能描述并机械地验证这种匹配。

我听到过的反对强静态类型检查的唯一严肃论点是：它可能会排除一些语义上正确的程序。实践中，这种情况极少发生；并且无论如何，每种语言都会提供某种后门，让你在真正必要时绕过类型系统。即便 Haskell 也有 unsafeCoerce。不过，这类手段应该谨慎使用。Franz Kafka 笔下的 Gregor Samsa 在变形成巨大甲虫时打破了类型系统，而我们都知道结局如何。

另一个常见论点是，处理类型会给程序员造成过多负担。写过几次 C++ 迭代器声明之后，我能同情这种感受；不过，有一种技术叫类型推断（type inference），它能让编译器根据使用上下文推导大多数类型。在 C++ 中，现在可以用 auto 声明变量，让编译器判断其类型。

在 Haskell 中，除了少数情况，类型标注都是可选的。尽管如此，程序员通常还是会写类型标注，因为它们能说明代码语义，也让编译错误更容易理解。Haskell 中常见的实践是先设计类型，再开始项目。随后，类型标注会驱动实现，并成为由编译器强制执行的注释。

强静态类型常被用作不测试代码的借口。你有时会听到 Haskell 程序员说：“如果能编译，它一定是正确的。”当然，类型正确的程序并不保证在产生正确输出的意义上是正确的。这种轻率态度的结果是，在若干研究中，Haskell 的代码质量并没有像人们预期那样遥遥领先。似乎在商业环境里，修 bug 的压力只会施加到某个质量水平为止；这更多与软件开发经济学和最终用户容忍度有关，而很少与编程语言或方法论有关。更好的标准也许是衡量有多少项目延期，或交付时大幅削减功能。

至于“单元测试可以替代强类型”的说法，可以考虑强类型语言中一种常见重构：改变某个函数参数的类型。在强类型语言里，只需修改该函数声明，然后修复所有构建失败点。在弱类型语言中，函数现在期待不同数据这一事实无法传播到调用点。单元测试也许能捕获一部分不匹配，但测试几乎总是概率性的，而不是确定性的。测试是证明的糟糕替代品。

2.3 类型是什么？（What Are Types?）

关于类型最简单的直觉是：类型是一组值。类型 Boolean 是包含 true 和 false 的二元素集合。类型 Char 是所有 Unicode 字符组成的集合，例如 a 或 ą。

集合可以是有限的，也可以是无限的。String 类型可以看作字符列表的同义说法，它就是无限集合的例子。

当我们声明 x 是一个 BigInt 时：

val x: BigInt

意思是说，它是整数集合中的一个元素。Scala 的 BigInt 可以用于任意精度算术。也存在对应机器类型的有限集合，例如 Int，类似 C++ 中的 int。

把类型与集合等同起来有一些微妙之处。多态函数会遇到循环定义问题，也不能拥有“所有集合的集合”。不过，正如我承诺的，我不会在数学细节上过分苛刻。好消息是，存在一个集合范畴，称为 $Set$，我们会直接使用它。在 $Set$ 中，对象是集合，态射（箭头）是函数。

$Set$ 是一个非常特殊的范畴，因为我们确实可以窥视它的对象内部，并由此获得许多直觉。例如，我们知道空集没有元素。我们知道存在特殊的单元素集合。我们知道函数把一个集合的元素映射到另一个集合的元素。它们可以把两个元素映射到一个元素，但不能把一个元素映射到两个元素。我们知道恒等函数把集合中的每个元素映射到自身，等等。接下来的计划是逐渐忘掉所有这些信息，转而用纯粹的范畴论术语表达这些概念，也就是用对象和箭头来表达。

在理想世界中，我们可以直接说：Haskell 类型是集合，Haskell 函数是集合之间的数学函数。但这里有一个小问题：数学函数并不执行任何代码，它只是“知道”答案。Haskell 函数则必须计算答案。如果答案能在有限步内获得，那没有问题，无论步数多大都可以。但有些计算涉及递归，可能永远不会终止。我们不能简单禁止 Haskell 中的非终止函数，因为区分终止函数与非终止函数是不可判定的，这就是著名的停机问题。因此，计算机科学家提出了一个绝妙想法，或者说一个大 hack，取决于你的视角：给每个类型都扩展一个特殊值，称为底（bottom），通常记作 _|_，或 Unicode 符号 $\bot$。这个“值”对应非终止计算。

因此，声明为：

val f: Boolean => Boolean

的函数可能返回 true、false 或 _|_；最后一种情况意味着它永远不会终止。

有趣的是，一旦接受底作为类型系统的一部分，把每个运行时错误也视为底就很方便，甚至可以允许函数显式返回底。后者通常通过类似 ??? 的表达式完成：

val f: Boolean => Boolean = x => ???

这个定义能够通过类型检查，因为 ??? 求值为底，而底是任意类型的成员，包括 Boolean。甚至可以写：

def f: Boolean => Boolean = ???

这里没有 x，因为底同样也是 Boolean => Boolean 类型的成员。

可能返回底的函数称为部分函数（partial functions），与之相对的是全函数（total functions），后者会对每个可能参数返回有效结果。

由于底的存在，你会看到 Haskell 类型与函数构成的范畴被称为 $Hask$，而不是 $Set$。从理论角度看，这是无穷无尽复杂性的来源，所以此刻我会拿出屠刀，终止这条推理线。从实用角度看，忽略非终止函数和底，把 $Hask$ 当成真正的 $Set$ 是可以的。Nils Anders Danielsson、John Hughes、Patrik Jansson 和 Jeremy Gibbons 的论文 Fast and Loose Reasoning is Morally Correct 为在多数上下文中忽略底提供了依据。

2.4 为什么需要数学模型？（Why Do We Need a Mathematical Model?）

作为程序员，你非常熟悉自己编程语言的语法和文法。语言规范通常一开始就会用形式化记法描述这些方面。但语言的含义，也就是语义，要难描述得多；它需要更多页数，形式化程度很少足够高，而且几乎从不完整。因此，语言律师之间有永无止境的讨论，也催生了大量专门阐释语言标准细节的书。

确实存在描述语言语义的形式化工具，但由于它们复杂，主要用于简化的学术语言，而不是现实中的编程巨兽。其中一种工具叫操作语义（operational semantics），它描述程序执行机制。它定义一个形式化的理想解释器。工业语言如 C++ 的语义，通常用非正式的操作推理描述，经常以某种“抽象机器”为基础。

问题在于，使用操作语义证明程序性质非常困难。为了展示程序的某个性质，本质上必须让它在理想解释器中“运行”。

程序员从不进行形式化正确性证明，这并不重要。我们总是“认为”自己写的是正确程序。没人坐在键盘前说：“噢，我就随便扔几行代码看看会发生什么。”我们认为自己写的代码会执行某些动作，并产生期望结果。当它没有做到时，我们通常会很惊讶。这意味着我们确实在推理自己写的程序，只不过通常是在头脑中运行解释器。问题是，跟踪所有变量真的很难。计算机擅长运行程序，人类并不擅长！如果我们擅长，就不需要计算机了。

不过，还有另一种选择。它叫指称语义（denotational semantics），以数学为基础。在指称语义中，每个编程构造都会被赋予数学解释。这样，如果你想证明程序的某个性质，只需证明一个数学定理。你也许会觉得证明定理很难，但事实是，人类已经积累了数千年的数学方法，有大量知识可以利用。而且，与职业数学家证明的定理相比，我们在编程中遇到的问题通常相当简单，甚至平凡。

考虑 Scala 中阶乘函数的定义：

val fact = (n: Int) => (1 to n).product

表达式 1 to n 是从 1 到 n 的整数序列。函数 product 会把序列中的所有元素相乘。这几乎就像数学教材中的阶乘定义。再与 C 代码比较：

int fact(int n) {
    int i;
    int result = 1;
    for (i = 2; i <= n; ++i)
        result *= i;
    return result;
}

还需要多说吗？

好吧，我第一个承认这是一次廉价攻击！阶乘函数有显然的数学指称。敏锐的读者也许会问：从键盘读取一个字符，或通过网络发送一个数据包，这些操作的数学模型是什么？很长一段时间里，这都是一个尴尬问题，会引出相当曲折的解释。看起来，对于许多编写有用程序所必需的重要任务，指称语义并不是最合适的工具；而这些任务很容易用操作语义处理。突破来自范畴论。Eugenio Moggi 发现，计算效果可以映射到单子。这是一个重要观察，不仅让指称语义重获新生，让纯函数式程序更加实用，也为传统编程投下了新的光。等我们发展出更多范畴论工具之后，会再讨论单子。

拥有编程数学模型的一个重要优点是，可以对软件正确性进行形式化证明。编写消费级软件时，这也许看起来没那么重要；但在某些编程领域，失败代价可能极高，甚至关乎生命安全。即便是在为医疗系统编写 Web 应用，你也会欣赏这样一个事实：Haskell 标准库中的函数和算法附带正确性证明。

2.5 纯函数与脏函数（Pure and Dirty Functions）

我们在 C++ 或其他命令式语言中称为函数的东西，并不等同于数学家所说的函数。数学函数只是从值到值的映射。

我们可以在编程语言中实现数学函数：给定输入值，这样的函数会计算输出值。生成一个数字平方的函数，可能会把输入值乘以自身。每次调用它时都会这么做，并且保证在相同输入下每次产生相同输出。一个数的平方不会随月相改变。

另外，计算一个数字的平方，不应该产生给你的狗发放美味奖励的副作用。会做这种事的“函数”不能轻易建模为数学函数。

在编程语言中，给定相同输入总是产生相同结果，并且没有副作用的函数称为纯函数（pure functions）。在 Haskell 这样的纯函数式语言中，所有函数都是纯的。正因为如此，更容易为这些语言赋予指称语义，并用范畴论建模。至于其他语言，我们总可以把自己限制在纯子集上，或者单独推理副作用。稍后会看到，单子如何让我们只用纯函数建模各种效果。因此，把自己限制在数学函数上并不会真正失去什么。

2.6 类型示例（Examples of Types）

一旦意识到类型是集合，就可以思考一些相当特别的类型。例如，对应空集的类型是什么？不，它不是 C++ 的 void，虽然在 Haskell 中这个类型确实叫 Void。它是没有任何值栖居的类型。你可以定义一个接收 Void 的函数，但永远无法调用它。要调用它，就必须提供一个 Void 类型的值，而这种值根本不存在。至于这个函数能返回什么，则没有任何限制。它可以返回任意类型，虽然它永远不会真的返回，因为它无法被调用。换句话说，它是一个返回类型多态的函数。Haskell 程序员给它起了个名字：

def absurd[A]: Nothing => A

记住，A 是类型变量，可以代表任意类型。这个名字并非巧合。类型与函数在逻辑上有更深的解释，称为 Curry-Howard 同构。类型 Nothing 表示假，函数 absurd 的类型对应“从假可以推出任何东西”这一命题，也就是拉丁格言 ex falso sequitur quodlibet。

接下来是对应单元素集合的类型。它只有一个可能值。这个值只是“存在”。你可能不会立刻认出它，但这就是 C++ 的 void。思考从这个类型出发和到这个类型的函数。来自 void 的函数总是可以被调用。如果它是纯函数，就总会返回相同结果。下面是这种函数的例子：

int f44() { return 44; }

你也许会认为这个函数接收“什么都没有”，但我们刚刚看到，真正接收“什么都没有”的函数永远不能被调用，因为没有值能表示“什么都没有”。那么这个函数接收什么？概念上，它接收一个哑值，而这个哑值永远只有一个实例，因此不必显式提到它。在 Scala 中，这个类型叫 Unit，它唯一的值也写作 ()。因此，下面是这个函数的 Scala 版本：

val f44: Unit => BigInt = _ => 44

这行代码声明 f44 接收 Unit 并返回 BigInt。调用它时提供 unit 值 ()。

f44(())

注意，每个从 unit 出发的函数都等价于从目标类型中选取一个元素。这里，它选取的是 BigInt 值 44。事实上，可以把 f44 看成数字 44 的另一种表示。这说明，我们可以不显式提到集合元素，而改为讨论函数（箭头）。从 unit 到任意类型 $A$ 的函数，与集合 $A$ 的元素一一对应。

那么返回类型为 void，或在 Scala 中返回类型为 Unit 的函数呢？在 C++ 中，这类函数用于副作用；但我们知道，在数学意义上，它们不是真正的函数。一个返回 unit 的纯函数什么都不做：它丢弃参数。

从数学上说，从集合 $A$ 到单元素集合的函数，会把 $A$ 的每个元素映射到这个单元素集合中的唯一元素。对每个 $A$，恰好存在一个这样的函数。下面是 BigInt 的例子：

val fInt: BigInt => Unit = x => ()

给它任意整数，它都会返回 unit。本着简洁精神，可以使用通配符 _ 表示被丢弃的参数，这样就不用为它发明名字：

val fInt: BigInt => Unit = _ => ()

注意，这个函数的实现不仅不依赖传入的值，甚至不依赖参数类型。

可以对任意类型使用相同公式实现的函数，称为参数多态函数。你可以用类型参数替代具体类型，用一个等式实现一整个函数族。那么，从任意类型到 unit 类型的多态函数应该叫什么？当然叫 unit：

def unit[A]: A => Unit = _ => ()

在 C++ 中，你会把这个函数写成：

template<typename T>
void unit(T) {}

类型谱系中的下一个是二元素集合。在 C++ 中它叫 bool；在 Haskell 中它叫 Bool；在 Scala 中则是 Boolean。区别在于，C++ 的 bool 是内建类型，而在函数式风格里，可以用代数数据类型定义一个类似类型：

sealed trait Bool
case object True extends Bool
case object False extends Bool

可以把这个定义读作：Bool 要么是 True，要么是 False。原则上，也可以在 C++ 中把布尔类型定义成枚举：

enum bool {
    true,
    false
};

但 C++ 的 enum 暗中仍是整数。C++11 的 enum class 本可以用于这里，但那样就必须用类名限定它的值，例如 bool::true 和 bool::false，更不用说还要在每个使用它的文件中包含合适头文件。

从 Bool 出发的纯函数，只是从目标类型中选取两个值：一个对应 True，另一个对应 False。

到 Bool 的函数称为谓词（predicates）。例如，Haskell 库 Data.Char 中充满了 isAlpha 或 isDigit 这样的谓词。在 C++ 中有类似库定义 isalpha、isdigit 等函数，不过它们返回的是 int 而不是布尔值。真正的谓词定义在 std::ctype 中，形式类似 ctype::is(alpha, c)、ctype::is(digit, c) 等。

挑战

1. 在你最喜欢的语言中定义一个高阶函数（或函数对象）memoize。这个函数接收一个纯函数 f 作为参数，并返回一个行为几乎与 f 完全相同的函数；区别在于，对每个参数，它只调用原函数一次，把结果保存在内部，之后使用相同参数调用时都返回这个保存的结果。你可以通过观察性能区分记忆化函数和原函数。例如，试着记忆化一个求值耗时很长的函数。第一次用某个参数调用时必须等待结果，但之后用同一参数调用时，应该立刻得到结果。
2. 试着记忆化一个你通常用于生成随机数的标准库函数。它能工作吗？
3. 大多数随机数生成器都可以用种子初始化。实现一个函数，它接收种子，用该种子调用随机数生成器，并返回结果。记忆化这个函数。它能工作吗？
4. 下面这些 C++ 函数哪些是纯的？试着记忆化它们，并观察在记忆化和未记忆化情况下多次调用时会发生什么：

// a. 正文示例中的阶乘函数。

// b.
std::getchar()

// c.
bool f() {
    std::cout << "Hello!" << std::endl;
    return true;
}

// d.
int f(int x) {
    static int y = 0;
    y += x;
    return y;
}

1. 从 Bool 到 Bool 有多少个不同函数？你能把它们全部实现出来吗？
2. 画出一个范畴，其中唯一对象是类型 Void、()（unit）和 Bool，箭头对应这些类型之间所有可能的函数。用函数名标注这些箭头。