数据推理与应用：从流到无限树

### 数据推理与应用：从流到无限树 在计算机科学领域，流（Streams）和无限树（Infinite Trees）是非常重要的概念，它们在数据处理、有限微积分等方面有着广泛的应用。下面我们将深入探讨流和无限树的相关知识。 #### 流的递归关系 流可以用来表示函数在自然数上的制表。通过特定的运算符 `≺` 和 `⋎`，我们可以捕获“一元”和“二元”递归。 对于“二元”递归序列，给定 `a0 = k`，`a2n+1 = f(an)` 和 `a2n+2 = g(an)`，它对应于流 `s = k ≺ map f s ⋎ map g s`。例如： ```plaintext bin = 0 ≺ 2 * bin + 1 ⋎ 2 * bin + 2 ``` 这里 `k = 0`，`f n = 2 * n + 1`，`g n = 2 * n + 2`，并且 `bin` 是 `id` 函数的制表，即 `bin = tabulate id = nat`。 对于正整数序列，我们可以推导出类似的方程： ```plaintext bin + 1 = (0 ≺ 2 * bin + 1 ⋎ 2 * bin + 2) + 1 = 1 ≺ 2 * (bin + 1) ⋎ 2 * (bin + 1) + 1 ``` 我们得到 `bin′ = 1 ≺ 2 * bin′ ⋎ 2 * bin′ + 1`，并且 `bin′ = bin + 1 = nat + 1 = nat′`。 此外，还有一些特殊的序列： - **最高有效位序列（msb）**： ```plaintext msb = 1 ≺ 2 * msb ⋎ 2 * msb ``` - **1的计数序列（ones）**： ```plaintext ones = 0 ≺ ones′ ones′ = 1 ≺ ones′ ⋎ ones′ + 1 ``` 需要注意的是，`x = x ⋎ x + 1` 没有唯一解，但所有解都具有 `ones + c` 的形式。 下面是一些序列的示例： ```plaintext ≫ msb ⟨1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, . .⟩ ≫ bin′ - msb ⟨0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, . .⟩ ≫ ones ⟨0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, . .⟩ ``` 序列 `bin′ - msb` 描述了到不超过 `bin′` 的最大2的幂的距离，在二进制中相当于移除最高有效位。 还有一个重要的序列是二进制进位序列或尺子函数（carry）： ```plaintext carry = 0 ⋎ carry + 1 ``` 这个序列给出了整除 `bin′` 的最大2的幂的指数，即二进制表示中（最低有效位优先）前导零的数量，它也指定了二进制递增的运行时间。 以下是二进制数与 `carry` 序列的对应关系： ```plaintext 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 0 1 ``` 如果将这个表格向左旋转90度，我们可以更清楚地看到它与尺子标记的对应关系，这也是为什么 `carry` 被称为尺子函数。 #### 有限微积分中的流应用 有限微积分是无限微积分的离散对应，其中有限差分（Finite Difference）取代了导数，求和（Summation）取代了积分。 ##### 有限差分 有限差分或前向差分是一个简单的非递归流运算符，定义如下： ```haskell Δ :: (Num α) ⇒ Stream α → Stream α Δ s = tail s - s ``` 以下是一些有限差分的示例： ```plaintext ≫ Δ 2nat ⟨1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, . .⟩ ≫ Δ carry ⟨1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 2, -2, 1, -1, 4, . .⟩ ≫ Δ nat3 ⟨1, 7, 19, 37, 61, 91, 127, 169, 217, 271, 331, 397, 469, 547, . .⟩ ≫ 3 * nat2 ⟨0, 3, 12, 27, 48, 75, 108, 147, 192, 243, 300, 363, 432, 507, 588, . .⟩ ``` 在无限微积分中，幂函数的导数有一个很好的规则：`(xn+1) d/dx = (n + 1)xn`。但在有限差分中，普通幂函数的表现不佳，例如 `Δ nat3` 并不等于 `3 * nat2`。 为了使有限差分与幂函数更好地配合，我们引入了下降阶乘幂（Falling Factorial Power）： ```plaintext x 0 = 1 x n+1 = x * (x - 1)n ``` 将其提升到流上：`sn = map (λx → x n) s`。下降阶乘幂满足 `s * (s - 1)n = sn+1 = sn * (s - n)`，并且有限微积分有一个类似幂函数导数的规则： ```plaintext Δ (natn+1) = (pure n + 1) * natn ``` 证明过程如下： ```plaintext Δ (natn+1) = { 定义 of Δ } tail (natn+1) - natn+1 = { 定义 of nat } (nat + 1)n+1 - natn+1 = { s * (s - 1)n = sn+1 = sn * (s - n) } (nat + 1) * natn - natn * (nat - pure n) = { 算术运算 } (pure n + 1) * natn ``` 有限差分的一些规则如下表所示： | 规则 | 描述 | | --- | --- | | `Δ (tail s) = tail (Δ s)` | 差分与取尾操作可交换 | | `Δ (a ≺ s) = head s - a ≺ Δ s` | 对带前缀的流进行差分 | | `Δ (s ⋎ t) = (t - s) ⋎ (tail s - t)` | 对交错流进行差分 | | `Δ n = 0` | 对常量流进行差分结果为零 | | `Δ (n * s) = n * Δ s` | 差分对常量乘法可分配 | | `Δ (s + t) = Δ s + Δ t` | 差分对加法可分配 | | `Δ (s * t) = s * Δ t + Δ s * tail t` | 差分的乘积规则 | | `Δ cnat = (c - 1) * cnat` | 对指数流进行差分