『純粋関数型データ構造』

https://gyazo.com/db94ffae1b1329ff4071ddd80e77e602

2017/4/28

原著

昔(2019)読んだ時めちゃくちゃ難しい印象があったが、今(2023)読んだら全然読めるようになってた

この本で学んだことを実践する場がほしい

アルゴ式あたりがちょうどよいか

あるいは競プロ系の本の例題を解くか

「このデータ構造を使って解く」というのが予めわかっている状態で解きたい

競プロがしたいわけではないので

1章

関数型データ構造の設計と実装が命令形データ構造より難しい理由

破壊的代入の制限があるから

破壊的代入の制限は安全に寄与するが、破壊的代入がある方が効率がいい

データの永続的な柔軟性が求められているから

正格評価の方が漸近的計算量の推論が容易

抽象データ型を具体的に実現したもの

データ型のインスタンス

オブジェクト、スタックとかキューとか

永続的同一性

更新操作によって得られる様々なバージョンを同一視した概念

今のスタックの状態と2個前のスタックの状態は異なるものだが、同一の概念のように呼ぶ感じ

第1部

関数型データ構造の入門

第2章 永続性

2.1 リスト

図のおかげでリスト操作の永続性がわかりやすい

なのでO(n)かかる

なのでO(n)かかる

二分木のinsertも、前後で大部分が共有される

第3章 古典的なデータ構造を関数型プログラミングで

3.3 赤黒木

3.4 注記

第2部

遅延評価と償却の関係性

4.1 $-記法

4.2 ストリーム

4.3 注記

5.1 償却解析の技法

5.2 キュー

5.3 二項ヒープ

5.6 残念なお知らせ

5.7 注記

第6章 遅延評価を介した償却と永続性

6.1 実行トレースと論理時間

6.2 償却と永続性の両立

6.3 銀行家法

6.4 物理学者法

6.5 遅延ペアリングヒープ

6.6 注記

第7章 償却の除去

7.1 スケジュール化

7.2 実時間キュー

7.3 二項ヒープ

7.4 共有に対応したボトムアップマージソート

7.5 注記

第3部

関数型データ構造を設計する汎用的な技法

第8章 遅延再構築

8.1 一括再構築

8.2 全域再構築

8.3 遅延再構築

8.5 注記

9.2 二進法表記

9.5 注記

10.1 構造的分解

10.2 構造的抽象

10.3 集成的型へのブートストラップ

10.4 注記

11.1 キューと両端キュー

11.2 結合可能両端キュー

11.3 注記

付録A Haskell版ソースコード

訳者あとがき

著者・訳者プロフィール

索引