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 のような正格な言語にサスペンションを加える記法を示し、最初の応用としてストリームを扱う。正格評価と遅延評価はどちらも解析にとって重要である。正格な言語は最悪時の構造を記述できるが償却的な構造は記述できず、遅延評価の言語はその逆である。

第5〜6章：償却の基礎、遅延評価による償却と永続性（Fundamentals of Amortization; Amortization and Persistence via Lazy Evaluation）

第5章は償却の基礎、すなわち操作の平均コストを抑える技法を示す。第6章は本書の土台である。構造の古いバージョンが使われ続けると従来の償却は成り立たなくなるが、遅延評価（メモ化を通じて）が償却と永続性を両立させる。遅延構造のコストを解析する著者の方法（銀行家の方法と物理学者の方法）は、キューと、共有を伴うボトムアップのマージソートで例示される。

第7章：償却の除去（Eliminating Amortization）

償却的な構造から、遅延された部分の早期実行を体系的にスケジューリングすることによって、最悪時の上界を導けることが多いと示す。最悪時にも操作が定数時間であるリアルタイムキューが主な例である。

第8章：遅延再構築（Lazy Rebuilding）

遅延再構築は大域的再構築の遅延版である。より単純だが、与えられるのは最悪時ではなく償却の上界であり、第7章のスケジューリングと組み合わせると最悪時の上界が回復する。バッチ再構築、大域的再構築、両端キュー（デック）が背景となる。

第9章：数値的表現（Numerical Representations）

数の体系との類比に基づく設計技法である。1 を足す、または引くのが定数時間である二進数の変種を選ぶことが、挿入と削除の設計の指針となる。位取り記数法、二進ランダムアクセスリスト、二項ヒープ、分節二進数、スキュー二進数を扱う。

第10章：データ構造的ブートストラップ（Data-Structural Bootstrapping）

ブートストラップには二つの型がある。上限のある解から上限のない解を作る構造分解と、非効率な解から効率的な解を作る構造抽象である。応用には、キュー、効率的に連結できるリスト、効率的に併合できるヒープが含まれる。

第11章：暗黙の再帰的減速（Implicit Recursive Slowdown）

最後の技術的な章は、Kaplan と Tarjan の再帰的減速の遅延版である。より単純だが償却的であり、最悪時の上界はスケジューリングで回復でき、暗黙のキュー、デック、連結可能な両端キューが得られる。

付録 A：Haskell のソースコード（Haskell Source Code）

約 20 ページの付録がプログラムの Haskell 版を示し、その後に約 10 ページの参考文献と索引が続く。

主要概念

第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 版を比べる。