函数式编程：代码中的数学结构

函数的基本概念：从加运算说起

函数定义

在数学上，我们已经习惯书写 $1 + 2 + 3 + 4$ 这种表达式。尽管看起来非常普通，但这个表达式里其实已经包含了非常多函数式编程的重要思想。

好吧，你可能会说，这里面哪有函数呢？其实 $+$ 就是一个二元函数，可以等价为 $\operatorname{add}$

$\operatorname{add}$ 输入两个实数，输出一个实数。我们可以用符号表示为

在 Javascript 里可以这样定义

function add(x, y) {
  return x + y;
}

或者使用箭头函数

const add = (x, y) => x + y;

有了 add 后，就可以改写原来的表达式

add(1, add(2, add(3, 4)));

可以看到，虽然表达式变得更加复杂，但计算结果是一样的。

不过，这里存在一些细微的差异：计算顺序不相同。$+$ 通常默认为左结合，即从左到右，从 $1$ 到 $4$；而我们的函数嵌套表达式其实是从右到左，从 $4$ 到 $1$。如果要改为从 $1$ 到 $4$，需要写成如下形式

add(add(add(1, 2), 3), 4);

函数的类型

$+$、$-$（减运算）、$\times$、$\div$ 都是二元函数，即接受两个参数并返回一个值。它们可以统一表示为

这里需要区分几个概念

• 声明定义域：函数声明的输入集合
• 实际定义域：函数实际能够接受的输入集合
• 陪域：函数声明的输出集合
• 值域：函数实际能够取到的输出集合

在数学上通常不区分声明定义域和实际定义域，而只说定义域——此时指的其实是实际定义域，因为数学函数要求在定义域的每个元素上都有定义；而值域在数学里也比陪域更多见。

但在函数式编程里，更常用的是声明定义域和陪域，函数实际的输入集合与输出集合反而较少关心——因为这些可能涉及程序的运行时状态，不方便静态分析。

上面的函数中，除 $\div$ 外声明的集合都和实际的集合相同；而 $\div$ 的第二个操作数是除数，不能为 $0$，所以它的实际定义域是 $(\mathbb{R},\mathbb{R}^*)$。其中 $\mathbb{R}^*$ 表示 $\mathbb{R}$ 除去 $0$ 这一元素，即 $\mathbb{R}^*=\mathbb{R} \setminus \set{0}$。

而 $-$（取负运算）、$\sin$、$\cos$、$\log$（底数为 $e$）、$\exp$（底数为 $e$）都是一元函数，可以表示为

这里声明的集合与实际的集合之间也存在区别

• $\log$ 只能作用在正实数上，因此实际的输入集合是 $\mathbb{R^+}$
• $\exp$ 的结果只可能为正实数，因此实际的输出集合是 $\mathbb{R}^+$
• $\sin$ 和 $\cos$ 的结果绝对值不大于 $1$，因此实际的输出集合是 $[-1, 1]$

在实际编程中，我们会面对非常多的类型。

比如在 TypeScript 中就有 number / string / boolean / null / undefined 等基础类型，T[] / [T1, T2] / { p1: T1; p2: T2 } / T1 | T2 等复合类型，以及直接把字面量作为类型的字面量类型。函数同样也有类型，它的类型由参数类型和返回值类型共同决定

function parseInteger(s: string) {
  return /^\d+$/.test(s) ? Number(s) : "请输入非负整数";
}

上述函数的类型就是 string => number | "请输入非负整数"，即参数类型为 string，值类型可能是 number，也可能是字面量 "请输入非负整数"。

函数类型的主要用处，就是推导函数之间能否组合，以及组合后得到的函数是什么类型。

函数的组合

现实世界中的函数是无穷无尽的，因为函数之间可以组合，而函数的组合可以得到新的函数。

我们先考虑数学中的例子。我们定义一个一元函数

使用 add、sub、mul、div 改写，以便更清晰地看出函数组合的本质

function f(x) {
  return div(add(x, 1), sub(mul(x, x), 1));
}

其中 mul 的值被作为 sub 的参数，而 add 和 sub 的值又作为 div 的参数。这就引出了函数组合需要满足的要求：只有当一个函数的返回值可以匹配另一个函数的参数时，才可以把前者的输出作为后者的输入。

上述例子中，输出是可以匹配输入的。

div 第二个参数实际只接受 $\mathbb{R}^*$，而这个位置是 sub 的返回值，因此 sub 的返回值被限制为 $\mathbb{R}^*$。但在不考虑 div 的情况下，子表达式 sub(mul(x, x), 1) 实际的输出集合是 $[-1, +\infty)$。这两个集合并不相同，在数学上，我们可以用差集判断哪些输入非法，用交集判断哪些输入合法

• 由于 $[-1, +\infty) \setminus \mathbb{R}^* = \set{0}$，因此 $\set{0}$ 不能用作 div 的输入或 sub 的输出
• 由于 $[-1, +\infty) \cap \mathbb{R}^*= [-1, 0) \cup (0, +\infty)$，因此 $[-1, 0) \cup (0, +\infty)$ 可以用作 div 的输入和 sub 的输出

经过一番推理后，我们最终可以确定这个函数实际的输入和输出集合为

现在我们构造一个特殊的例子，看看当输出不匹配输入时会发生什么

1. $\exp$ 的实际输入和输出为 $\mathbb{R} \to \mathbb{R}^+$，因此 $\mathbb{R}$ 被映射到 $\mathbb{R}^+$
2. $-$ 的输入接上 $\exp$ 的输出 $\mathbb{R}^+$，而 $-$ 在 $\mathbb{R}^+$ 上的像集为 $\mathbb{R}^-$，因此 $\mathbb{R}^+$ 被映射到 $\mathbb{R}^-$
3. $\log$ 的输入接上 $-$ 的输出 $\mathbb{R}^-$，但 $\log$ 实际只接受 $\mathbb{R}^+$，而 $\mathbb{R}^+ \cap \mathbb{R}^- = \empty$，因此不存在合法的输入

最后我们发现，任何 $x \in \mathbb{R}$ 都无法作为 $f$ 的输入。因此在实数范围内，这种组合是失败的。用数学的说法，这叫定义域为空。

在实际编程里，函数类型的推导与之类似。

比如 TypeScript 可以根据函数声明的参数类型，自动推导出返回值的类型；但这种类型推导显然不会像刚才的分析那样对类型中的每个值都进行验证，而只会在声明的输入类型上进行类型层面的推导。

这是一个 TypeScript 中的例子

const getLength = (s: string): number => s.length;
const isBig = (n: number): boolean => n > 32;

这两个函数分别对应类型

如果把 getLength 的返回值作为 isBig 的参数

const isLongString = (s: string) => isBig(getLength(s));

由于两者类型都是 number，因此可以进行组合，并且 TypeScript 能够推断出 isLongString 的类型应该为

但反过来把 isBig 的返回值作为 getLength 的参数就存在问题

const bad = (n: number) => getLength(isBig(n));

这里 isBig 的返回值是 boolean 而 getLength 的参数为 string，类型不匹配。因此无法这样组合。

描述函数的符号：范畴论、类型论、集合论

数学中常用的语言是集合论，但在函数式编程里，更常用的是类型论和范畴论。

本文不会详细介绍范畴论和类型论，不过作为一种入门直觉，可以用集合论进行概念上的类比

比如指数函数 $\exp(x) = e^x$，在集合论里这是一个从实数集合 $\mathbb{R}$ 到正实数集合 $\mathbb{R}^+$ 的映射

在类型论里，这是函数类型 $\text{Real} \to \text{PositiveReal}$ 中的一个项

或者表示为

而在 $\mathbf{Set}$ 范畴中，这是从对象 $A$ 到对象 $B$ 的态射

在笛卡尔闭范畴里，还可以表示为从全局元素 $1$ 到指数对象 $B^A$ 的态射

函数复合与管道：将多个函数连接成一个函数

管道和函数复合密切相关。我们先介绍函数复合。

函数复合的数学定义

数学上，函数复合是一种特殊的函数组合。有这样一组一元函数

我们希望先计算 $f$，再计算 $g$，最后计算 $h$，即

那么这个组合出来的函数需要这样写

如果再多计算几个函数，这种嵌套会变得非常复杂，难以阅读。数学上可以使用函数复合来简化此时的函数组合

复合的顺序是从右到左，且满足结合律

函数复合得到的结果是一个新的函数。这个新的函数可以接受一个参数，等价于原先的写法

管道的数学定义

而管道几乎就只是给函数复合换了个符号和顺序：管道的顺序是从左到右，而函数复合是从右到左

而最初送入管道的值，通常就放到管道的最左边

管道在编程语言里比较常见的符号是 | 和 |>。另外一些语言的链式调用 object.f().g().h() 也可以看作一种管道符号，虽然写法上是面向对象的，但计算模型上却是函数式的。

管道示例：Bash

管道出现在许多语言里。比如 Bash 的管道

cat server.log \
  | grep "ERROR" \
  | sort \
  | uniq -c

这可以被理解为

uniq_count(sort(grep_error(cat("server.log"))));

每个函数（bash 中的术语是命令）的输入是文本，输出也是文本，因此每个函数都是

这满足了函数复合的要求——前一个函数的输出匹配下一个函数的输入。因此各种 UNIX 工具才可以自由组合。

管道示例：SQL

一些 SQL 方言也支持管道语法，比如 GoogleSQL

FROM users
|> WHERE age >= 18
|> AGGREGATE COUNT(*) AS user_count
   GROUP BY age
|> WHERE user_count >= 100
|> ORDER BY age DESC
|> LIMIT 10;

SQL 的每个函数（SQL 中的术语是操作）都接收表，然后返回表

于是 GoogleSQL 里的操作就可以自由组合，不会发生普通 SQL 里 AGGREGATE 聚合之后再筛选时只能用 HAVING 不能用 WHERE 的问题。

管道示例：jq

jq 语言里也存在大量的管道

.users[]
| select(.age >= 18)
| .name

jq 的每个函数（jq 中的术语是过滤器）都接受 JSON，然后返回零个、一个或多个 JSON

因此 jq 中有时候需要用 [filter] 等方法让 $\operatorname{Stream}(\text{JSON})$ 重新变回 $\text{JSON}$，以便后续的管道能够将输入当成单个 JSON 处理。

管道示例：Haskell

Haskell 里可以使用 & 作为管道操作符

import Data.Function ((&))

3 & (+1) & (*2) & show

或者不用标准库，自己实现一个管道 |>

x |> f = f x

3 |> (+1) |> (*2) |> show

不过 Haskell 中的函数复合更值得拿出来说明

sumSquaresOfEvens :: [Int] -> Int
sumSquaresOfEvens = sum . map (^2) . filter even

Haskell 的管道从左到右，但函数复合从右到左，且语法完全照搬数学上的写法，连符号都很相似

这些函数的类型分别为

filter even :: [Int] -> [Int]
map (^2)    :: [Int] -> [Int]
sum         :: [Int] -> Int

复合的完整过程为

所以这些函数可以把输入输出连接起来，复合成一个函数。

管道示例：Java

虽然 Java 是一门面向对象语言，但链式调用本身却非常的函数式

users.stream()
    .filter(User::isActive)
    .map(User::getName)
    .sorted()
    .toList();

这里的实际含义是，在 users 对象上调用 stream()，然后再在 stream() 返回的对象上调用 filter(User::isActive)，并重复这个过程到 toList() 调用完成。虽然语法建立在面向对象的基础上，但思维却非常的函数式

这完全就是前面提到的管道。

管道示例：JavaScript

在 JavaScript 里同样有链式调用

[1, 2, 3, 4, 5, 6]
  .filter((n) => n % 2 === 0)
  .map((n) => n * 10)
  .reduce((a, b) => a + b, 0);
// 120

其中的类型变化是 number[] => number[] => number[] => number。

JavaScript 目前还没有原生的管道语法，不过可以自己手动实现一个简易的 pipe

function pipe(...fns) {
  return (x) => fns.reduce((v, fn) => fn(v), x);
}

这里 pipe 本身是一个函数，它的参数是函数，返回值也是函数。这叫做高阶函数——我们马上就会讲到。pipe 调用后返回一个函数，再调用返回的函数就能得到值

pipe(Math.floor, Math.sqrt, Math.round)(3.7); // 2
pipe(Number, Math.sqrt, Math.round)(" 42 "); // 6

如果想让 pipe 的第一个参数是进入管道的初始值，可以这样修改

function pipe(x, ...fns) {
  return fns.reduce((v, fn) => fn(v), x);
}

然后调用

pipe(3.7, Math.floor, Math.sqrt, Math.round); // 2
pipe(" 42 ", Number, Math.sqrt, Math.round); // 6

高阶函数：函数族、泛函与算子

接下来要介绍的就是函数式编程中相对抽象，但非常重要的概念——高阶函数。

高阶函数指的是参数或返回值中含有函数的函数。为了建立数学直觉，我们先通过三类常见的数学对象——函数族、泛函和算子——来理解高阶函数。

函数族

函数族的输入是数，输出是函数。

在数学上，典型的函数族就是对数函数族

对数函数族接受一个底数，然后返回一个对数函数。不过数学上对底数有一些要求，因此其实际类型为

所有对数函数都可以通过 $\operatorname{Log}$ 函数族生成出来。而对于那些常用的对数函数，数学中都有别名

对返回的函数进行调用就能得到值，这可以等价为对原来的函数族调用两次

指数函数族也可以这样表示，通过接受底数，返回一个指数函数

实际类型可以表示为

在 JavaScript 里可以如下定义函数族

const Log = (a) => (x) => Math.log(x) / Math.log(a);

然后通过这个函数族生成一连串函数并调用

const ln = Log(Math.E);
const lg = Log(10);

lg(1000);
Log(10)(1000);

Haskell 可以这样写

logFamily :: Floating a => a -> a -> a
logFamily a x = log x / log a

ln = logFamily (exp 1)
log10 = logFamily 10

log10 1000
logFamily 10 1000

当然对于 Haskell，标准库里其实已经有了对数函数族 logBase，直接用就行

log10 = logBase 10
log10 1000
logBase 10 1000

泛函

泛函的输入是函数，输出是数。

在数学上，典型的泛函就是定积分

数学上通常用 $C(\mathbb{R})$ 表示 $\mathbb{R} \to \mathbb{R}$ 上的连续函数，因此定积分泛函的类型为

一个定积分泛函的示例如下

把这个泛函作用于函数，就能得到其在 $[0, 1]$ 区间上的积分

Haskell 的标准库里没有积分，我们先实现一个简单的数值积分

integrate :: Double -> Double -> (Double -> Double) -> Double
integrate a b f =
  let n  = 10000
      dx = (b - a) / fromIntegral n
  in sum [f (a + (fromIntegral i + 0.5) * dx) * dx | i <- [0 .. n - 1]]

然后可以这样表示区间 $[0, 1]$ 上的定积分泛函

integralFrom0To1 :: (Double -> Double) -> Double
integralFrom0To1 f = integrate 0 1 f

最后给这泛函一个函数，就会返回其在 $[0, 1]$ 上定积分的结果。由于数值积分的精度问题，结果不完全准确

ghci> integralFrom0To1 (\x -> 2 * x)
0.9999999999999998
ghci> integralFrom0To1 sin
0.45969769432340096
ghci> integralFrom0To1 cos
0.8414709851585067

算子

算子的输入和输出都是函数。

在数学上，典型的算子就是求导算子

数学上通常用 $C^1(\mathbb{R})$ 表示 $\mathbb{R} \to \mathbb{R}$ 上的一阶连续可微函数。因此求导算子的类型为

求导算子接受一个函数，然后返回其导函数，比如

变限积分也是一个算子，这是一种上限或下限不固定的积分。比如变上限积分

其类型是

变限积分接受一个函数，返回其原函数。比如

在 Haskell 的标准库里没有微分，我们先定义一个简单的数值微分

derivative :: (Double -> Double) -> (Double -> Double)
derivative f = \x ->
    let h = 1e-6
    in (f (x + h) - f (x - h)) / (2 * h)

然后对 $x^2$ 运用求导算子

square' = derivative (\x -> x * x)

得到的就是其导函数 $2x$。不过由于数值微分的精度问题，不完全准确

ghci> square' 2
4.000000000115023
ghci> square' 3
6.000000000838668
ghci> square' 4
8.000000000230045
ghci> square' 5
10.00000000139778

对于变上限积分也一样。还是使用之前编写的数值积分

integrate :: Double -> Double -> (Double -> Double) -> Double
integrate a b f =
  let n  = 10000
      dx = (b - a) / fromIntegral n
  in sum [f (a + (fromIntegral i + 0.5) * dx) * dx | i <- [0 .. n - 1]]

这里第一个参数是下限，第二个参数是上限，第三个参数是函数。我们要交换一下变量顺序，让下限的后一个参数是函数

integralFromLower :: Double -> (Double -> Double) -> (Double -> Double)
integralFromLower a f x = integrate a x f

现在我们就得到了变上限积分算子

integralFromLower0 :: (Double -> Double) -> (Double -> Double)
integralFromLower0 = integralFromLower 0

然后对 $2x$ 运用变上限积分算子

square = integralFromLower0 (\x -> 2 * x)

得到的函数就是 $x^2$。不过由于数值积分的精度问题，结果不完全准确

ghci> square 2
3.999999999999999
ghci> square 3
9.0
ghci> square 4
15.999999999999996
ghci> square 5
25.0

更一般的高阶函数

前面提到的只是数学上比较典型的高阶函数，而实际的高阶函数远远不止这几种。

比如，数学上的不定积分接受一个函数，然后返回其原函数族

这里 $F(x)+C$ 就是之前提到的函数族，指定了参数 $C$ 后才能得到唯一的原函数。因此 $F(x)+C$ 的类型为 $\mathbb{R} \to C^1(\mathbb{R})$。

而不定积分返回这个函数族，类型可写为

比如

在指定 $C$ 后就能确定唯一的原函数。

对于代码示例，我们沿用之前在 Haskell 里实现的简单数值积分

integrate :: Double -> Double -> (Double -> Double) -> Double
integrate a b f =
  let n  = 10000
      dx = (b - a) / fromIntegral n
  in sum [f (a + (fromIntegral i + 0.5) * dx) * dx | i <- [0 .. n - 1]]

这里第一个参数是下限，第二个参数是上限，第三个参数是函数。我们需要修改一下参数顺序

integralIndefinite :: (Double -> Double) -> Double -> Double -> Double
integralIndefinite f c x = integrate 0 x f + c

我们可以测试几个示例

ghci> cosF = integralIndefinite cos 0
ghci> cosF 0
0.0
ghci> cosF 1
0.8414709851585067
ghci> cosF 2
0.9092974283411775
ghci> cosF pi
1.0728180496744066e-16
ghci> cosF (pi/2)
1.0000000010280823

在编程里，高阶函数非常多见。像前面提到的函数复合 pipe 就是一个高阶函数，接受两个函数，返回复合后的函数，其类型可以表示为

后文将要提到的柯里化 curry 和反柯里化 uncurry 也是高阶函数。可以说，编程中所有对函数做变换的函数，以及用来构造函数的函数，都是高阶函数。

柯里化：把多元函数转为一连串的一元函数

柯里化的数学定义

对于一般的二元函数

可以被柯里化为

也可以把已经柯里化的函数

反柯里化为

用集合论解释就是，从 $A \times B$ 映射到 $C$ 的所有函数组成的函数空间，与从 $A$ 映射到 $\operatorname{Hom}(B, C)=\Set{f\mid f: B \to C}$ 的所有函数组成的函数空间同构

而在范畴论黑话里，这通常表述为：在笛卡尔闭范畴 $\mathcal C$ 上，对每个对象 $B$，积函子 $(-\times B): \mathcal C \to \mathcal C$ 是幂函子 $(-)^B: \mathcal C \to \mathcal C$ 的左伴随

正如前面说到的，$\operatorname{curry}$ 本身也是一个高阶函数：接受未柯里化的函数，然后返回柯里化的函数。其类型可以表示为

更一般地，任意一个多元函数

都可以被柯里化为一连串一元函数

柯里化示例：对数和指数

对于这样一个表达式

显然我们需要同时知道 $a$ 和 $x$ 的值，才能得知结果。因此，对数运算其实是一个二元函数

我们定义

把参数 $(\mathbb{R}, \mathbb{R})$ 改写成笛卡尔积的形式 $\mathbb{R} \times \mathbb{R}$，于是 $\operatorname{Log}$ 的类型为

但此前介绍函数族的时候，我们已经发现：我们通常都会固定底数，得到那些常用的对数函数

在这里 $\operatorname{Log}$ 接受一个参数，然后返回一个函数，其类型为

虽然这和我们最开始定义的类型不一样，但显然 $\operatorname{Log}$ 仍然表示相同的运算！因此我们可知这两种类型是同构的

也就是说，原先的二元函数 $\operatorname{Log}$，现在变成了一连串一元函数。

现在，我们可以只调用一次，得到一个常用的对数函数；也可以进行多次调用，直接得到结果

指数函数也是类似的。对于如下表达式

需要同时知道 $a$ 和 $x$ 的值才能计算出结果。因此指数运算是二元函数

但通过柯里化，我们可以先固定底数，得到那些常见的指数函数

柯里化示例：四则运算

四则运算这些二元函数也全都可以柯里化。就以加法为例，其通常被认为是一个二元函数

但通过柯里化，加法被转换为一连串一元函数

用 JavaScript 表示就是

// 未柯里化
const add = (x, y) => x + y;

// 柯里化
const add = (x) => (y) => x + y;

然后我们就可以一次只传一个参数，或者通过多次调用的方式一次传多个参数

const add5 = add(5);
add5(3);

add(5)(3);

柯里化示例：JavaScript

我们可以在 JavaScript 里自己实现一个简易的 curry

function curry(fn) {
  return function curried(...args) {
    if (args.length >= fn.length) {
      return fn.apply(this, args);
    }

    return function (...nextArgs) {
      return curried.apply(this, args.concat(nextArgs));
    };
  };
}

我们定义一个三元函数，测试一下效果

function add(a, b, c) {
  return a + b + c;
}

const curriedAdd = curry(add);

curriedAdd(1)(2)(3); // 6
curriedAdd(1, 2)(3); // 6
curriedAdd(1)(2, 3); // 6
curriedAdd(1, 2, 3); // 6

柯里化示例：Haskell

Haskell 的函数默认就是柯里化的形式，因此

add :: Int -> Int -> Int
add x y = x + y

表示类型

Haskell 的函数类型是右结合的，因此 Int -> Int -> Int 实际解析为

Int -> (Int -> Int)

Haskell 的函数应用是左结合的，因此 add 3 4 实际解析为

(add 3) 4

并且 Haskell 的标准库里已经实现了一个 curry 和 uncurry

ghci> :t curry
curry :: ((a, b) -> c) -> a -> b -> c
ghci> :t uncurry
uncurry :: (a -> b -> c) -> (a, b) -> c

柯里化的编程实践

柯里化不仅在数学上有非常优美的形式，而且在编程里也有很多好处。

显然，一个最直观的用途就是——让多元函数可以进入单参数的管道。

多元函数需要多个参数，因此在单参数的管道里，多元函数没办法把自己的输入接到任何函数的输出上。而柯里化可以把多元函数转变为一连串的一元函数，从而能够进入管道。

回顾之前提到的 Bash 管道示例

cat server.log \
  | grep "ERROR" \
  | sort \
  | uniq -c

在函数式的视角，我们可以认为 grep 其实是一个二元函数：第一个参数是模式字符串，第二个参数是待匹配的文本。而我们指定了第一个参数后，得到了一个一元函数，这个函数只需输入待匹配的文本，而文本现在就可以通过管道传进来。

柯里化能够让部分应用更方便。部分应用后文马上就会介绍，简要地说，部分应用通过提前固定一部分参数，得到一个更具体的函数。此后使用这个更具体的函数时就不需要重复传参，从而实现了参数复用。而且使用更具体的函数可以让代码更加声明式，此时只看函数名就能知道函数有什么用，不用考虑每个位置的参数是什么意思

const applyDiscount = (rate) => (price) => price * (1 - rate);
const vipDiscount = applyDiscount(0.2);

const prices = [100, 200, 300];
prices.map(vipDiscount);

函数包装：函数适配和函数装饰

函数包装指的是，创建一个新函数并在内部调用已有函数。

函数包装本身是个很宽泛的概念，我将其分为两种类型

1. 函数适配：改变原函数的调用方式，让其符合调用方的需要
2. 函数装饰：保持原函数的调用方式，只在外围增加额外行为

这两者之间没有特别清晰的分界，也不严格互斥，因此完全可以同时使用。

后文先介绍函数适配，再讲解函数装饰。

函数适配

柯里化本身就可以看作一种函数适配技术：调整参数结构，把多元函数变成一系列一元函数。

除此之外还有几种比较典型的函数适配技术：固定参数、重排参数、增加参数、转换返回值。当然，函数适配技术远不止这几种。

函数适配本身没什么深刻的数学原理，但体现了函数式编程中一个非常朴素又非常重要的思想：已有函数并不需要被修改；我们可以通过修改参数或返回值等操作，构造出具有新语义的函数。

函数适配技术：固定参数

固定参数也叫特化参数或者部分应用，这和柯里化密切相关。部分应用的正式定义是：在一个函数上先固定一部分参数，然后返回一个接受剩余参数的新函数。

以 $e$ 为底的对数函数就是一个典型的例子

我们先固定了底数，此后使用 $\ln$ 就不需要再指定底数了。

定积分也是一个部分应用的例子。回顾我们之前定义的数值积分

integrate :: Double -> Double -> (Double -> Double) -> Double
integrate a b f =
  let n  = 10000
      dx = (b - a) / fromIntegral n
  in sum [f (a + (fromIntegral i + 0.5) * dx) * dx | i <- [0 .. n - 1]]

代码中的数值算法不重要，这里需要关注的点是：我们把积分运算定义为一个三元函数，其中第一个参数是下限，第二个参数是上限，第三个参数是被积函数，返回值是定积分的结果

而定积分泛函就是只固定前两个参数

-- 区间 [0,1] 上的定积分泛函
integralFrom0To1 :: (Double -> Double) -> Double
integralFrom0To1 = integrate 0 1

即

函数适配技术：重排参数

重排参数指的是改变原函数的参数顺序，然后得到一个新的函数。

还是用之前定义的 integrate 举例，我们可以基于此适配一个变上限积分或者变下限积分

-- 下限为 0 的变上限积分
integralFrom0 :: (Double -> Double) -> (Double -> Double)
integralFrom0 f x = integrate 0 x f

-- 上限为 1 的变下限积分
integralTo1 :: (Double -> Double) -> (Double -> Double)
integralTo1 f x = integrate x 1 f

变上限积分固定了下限，变下限积分固定了上限，但这里我们还调整了参数顺序，从而让变上限积分和变下限积分的第一个参数是函数。

Haskell 里有多种调整参数顺序的方法，像这种重新定义是最直观的

integralFromLower a f x = integrate a x f
integralToUpper b f x = integrate x b f

对于二元函数，也可以使用 flip 交换参数顺序

integralFrom0 = flip (integrate 0)

函数适配技术：增加参数和转换返回值

增加参数指的是在原函数的基础上增加参数，而转换返回值指的是改变原函数的返回值。

继续用 integrate 举例，我们可以基于此定义一个不定积分

integralIndefinite :: (Double -> Double) -> Double -> Double -> Double
integralIndefinite f c x = (integrate 0 x f) + c

这里我们做了多件事情

• 固定参数，下限被固定为 0
• 重排参数，f 成为了 integralIndefinite 的第一个参数
• 增加参数，然后把增加的参数 c 加到返回值上

把这些步骤拆开可以看得更清晰一点——我们其实就是对之前定义的变上限积分函数做了点修改：添加了一个参数，然后把这个参数加到返回值中

integralFrom0 f x = integrate 0 x f
integralIndefinite f c x = (integralFrom0 f x) + c

这里我们指定了变上限积分的下限为 0。这个下限是随便选的，因为变上限积分公式允许下限是一个任意常数

而不定积分就是变上限积分得到的原函数加上积分常数 $C$。因此我们在 integrate 0 x f 得到的结果后加上 c。

函数装饰

函数装饰同样没什么深刻的数学原理，在编程里函数装饰只是很普通也很好理解的技术。

函数装饰通常使用函数装饰器实现，而函数装饰器可以看作一个高阶函数：接受一个函数，然后返回被装饰的函数。

后文介绍几种常见的函数装饰技术，包括前置处理、后置处理、调用拦截、调用控制、附加状态等。当然，函数装饰技术同样远不止这几种。

函数装饰技术：前置处理和后置处理

前置处理就是在函数调用前插入额外行为，后置处理就是在函数调用后插入额外行为。

在 JavaScript 里可以表示为

function decorate(f) {
  return (...args) => {
    before(args);

    const result = f(...args);

    after(result);
    return result;
  };
}

日志、计时、检查、清理等通常都会用到前置处理和后置处理。

函数装饰技术：调用拦截和调用控制

调用拦截会先判断是否调用原函数。

缓存、权限检查、短路、去重等都可以通过调用拦截实现。下面是一个用 JavaScript 实现缓存的例子

function cached(f) {
  const cache = new Map();

  return (x) => {
    if (cache.has(x)) return cache.get(x);

    const result = f(x);
    cache.set(x, result);
    return result;
  };
}

调用控制类似于调用拦截，会决定原函数何时调用、调用几次。

重试、防抖、节流、超时等都可以通过调用控制实现。下面是一个用 JavaScript 实现重试的例子

function retry(f, n) {
  return async (...args) => {
    let lastError;

    for (let i = 0; i < n; i++) {
      try {
        return await f(...args);
      } catch (error) {
        lastError = error;
      }
    }

    throw lastError;
  };
}

函数装饰技术：附加状态

附加状态可以让装饰后的函数拥有原函数没有的状态。

缓存实际上也属于附加状态这一类型。下面是用 JavaScript 实现调用计数的例子

function countCalls(f) {
  let count = 0;

  return (...args) => {
    count++;
    return f(...args);
  };
}

闭包：捕获环境中的自由变量

编程上的闭包和数学上的闭包完全不一样。

在数学上，闭包指的是：包含某个对象 $S$ 并且对某种运算 $*$ 封闭的最小对象

比如包含自然数并且对减法封闭的最小对象是整数，即自然数在减法运算下的闭包是整数

而编程里的闭包，其正式定义是：一个函数加上它定义时所处的词法环境。

听起来有点抽象，我们先看一个 JavaScript 示例，这个闭包示例在前面其实已经出现过，被用来实现柯里化和部分应用

const add = (x) => (y) => x + y;
const add5 = add(5);
add5(3); // 8

add 返回的函数 (y) => x + y 中参数只有 y，但函数体中却用到了 x。此时我们把 y 叫做这个函数的绑定变量，而 x 叫做自由变量。

调用 add(x) 返回的函数闭合了外层参数 x 的绑定。当调用 add(5) 时，绑定的值为 x = 5。

再来看一个示例

let x;
const add = (y) => x + y;

add(1); // NaN

x = 5;
add(1); // 6

x = 10;
add(1); // 11

当调用 add 时，函数在全局词法环境中寻找自由变量 x。第一次调用时 x 的值为 undefined，因此计算结果为 NaN；后续修改了 x 的值，由于闭包捕获的是变量的绑定而非变量的值，因此 add(1) 的返回值会随着 x 的变化而变化。

闭包可以用来实现函数的私有状态

function makeCounter() {
  let count = 0;
  return function () {
    count++;
    return count;
  };
}

const c1 = makeCounter();
c1(); // 1
c1(); // 2
c1(); // 3

const c2 = makeCounter();
c2(); // 1
c2(); // 2

调用 makeCounter() 返回的函数捕获了 makeCounter 词法作用域中的局部变量，且每次调用 makeCounter() 都能返回一个独立的闭包。

函数装饰器的实现也用到了闭包

function decorate(fn) {
  return function (...args) {
    // 前置处理
    const result = fn.apply(this, args);
    // 后置处理
    return result;
  };
}

每次调用 decorate(fn) 都会产生一个独立的闭包，而 fn 被这个闭包所捕获。

Haskell 里可以这样定义闭包

makeAdder x = \y -> x + y

add3 = makeAdder 3

其中自由变量 x = 3 被闭包 add3 捕获。

因为 Haskell 的函数都是柯里化的，所以上面的写法和下面的写法一样

makeAdder x y = x + y

函子：范畴之间的保结构映射

协变函子的数学定义

用类型论解释，一个协变函子包含两个部分：一部分是类型构造器 $F$，可以应用到类型上得到新的类型

另一部分是协变映射 $\operatorname{map}_F$，可以应用到函数上得到新的函数

在范畴论的语言里，前者 $A \mapsto F(A)$ 是对象映射，后者 $\operatorname{Hom}(A, B) \mapsto \operatorname{Hom}(F(A), F(B))$ 是态射映射。

协变函子必须满足两个函子律：一个是保持恒等态射，也就是恒等函数被映射为恒等函数，这里 $\operatorname{id}_A$ 表示 $A \to A$ 中的恒等函数，$\operatorname{id}_{F(A)}$ 表示 $F(A) \to F(A)$ 的恒等函数

另一个是保持复合，也就是先复合再映射和先映射再复合的结果相同

只有满足恒等律和复合律时 $(F, \operatorname{map}_F)$ 才构成一个协变函子。

逆变函子的数学定义

逆变函子和协变函子很类似，同样由类型构造器 $F$ 和映射 $\operatorname{contramap}_F$ 组成，只不过 $\operatorname{contramap}_F$ 是一个逆变映射——得到方向相反的函数

逆变函子同样要满足两个函子律，即恒等律

和复合律

协变函子示例：Maybe

听起来有点抽象，我们可以先看一个 TypeScript 中的例子

type Maybe<A> = { tag: "just"; value: A } | { tag: "nothing" };
// A => Maybe<A>

const mapMaybe =
  <A, B>(f: (a: A) => B) =>
  (m: Maybe<A>): Maybe<B> => {
    switch (m.tag) {
      case "nothing":
        return { tag: "nothing" };
      case "just":
        return { tag: "just", value: f(m.value) };
    }
  };
// (A => B) => Maybe<A> => Maybe<B>

这实现了一个 Maybe 函子，其中

• Maybe 是对象映射，把 number 变成 Maybe<number>
• mapMaybe 是态射映射，把 number -> number 变成 Maybe<number> -> Maybe<number>

然后可以如下使用

const inc = (n: number) => n + 1;
// number => number
const incMaybe = mapMaybe(inc);
// Maybe<number> => Maybe<number>

incMaybe({ tag: "just", value: 3 });
// { tag: "just", value: 4 }

incMaybe({ tag: "nothing" });
// { tag: "nothing" }

我们可以验证一下上述的示例，确实符合这两个函子律

const id = <A>(x: A): A => x;
mapMaybe(id);
// Maybe<A> => Maybe<A>

const compose =
  <A, B, C>(g: (b: B) => C, f: (a: A) => B) =>
  (a: A): C =>
    g(f(a));
const f = Math.sqrt;
const g = Math.round;
const x: Maybe<number> = { tag: "just", value: 3 };
mapMaybe(compose(g, f))(x);
// { tag: 'just', value: 2 }
compose(mapMaybe(g), mapMaybe(f))(x);
// { tag: 'just', value: 2 }

逆变函子示例：Predicate

我们可以用之前实现的协变函子 Maybe 构造一个逆变函子 Predicate

type Predicate<A> = (m: Maybe<A>) => boolean;
// A => Predicate<A>

const contramapPredicate =
  <A, B>(f: (a: A) => B) =>
  (pb: Predicate<B>): Predicate<A> =>
  (ma: Maybe<A>): boolean =>
    pb(mapMaybe(f)(ma));
// (A => B) => Predicate<B> => Predicate<A>

其中

• Predicate 是一个类型构造器，把类型 A 变为类型 Predicate<A>，而 Predicate<A> 是一个函数类型。
• contramapPredicate 是一个高阶函数，把函数 A => B 变为函数 Predicate<B> => Predicate<A>。

这个逆变函子可以如下使用

const lengthOf = (s: string): number => s.length;
// string => number

const predicateByLength = contramapPredicate(lengthOf);
// Predicate<number> => Predicate<string>

这里我们使用 contramapPredicate 把一个 string => number 函数变成了 Predicate<number> => Predicate<string> 函数，这个新的函数可以继续用来转换函数

const isSmallNumber: Predicate<number> = (m) => m.tag === "just" && m.value < 5;
// Predicate<number>
isSmallNumber({ tag: "just", value: 3 });
// true
isSmallNumber({ tag: "just", value: 10 });
// false
isSmallNumber({ tag: "just", value: "abc" });
// [ERROR]: Type 'string' is not assignable to type 'number'

const isShortString: Predicate<string> = predicateByLength(isSmallNumber);
// Predicate<string>
isShortString({ tag: "just", value: "abc" });
// true
isShortString({ tag: "just", value: "abcdefg" });
// false
isShortString({ tag: "just", value: 3 });
// [ERROR]: Type 'number' is not assignable to type 'string'

数学中的逆变函子：对偶函子

从向量空间 $V$ 到向量空间 $W$ 的所有线性映射构成的向量空间为

设 $V,W$ 是实向量空间，它们的对偶空间定义为

现在取一个线性映射 $f: V\to W$，对于任意一个 $W^*$ 中的余向量 $\omega: W \to \mathbb R$，$f$ 都可以和 $\omega$ 复合

复合的结果恰好在 $V^*$ 中

因此，若定义 $f$ 的对偶 $f^*$ 为与 $f$ 的前复合

便能得到

从而 $f^*$ 可表示为从 $W^*$ 到 $V^*$ 的映射

和 $f$ 放在一起对比

因此对偶操作 $(-)^*$ 在对象上定义为

在态射上定义为

由于 $f^*$ 反转了 $f$ 的箭头，所以对偶是一个逆变函子。

当然，还要验证对偶满足两条函子律。首先是恒等律，即恒等映射对偶后仍是恒等映射

其次是复合律，即先复合后对偶等于先对偶后复合

我们也可以直接用范畴论定义一个逆变函子来表示对偶函子。首先固定 $K$，然后定义类型构造器 $F$ 为

再定义逆变映射 $F$ 为

关于 $\operatorname{Hom}(f, K)$

虽然带入 $F(f)$ 可以得到 $\operatorname{Hom}(f, K)$，但这其实应该理解为

$$F(f)=[\operatorname{Hom}(-, K)](f)$$

$\operatorname{Hom}(-, K)$ 本身不可分割，只是数学里习惯复用 滥用 符号。

展开 $F(V)$ 和 $F(W)$

我们取一个 $g: W \to K$ 看看映射效果

这里 $F(f)(g)$ 的把 $g$ 输入变成了 $f$ 的输入，这恰好可以通过对 $g$ 进行与 $f$ 的前复合得到