01 / 導讀
導讀
引用
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 兩個版本。