Purely Functional Data Structures（纯函数式数据结构）

引用

Okasaki, C. (1998). Purely Functional Data Structures. Cambridge University Press.

章节概要

本书约 230 页，共十一章，另有一个收录 Haskell 源代码的附录。书名以及若干章名与作者 1996 年的卡内基梅隆大学博士论文相同。其出发点是：大多数教科书中的数据结构都以命令式语言为前提，而面向 Standard ML、Haskell 或 Scheme 的数据结构必须在没有赋值的情况下工作，并且在更新之后仍要保持旧版本可用。本书介绍设计技术，使读者能够构造自己的函数式数据结构，同时介绍经典结构（出版社提到红黑树和二项队列）以及许多专为函数式语言开发的新结构。代码以 Standard ML 和 Haskell 给出。

第1章：引言（Introduction）

开篇一章阐明函数式与命令式数据结构的对比。破坏性更新对函数式设计是一种不利条件，而持久性是一个额外要求，因为函数式数据结构会保留每一个版本。本章还确定术语，因为“数据结构”有几种相关的含义。

第2章：持久性（Persistence）

本章讨论持久数据结构与瞬时（ephemeral）数据结构：持久结构在更新后支持多个版本，而瞬时结构只允许最新的版本。它建立起这样的认识：函数式程序理所当然地使用持久性，并为后面把持久性与摊还分析结合起来的困难作准备。

第3章：函数式环境中的一些常见数据结构（Some Familiar Data Structures in a Functional Setting）

在引入新技术之前，本书先在函数式语言中重新审视常见的数据结构，展示当更新不能是破坏性的时候，有哪些地方会发生变化。

第4章：惰性求值（Lazy Evaluation）

本章介绍惰性求值：把表达式推迟到需要其值时再求，并缓存结果（记忆化）。它给出一种向 Standard ML 这类严格语言中加入挂起（suspension）的记号，并以流作为首个应用。严格求值与惰性求值对分析都很重要：严格语言能描述最坏情形的结构却不能描述摊还结构，惰性语言则正相反。

第5–6章：摊还基础；通过惰性求值实现摊还与持久性（Fundamentals of Amortization; Amortization and Persistence via Lazy Evaluation）

第5章介绍摊还的基础，即对操作的平均代价加以界定的技术。第6章是全书的基础：当旧版本的结构仍在使用时，传统摊还会失效，而惰性求值（通过记忆化）使摊还与持久性得以调和。作者分析惰性结构代价的方法，包括银行家方法和物理学家方法，在队列和带共享的自底向上归并排序上作了演示。

第7章：消除摊还（Eliminating Amortization）

本章表明，通常可以通过系统地调度惰性部分的提前执行，由摊还结构推导出最坏情形的界。以最坏情形下操作为常数时间的实时队列为主要例子。

第8章：惰性重建（Lazy Rebuilding）

惰性重建是全局重建的惰性变体。它更简单，但给出的是摊还界而非最坏情形的界；与第7章的调度结合后，可以恢复最坏情形的界。批量重建、全局重建和双端队列（deque）是相关背景。

第9章：数值表示（Numerical Representations）

一种建立在与数制类比之上的设计技术：选择一种“加一或减一只需常数时间”的二进制变体，来指导插入和删除的设计。本章涵盖位置数制、二进制随机访问表、二项堆，以及分段二进制数和偏斜二进制数。

第10章：数据结构自举（Data-Structural Bootstrapping）

自举有两种形式：结构分解，即由有界的解构造无界的解；结构抽象，即由低效的解构造高效的解。应用包括队列、可高效拼接的表和可高效合并的堆。

第11章：隐式递归减速（Implicit Recursive Slowdown）

最后一个技术性章节是 Kaplan 和 Tarjan 递归减速的惰性变体。它更简单但是摊还的，最坏情形的界可通过调度恢复，并给出隐式队列、双端队列和可拼接的双端队列。

附录 A：Haskell 源代码（Haskell Source Code）

约二十页的附录给出程序的 Haskell 版本，之后是约十页的参考文献和索引。

核心概念

第1–4章：持久性与惰性

• 持久结构与瞬时结构：更新之后旧版本是否仍然可用。
• 惰性求值与记忆化：推迟计算并缓存其结果。
• 严格与惰性：两种求值顺序，以及各自让人能就代价表达些什么。

第5–8章：摊还

• 摊还：界定一系列操作的总代价，而非每次操作的代价。
• 银行家方法与物理学家方法：分析惰性结构摊还代价的两种方式。
• 调度：提前运行惰性工作以恢复最坏情形的界。
• 惰性重建：把结构的重建分摊到后续的操作中。

第9–11章：设计技术

• 数值表示：仿照数制设计的结构。
• 结构分解与结构抽象：自举的两种形式。
• 隐式递归减速：递归减速的惰性形式，用来得到队列和双端队列。

评析

优点

• 观点鲜明。 出版社的介绍把本书定位为站在函数式语言角度看数据结构，并给出设计新结构的技术，而不是一份目录。
• 方法加例子。 后面各章都围绕一种通用技术（惰性重建、数值表示、自举、隐式递归减速）展开，并用队列、双端队列、堆和随机访问表等具体结构加以说明。
• 两种语言。 源代码在正文中用 Standard ML 给出，附录中是 Haskell，且大多数程序容易改写到其他函数式语言。
• 评论者的评价。 《Computing Reviews》称其重要，因为它从函数式角度介绍数据结构，是专业函数式程序员的便捷参考，程序结构良好、易读，并放在方框中；还指出 C 和 Java 程序员也会发现这些结构实现起来相当直接。
• 可用于自学。 出版社指出，它既可作参考，也可用作教程或自学。

局限

• 与求值顺序绑定。 作者指出，在完全严格或完全惰性的语言中，程序员可以使用其中一部分结构，但不是全部，因为有若干结构同时依赖两种求值方式。
• 语言限制。 有些递归结构难以用 Standard ML 表达（作者提到多态递归和递归模块），因此文中有时先用伪代码，再展示如何转换为合法代码。
• 篇幅短且专门。 全书 232 页，面向已经使用函数式语言的程序员；它不是函数式语言或一般数据结构的入门书。
• 成书年代。 本书初版于 1998 年，读者应查阅较新的文献以了解后来的进展。

在课程中的定位

本课程中的大多数其他书讲的是命令式的结构。《Grokking Algorithms》和《A Common-Sense Guide to Data Structures and Algorithms》是通俗的入门书，代码用 Python 等语言；《Data Structures and Algorithms in Java》是第二门课的教材，从抽象数据类型出发构造每种结构；《Open Data Structures》给出精确的接口、完整的实现和运行时间证明，且在线免费；《Advanced Data Structures》是研究生层次的论述，附有 C 实现和对研究文献的引用。

Okasaki 的书是对它们的补充，而不是替代。适合在学过标准的数据结构课程并有一些函数式语言经验之后阅读，用来了解如何在不使用变更的情况下获得相当的界，以及摊还分析在持久性下如何成立。

如何使用本书

本书面向学过数据结构课程、对 Standard ML、OCaml 或 Haskell 等函数式语言有实际了解的读者；熟悉摊还分析会有帮助。

实用安排：

• 核心： 第2–4章（持久性与惰性），然后是关键的第6章（持久性下的摊还）。
• 技术： 第7–8章（调度与惰性重建），然后按兴趣读第9–11章中的某几章。第9章最为自成一体。
• 选读： 需要温习摊还时读第5章；第11章最为进阶。
• 代码： 至少用自己的语言实现队列和一种堆，包括对持久用法的测试，并比较 Standard ML 和 Haskell 两个版本。