「関数プログラミング向けのデータ構造」と「遅延評価」を知るための一冊

関数プログラミング向けのデータ構造というものについて、
考えたことがあるでしょうか？

良くアルゴリズム本に出てくるデータ構造は、
破壊的更新を使った命令的（手続き的）なスタイルで使われることを前提に定義されています。
そのためデータ構造の中には、
Standard ML（SML）や Haskell などのような関数型言語で使おうとすると（非常に）効率が悪いものもあります。


本書ではならし解析や遅延評価を用い、
「どうしたらより効率の良いデータ構造が構築できるか」についてせまっていきます。


本書は実は Haskell ではなく SML を対象として書かれているのですが、
Haskell をやっていく中でもその重要度が劣ることはありません。
寧ろ、
Haskell 的にはその価値が増すかもしれません。
破壊的更新を一切行わず、
代わりに遅延評価を用いるという方針は、
Haskell にこそ向いたものです。
実際、
GHC や Hugs などの Haskell の処理系に付属するライブラリには、
Data.Queue や Data.Sequence など、
本書で述べられているテクニックやその発展を使っているものもあります。


また、
SML のような本来遅延評価ではない言語に遅延評価を差し込んでいくという形で議論が展開されていくため、
遅延評価って何が良いのかよくわからない人は本書を読むことで遅延評価というものの価値を知ることができるでしょう。


本書のソースコードは SML を使って書かれていますが、
巻末に Haskell でのコードが載っているので、
巻末のコードと照らし合わせながら読めば Haskell しか知らない人であっても分からないということはないと思います。


ただ、
一点注意しておかなればならないのは、
本書はその性格上アルゴリズムの知識を前提とすることです。
他にアルゴリズム本を読んだことがなければ、
先に何か適当な本を読んでおくと良いでしょう。
Algorithms: A Functional Programming Approach という Haskell を使ったアルゴリズム本があるので、
Haskell をやっている人であれば先にこれを読んでおくと良いかもしれません。