第 18 章不可变与函数式数据结构 — 改而不动,路径复制¶

这一章讲什么: 怎么做到「更新一个数据结构,同时原封不动保留它的旧版本」—— 这是第 2 章纯度纪律、第 3 章不可变 bag 的自然终点,也是函数式编程的收官。它在全书链条里的位置:全书的落点。前面 17 章每个结构在这里被问一遍: 「你能不能不修改就更新?」答案分三类:天生可以(栈)、改改可以 (链表/BST/trie/队列)、救不了(数组/哈希/双端队列)。

1. 顶层全景¶

  持久化数据结构 = 更新产新版本,旧版本原样保留
      │
      ├─ 手段:路径复制(path copying)——只复制改动路径上的节点,
      │        其余全部共享;旧根 = 旧版本,新根 = 新版本
      │
      ├─ 好消息:
      │    栈:第 10 章的实现本来就没改任何节点 → 天生函数式,O(1)
      │    链表/BST/trie:递归返回新节点,共享未动子树,O(log n)～O(k)
      │    队列:双栈表示(back 进、front 出;front 空则整体倒栈),摊还 O(1)
      │    AVL/红黑/伸展、基数树/TST:同一手法推广
      │
      └─ 坏消息:
           数组:O(1) 随机访问与持久化不可兼得(可换平衡树 O(log n),哈希表同病)
           双端队列/循环列表:改一节点的 next 必须改前驱,连锁全复制
           堆(数组版):卡在数组上;指针版堆(treap/斜堆/斐波那契)可救

  图说:一个动作(路径复制)扫遍全书结构,得出三张清单。

2. 主线例子:BST add(34) 的路径复制走查¶

用第 12 章那棵树(根 22;左子 9;右子 56→左 24→左 23),函数式 add(34):

  add(22节点):34 > 22 → 返回 新节点(22, 左=原左, 右=add(56节点))
  add(56节点):34 < 56 → 返回 新节点(56, 左=add(24节点), 右=原右)
  add(24节点):34 > 24 → 返回 新节点(24, 左=原左, 右=新叶(34))

新树路径:新22 → 新56 → 新24 → 新34,共 4 个新节点; 9 子树、23 叶、56 的右子——全部原样共享,一个指针没动⁵。旧根(老22)拿在手里,看到的仍是没加 34 的老树——版本时间机就这么简单。性能不变:O(树高) 时间 + O(路径长) 的新节点;代价是常数倍的内存分配。

3. 核心原理¶

3.1 数组与哈希:救不了的两个¶

第 3 章埋的伏笔在此兑现。数组本质可变:改下标 i 是原地写, 想保留旧版就得整表复制;用「下标当键的平衡 BST」模拟可以持久化, 但随机访问从 O(1) 退到 O(log n)——「O(1) 与持久化不可兼得」; 更复杂的技术(O'Neill 与 Burton 的方法)也拿不回 O(1)。推论:哈希表一族同样没有好的持久化等价物¹。书里安慰读者:「开头听着丧,但多数结构都能找到等价物」——接下来三节兑现。

3.2 栈与链表:天生与顺手¶

栈是最大的惊喜:第 10 章的 push/pop 本来就是「造新节点/返回 next」, 从没改过任何已有节点——原实现即函数式,O(1) 封顶²。 普通链表:add/remove 递归版只要改写成「返回新节点而非改指针」, 改动位置之前的节点复制、之后共享;其余操作(at/size)原样可用。全部仍是 O(n)(链表的固有天花板),但多了「旧版本还在」的能力³。

3.3 队列:双栈的巧劲¶

队列是首个真挑战:出队像 pop(函数式,好办),入队要动尾指针—— 顺着 next 链一路改到头,等于全复制。解法(也是习题 10.12 的呼应): 用两个栈表示一个队列——入队 push 到 back,出队 pop front; front 空了就把 back 整体倒入 front(顺序恰好反转,队首到栈顶)。每个元素一生经历「back 进、back 出、front 进、front 出」四次 O(1), 摊还 O(1)——第 4 章摊还分析的第二次实战⁴。

3.4 树与 trie 家族:同一手法推广¶

BST 增删 = 递归返回新树,双子删除同样处理(新根 + 新路径); 书上明言 AVL/红黑/伸展都可以套这套写法,复杂度不变,只是多点分配。指针版堆(treap、斜堆、斐波那契)同理;数组堆卡死在数组上。trie 家族 (数组版/对象版/基数树/TST)也一样:新根 + 新路径,大头共享⁶。 判据一句话:节点靠指针连、且更新只波及一条根到改动点的路径 → 可函数化; 更新天然波及一片(数组整体、双端队列的双向环)→ 救不了。

4. 作者的判断与证据¶

开篇先泼冷水再给糖:数组/哈希的「不可兼得」定理级结论放在最前, 「depressing beginning」是作者原话——先立诚实的边界,再展示广度¹。
「旧版本可用」不只是洁癖:持久化天然支持撤销/历史视图/并发快照, 书里以 Redux 状态管理开篇点题(第 3 章 Redux 注的回收)。
摊还口径再次出现:双栈队列的 O(1) 是摊还,与惰性二项、倍增数组构成全书的摊还三部曲⁴。
收尾的立场与第 2 章首尾呼应:「实用主义地用函数式,该可变时就可变」 ——中间路线最后一次重申⁷。

判断(我们的,不是书里的): 本章其实是全书最「编程语言」的一章: 它演示了语言范式如何反向筛选数据结构——纯函数语言(Haskell/Elm) 的世界里,数组/哈希天然缺席,链表/BST/双栈队列成为默认; JS 的混合范式让你两样都留。读这本书若只看算法,会漏掉这层: 数据结构没有绝对优劣,只有「与你承诺的编程模型是否匹配」。 如果错,会错在: 「范式筛选结构」是宏观叙事;工程现实中持久化数据结构库(如 Immutable.js、持久化 vector 的 trie 实现,补充: 哈希数组映射前缀树 HAMT,不在书里)已大幅改写「数组救不了」的结论—— O(log₃₂ n) 的「近似 O(1)」实用上够快。原书的二分(可救/不可救) 在 2025 年应读为「有工程代价」,而非「不可」。

5. 边界与局限¶

O(log n) 的「持久化数组」只有一句指路(O'Neill/Burton),没有实现; HAMT 等现代实现未提及(补充,不在书里);
delete 后「键不存在仍建新树」的浪费被习题 18.3 点破(可返回原树, 需要相等性检查),正文版未优化;
持久化的内存占用(多版本共存)与 GC 压力没量化讨论;
并发场景下的「免锁共享」卖点只是暗示,未展开(补充,不在书里)。

5.1 习题答案补遗(「Chapter 18」)¶

front() 怎么取队首(18.2):front 栈非空就取它的栈顶;front 空时队首在 back 栈的底端——沿 next 一路走到底。空队列返回 undefined⁸。
「键不存在就别建新树」(18.3):正文 remove 对不存在的键也白造一路新节点; 答案给的最简修法是抛异常包 try/catch——键没找到就 catch 住、返回原树, 一行额外结构都没有⁹。
一行 minKey(18.4):minKey = (tree) => isEmpty(tree.left) ? tree.key : minKey(tree.left)——根无左子则根最小,否则左子树全权负责; 递归版把「一路向左」压成三目表达式¹⁰。

6. 可带走的¶

持久化 = 更新产新版本、旧版本保留;手段统一是路径复制。
数组与哈希没有 O(1) 的持久化等价物;双端队列/循环列表同样没救。
栈天生函数式;链表/BST/trie 递归返回新节点即可,复杂度不变。
队列用双栈(back/front + 整体倒转),入出队摊还 O(1)。
判据:更新是否只波及一条根到叶的路径?是 → 可函数化。
实用立场:函数式优先,数组该用还用——第 2 章中间路线的终章回响。

7. 原文地图¶

主题	原书章	原文位置
持久化定义与 Redux	Functional Data Structures	`text/64-fm-functional-data-structures.txt:26`(搜「keeping previous versions」) · `text/64-fm-functional-data-structures.txt:37`(搜「Arrays support」)
数组/哈希不可兼得	Functional Data Structures	`text/64-fm-functional-data-structures.txt:40`(搜「O(log n)」) · `text/64-fm-functional-data-structures.txt:43`(搜「hash tables」)
链表的函数式增删	Functional Data Structures	`text/64-fm-functional-data-structures.txt:88`(搜「const add = (list」) · `text/64-fm-functional-data-structures.txt:117`(搜「const remove = (list」)
栈天生函数式	Functional Data Structures	`text/64-fm-functional-data-structures.txt:142`(搜「restriction」) · `text/64-fm-functional-data-structures.txt:159`(搜「fully functional」)
双栈队列与摊还	Functional Data Structures	`text/64-fm-functional-data-structures.txt:180`(搜「whole copy」) · `text/64-fm-functional-data-structures.txt:268`(搜「four constant-time」)
双端队列/循环列表无解	Functional Data Structures	`text/64-fm-functional-data-structures.txt:281`(搜「no functional equivalent」)
BST 路径复制	Functional Data Structures	`text/64-fm-functional-data-structures.txt:327`(搜「newNode(tree.key, add」) · `text/64-fm-functional-data-structures.txt:356`(搜「const remove = (tree」)
树/trie 家族推广	Functional Data Structures	`text/64-fm-functional-data-structures.txt:381`(搜「AVL」) · `text/64-fm-functional-data-structures.txt:406`(搜「radix trees」)
实用主义收尾	Functional Data Structures	`text/64-fm-functional-data-structures.txt:452`(搜「be flexible」)

出处:「Functional Data Structures」第 37–46 段(text/64-fm-functional-data-structures.txt:40,搜「O(log n)」)。原文:数组可变、改后无法取回旧值;「常用技巧是用下标当键的平衡 BST,但要 O(log n)」;哈希表同病;「这个开头可能显得丧,但多数结构能找到等价物」。 ↩↩
出处:「Functional Data Structures」第 139–159 段(text/64-fm-functional-data-structures.txt:159,搜「fully functional」)。原文:push/pop 从不修改已有节点的值或指针,「原实现已经是完全函数式的」;性能仍 O(1)。 ↩
出处:「Functional Data Structures」第 64–129 段(text/64-fm-functional-data-structures.txt:88,搜「const add = (list」)。原文:add 递归版:位置 0 或空表 → 新节点指向旧表;否则复制当前节点、递归进尾;「你不必重做整个列表——新节点加链接,其余原样」。 ↩
出处:「Functional Data Structures」第 166–268 段(text/64-fm-functional-data-structures.txt:180,搜「whole copy」;:268,搜「four constant-time」)。原文:入队要改尾导致全复制 → 双栈表示;front 空则把 back 整体倒入;「每个值经历四次 O(1) 操作,摊还 O(1)」。 ↩↩
出处:「Functional Data Structures」第 301–335 段(text/64-fm-functional-data-structures.txt:327,搜「newNode(tree.key, add」)。原文:add 返回新树:新根、新路径,其余共享;「从旧根看是原结构,从新根看是新树」。 ↩
出处:「Functional Data Structures」第 381、406 段(text/64-fm-functional-data-structures.txt:381,搜「AVL」;:406,搜「radix trees」)。原文:AVL/红黑/伸展可套同法;堆的指针版可、数组版不可;trie/基数树/TST「总是同一类解法」。 ↩
出处:「Functional Data Structures」第 452 段(text/64-fm-functional-data-structures.txt:452,搜「be flexible」)。原文:「实用主义地应用函数式;必须灵活,知道何时选什么。」 ↩
出处:「Chapter 18」第 16–29 段(text/81-ch18-chapter-18.txt:16,搜「const front」)。答案原文:front 栈非空取其顶;为空则「遍历 back 直到其尾,因为那才是队首」。 ↩
出处:「Chapter 18」第 35 段(text/81-ch18-chapter-18.txt:35,搜「throw an exception」)。答案原文:「最简单的做法是键未找到就抛异常,用 try...catch 包住搜索,异常则返回原树。」 ↩
出处:「Chapter 18」第 44 段(text/81-ch18-chapter-18.txt:44,搜「minKey = (tree)」)。答案原文:根无左子则根为最小;否则最小值必在左子树(其中所有值都小于根)。 ↩

第 18 章 不可变与函数式数据结构 — 改而不动,路径复制¶