中身はともかく、ストーリーを忘れないようにメモ
純粋関数型言語でデータ構造を書くと以下のような利点が得られて嬉しい
- 自動的に永続性（persistent)が得られる。（要素を更新した後でも、更新前のデータに安全にアクセス可能）
- 破壊的代入を伴う命令形言語で実装された多くのデータ構造は短命(ephemeral）である。
- 命令形言語では複雑になる、ある主のデータ構造が抽象化を通して非常にシンプルになる（LinkedList, Red-Black Tree)
が！
（破壊的代入を許可した実装に比べて）効率の良い実装が難しいデータ構造があるという弱点がある。
しかし、実は色々なテクニックを使うと効率よく実装できる！というのがこの本の前半の趣旨
List２つ使ってQueueを作る例
- Listをリバースする操作が入る。（これはO(N))
- 操作の最悪計算量でいうとO(N)になるが、操作列に対する償却計算量はO(1)となることが証明できる。
- 証明テクニックなどの説明もある
- その他ヒープでの例とかも紹介
償却計算量を使えば、効率は良くなる！以上！とはならない。
純粋関数型言語で書くと得られる永続性を利用すると償却計算がなんども実行される可能性がある。
先程のQueueの例ではリストをreverseする直前のデータを持っておいて、何度もdequeueすると、何度もreverseされることになる。
これでは困るのでなんとか計算を共有したい。そこで遅延評価とメモ化という関数型おなじみのテクニックが登場する。
reverse操作をメモ化すれば、なんどもreverse操作が呼ばれてもメモ化されるのでO(1)で処理が可能。
言うのは簡単だが証明テクニックなどを頑張る必要がある。（過去の履歴：操作履歴、これからあり得る操作：論理未来などの概念も導入される）
メモ化されるから最強！以上！とはならない。
償却計算量という操作列に対する計算量の上限では満足できない場合がある。（リアルタイムシステムなど） そういうシステムも関数型で書きたいかもしれないので、操作に対する上限を与えることにする。
ここでは償却を少しずつ行うスケジュールという概念が導入される。
Queueの例では、insertされるたびに少しずつreverseを裏で進めておくことにする。 1操作あたり、どのくらい計算を進めておけばいいのかをデータ構造の不変条件などを考えながら緻密に組み立てていく。
ここまでで、償却計算量で我慢していた関数型のデータ構造が、メモ化・スケジュールといったテクニックを通して 破壊的代入を伴う言語と同等レベルの最悪計算量を持てるようになることがわかった。（さらに、永続化という性質もついてくる）
データ構造を設計するためのテクニックが紹介される
- 遅延再構築
- 記数法表現
- データ構造ブートストラップ
- 暗黙再起減速
- 純粋関数型データ構造 https://www.amazon.co.jp/dp/4048930567