跨卷导读：函数、复合、逆与增长

先把函数写成一份集合合同

函数不是只有“输入变输出”的箭头，也不是所有带参数的程序都天然是数学函数。它需要声明输入集合、输出集合和规则，并保证每一个允许输入恰好对应一个输出。作者目录中第1卷第4章《斐波那契数列和生成函数》会把这种关系用于数列与生成函数；本页再把它连接到复合、逆和算法增长。作者目录用于核对原书章节边界。

先预测：若两个程序都接受一个整数并返回一个整数，它们就一定可以任意复合吗？不一定。前一个结果必须满足后一个函数的输入合同；如果程序还依赖时间、随机源或文件状态，这些依赖也必须被建模，否则“同输入同输出”的数学保证并不存在。

定义域、陪域与像集

决定哪些输入可以被讨论； 陪域 是函数箭头声明的目标； 像集 是实际输出的集合。写作

时，$X$ 是定义域，$Y$ 是陪域，而 $f(X)$ 才是像集。三者分开，满射与逆函数的判断才不会出现歧义。

例如

是函数，因为每个实数都有唯一平方；但 $f(2)=f(-2)=4$，所以它不是单射，像集是 $[0,\infty)$，相对于陪域 $\mathbb R$ 也不是满射。如果改成

它才同时满足单射和满射，逆函数 $f^{-1}(y)=\sqrt y$ 的定义域也随之确定。

复合函数：中间类型必须接得上

若

则复合函数 $f\circ g$ 定义为先执行 $g$ 再执行 $f$：

复合函数 满足结合律

但一般不满足交换律。令 $f(x)=x^2$、$g(x)=x+1$，则

程序中的组合还要检查中间类型和前置条件。若第一个函数只能保证输出任意整数，而第二个函数要求正整数，表面类型相似也不能证明组合安全。

type Result<T> = { ok: true; value: T } | { ok: false; error: string };
 
function composeResult<A, B, C>(
  first: (input: A) => Result<B>,
  second: (input: B) => Result<C>,
): (input: A) => Result<C> {
  return (input) => {
    const intermediate = first(input);
    return intermediate.ok ? second(intermediate.value) : intermediate;
  };
}

这里错误通道也参与复合，失败不会被伪装成普通值；这正是把数学上的“定义域限制”翻译成程序合同的一种方式。

单射、满射、双射与逆

双射 才能保证通常意义上的逆函数。若 $f:X\to Y$ 是双射，则存在 $f^{-1}:Y\to X$，并满足

只满足第一式可能是左逆，只满足第二式可能是右逆；只有双边逆才能把输入和输出完整地互相撤销。严格单调函数在区间上保证单射，但不自动保证相对于任意陪域满射。例如 $e^x:\mathbb R\to\mathbb R$ 严格递增，却没有命中非正实数；把陪域改成 $(0,\infty)$ 后才成为双射，逆函数是 $\ln y$。

限制定义域和陪域不是注释，而是逆函数成立的组成部分。压缩文件、序列化和解码也遵守同样的逻辑：若编码只对合法消息集合定义，就要明确集合边界；若解码可能失败，工程合同应返回成功值或错误，而不是假装无条件可逆。

四卷中的函数形态

数列：从递推关系到封闭表达式

第1卷第4章的四个关键对象是：斐波那契数列、等比数列与无穷级数、生成函数、递推关系与封闭表达式。它们把“每一项由前项决定”的关系逐步换成更适合整体计算的表示。

斐波那契数列可以写为

这是递推关系；尝试 $F(n)=r^n$ 会得到特征方程 $r^2-r-1=0$，从而寻找封闭表达式。生成函数 $F(x)=\sum_{n\ge0}F(n)x^n$ 又把递推转成代数分式。每种表示都保留对象，却把不同的运算变得容易。

极限与连续：用量词控制误差

第3卷用 $\varepsilon$—$\delta$ 语言表达“输入靠近 $a$ 时输出靠近 $L$”：

量词顺序说明：先给定输出容差，再找能满足它的输入容差，最后对所有符合条件的输入负责。这种函数合同也为数值求根、连续性和误差分析提供了严格语言。

线性变换与随机变量

线性变换 $T:V\to W$ 满足

选定基后，矩阵表示变换，函数复合对应矩阵乘法，可逆矩阵对应双射线性变换。随机变量则是函数 $X:\Omega\to\mathbb R$，把复杂样本映射为可求期望的数值；指示器随机变量只输出 0 或 1。

函数增长：从表示到算法规模

比较

长期看，对数增长慢于任意正次幂，固定次幂慢于指数。渐近阶 可以解释二分查找、比较排序与指数枚举的规模差异，但不能替代有限输入的基准测试：常数、缓存、分支和输入分布都可能改变实际表现。

编程中的函数合同

数学函数给程序设计三条约束：影响结果的时间、配置、随机源和数据库快照应该成为显式输入；定义域外输入、解析失败和数值溢出应该进入显式错误通道；前一函数的输出合同必须满足后一函数的输入合同。

普通程序过程不一定是纯函数。它可能依赖 I/O、全局状态或随机设备；若希望把它建模为确定函数，可以把随机种子或状态加入输入和输出：

这样做不是为了把每个系统都伪装成数学对象，而是为了明确哪些依赖已经被记录，哪些错误还没有被覆盖。可替换、可缓存和局部推理都建立在这份合同上。

三步动手复习

本章练习

本章回顾

• 函数由定义域、陪域、规则和唯一输出共同构成；像集是实际命中的结果集合。
• 单射避免碰撞，满射覆盖陪域，双射同时满足二者并允许双边逆。
• 复合函数先执行右侧函数，中间集合和错误通道必须兼容。
• 第1卷的斐波那契数列、等比数列与无穷级数、生成函数和递推关系都可以放进函数框架。
• $\varepsilon$—$\delta$ 语言、线性变换和随机变量展示了函数概念在不同对象上的迁移。
• 渐近阶比较长期增长，实际性能仍需结合常数、输入分布和可复现基准。
• 编程函数合同必须显式表达状态依赖、前置条件、后置条件和失败路径。