関連サイト
本書の関連ページが用意されています。
内容紹介
私が初めてStandard MLでプログラミングをしたのは1989年のことだった。効率的なデータ構造を実装するのが日頃の楽しみだった私は、さっそく、特に好きなデータ構造をいくつかStandard MLに移植し始めた。そのうちの一部は、非常に簡単に移植でき、しかもうれしいことに、できあがったコードがCやPascalやAdaで書いてあった元の版よりもずっときれいでずっと簡潔になることがしばしばあった。しかし、この経験はそう楽しいことばかりでもなかった。幾度となく、破壊的更新を使いたい気持ちに駆られた。破壊的更新はStandard MLにおいて非推奨の機能であり、他の多くの関数型言語では禁止されているものである。私は既存の文献にヒントを求めたが、わずかな論文しか見つからなかった。しだいに私は、この分野が未開拓であることに気づき、新しいやり方を探求し始めた。
それから8年が経つが、私はいまだに探求している。関数型言語で効率的に実装する方法が知られていないデータ構造の例はまだ数多く存在する。しかしこれまでに、関数型言語でできることについて多くの知見を得てきた。この本では、これらの知見を体系化してみたいと思う。本書が関数型プログラマにとっての参考書となること、また、関数型の世界におけるデータ構造についてもっと学びたい人たちの教科書となることを願っている。
(本書「序文」より)
書誌情報
- 著者: Chris Okasaki(著), 稲葉一浩, 遠藤侑介(訳)
- 発行日: 2017-04-28 (紙書籍版発行日: 2017-04-28)
- 最終更新日: 2017-04-28
- バージョン: 1.0.0
- ページ数: 215ページ(PDF版換算)
- 対応フォーマット: PDF
- 出版社: アスキードワンゴ
対象読者
著者について
Chris Okasaki
アメリカのコンピュータ科学者。専門はプログラミング言語とアルゴリズム、特にこれらの分野の共通領域にある純粋関数型データ構造。アメリカの陸軍士官学校でコンピュータ科学の教鞭をとる。趣味はボードゲームとブリッジ。
稲葉一浩
プログラマ。趣味は海の写真を撮ることとトマトジュース。著書に『Boost C++ Libraries プログラミング』（秀和システム）『Google Maps API 徹底活用ガイド』（毎日コミュニケーションズ）。
遠藤侑介
プログラマ。趣味はプログラミング言語Ruby の開発、関東の鉄道の沿線ウォーキング。著書に『あなたの知らない超絶技巧プログラミングの世界』（技術評論社）、『Ruby でつくるRuby– ゼロから学びなおすプログラミング言語入門』（ラムダノート）、訳書に『抽象によるソフトウェア設計』『型システム入門プログラミング言語と型の理論』（ともにオーム社）。
目次
序文
第1章 はじめに
- 1.1 関数型データ構造と命令型データ構造
- 1.2 正格評価と遅延評価
- 1.3 用語
- 1.4 アプローチ
- 1.5 構成
第2章 永続性
- 2.1 リスト
- 2.2 二分探索木
- 2.3 注記
第3章 古典的なデータ構造を関数型プログラミングで
- 3.1 左偏ヒープ
- 3.2 二項ヒープ
- 3.3 赤黒木
- 3.4 注記
第4章 遅延評価
- 4.1 $-記法
- 4.2 ストリーム
- 4.3 注記
第5章 償却の基礎
- 5.1 償却解析の技法
- 5.2 キュー
- 5.3 二項ヒープ
- 5.4 スプレーヒープ
- 5.5 ペアリングヒープ
- 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 注記
第8章 遅延再構築
- 8.1 一括再構築
- 8.2 全域再構築
- 8.3 遅延再構築
- 8.4 両端キュー
- 8.5 注記
第9章 記数法表現
- 9.1 位取り記数法
- 9.2 二進法表記
- 9.3 ねじれ二進数
- 9.4 三進数と四進数
- 9.5 注記
第10章 データ構造ブートストラップ
- 10.1 構造的分解
- 10.2 構造的抽象
- 10.3 集成的型へのブートストラップ
- 10.4 注記
第11章 暗黙再帰減速
- 11.1 キューと両端キュー
- 11.2 結合可能両端キュー
- 11.3 注記