2014年11月 5日

『関数プログラミング 珠玉のアルゴリズムデザイン』が発売されます!

鹿野です。「珠玉」という言葉を目にして、ジョン・ベントリーの『珠玉のプログラミング』という本を思い浮かべるプログラマの方は少なくないでしょう。『珠玉のプログラミング』は、 "Communications of the ACM" に連載されていた名コラム "Programing Pearls" を一冊の書籍としてまとめたものでした。

ところで関数プログラミングに興味がある方の多くは、いろいろ調べているときに、"Functional Pearls" と冠された論文に突き当たったことが一度ならずあるのではないでしょうか。「関数なんたらの珠玉」ともいえるこのシリーズは、 "Journal of Functional Programming" に掲載されている一連のコラムで、これまでさまざま著者によって 80 編ほどの記事が連載されてきました。

そんな "Functional Pearls" のうち、全体の四分の一ほどを執筆しているのは、『関数プログラミング入門 Haskellで学ぶ原理技法』("Introduction to Functional Programming using Haskell")の著者でもある Richard Bird 先生です。その Bird 先生による珠玉中の珠玉ともいえるコラムを集めた書籍『関数プログラミング 珠玉のアルゴリズムデザイン』("Pearls of Functional Algorithm Design")が、いよいよ2014年11月11日に発売されます!

DSC_0078.JPG

本書は、新たに書き足された「珠玉」をふくめ、全部で 30 編の濃縮されたコラムから構成されています。どのコラムも、仕様そのままの愚直なコードから効率的なアルゴリズムを導出したり、数学的に証明できる事実を使って効率のよい演算子を定義したり、関数プログラミングならではの妙技を思う存分に味わえます。巧妙すぎるあまり、一見すると「な... 何を言ってるのか わからねー」という部分も少なからずあるのですが、幸いにも一つひとつの記事は短くまとめられているので、地道に数学の本のように1行ずつアタックしていけば、だんだん話が見えてきて少しずつ楽しくなるはずです。本書を楽しむには、プログラミングの本と違って、コンピュータよりもむしろ紙とボールペンが必須かもしれません。

章ごとに独立した内容なので、どの章から読んでも問題はないのですが、そうはいっても最初の章から読む人が多いと思います。Bird 先生のノリに慣れるまでは、各章でいったい何がしたいのかを理解するのもけっこうハードなので、最初の10章だけ私的ダイジェストを書いてみました。

第1章 最小自由数
自然数からなるリストがあるとき、そこに含まれていない数のうちでいちばん小さいものを見つけよう、という問題です。0から順番に「リストに入ってる否か」を1つずつ調べればよさそうですが、毎回リストをなめる必要があるので、効率的とはいえません。そこで、線形時間の解法を探そうというのが本章の題目です。この章でアルゴリズムを効率よくするために使う武器は、おなじみの配列や分割統治法です。「プログラム運算」はまだ出てきません。
第2章 上位者問題
リストや配列で、自分よりも右側に自分よりも大きな要素が何個あるかを調べよう、という問題です。やっぱり分割統治法を使う問題ですが、今度は第1章のときほど素直に分割と併合を定義できないので、問題を一般化したうえで「プログラム運算」を使おうという流れになっています。
第3章 鞍型探索の改良
f(x,y) = z (x,y,zは自然数)という単調増加関数の逆関数を設計しようという問題です。効率がいい逆関数を設計すべく探索空間をうまく絞る方法について、4人の超優秀な学生による寸劇が繰り広げられます。その過程で、アルゴリズムの設計における漸化式を解いたり下界を決めたりすることの大切さを分かってもらおうというストーリーです。
第4章 選択問題
有限集合の合併から、k番目に小さい要素を求めよう、という問題です。引き続き分割統治法を使う問題ですが、演算子の性質を見極めてプログラム運算に活用する例題です。
第5章 組和の整列
単調な二項演算子の出力結果からなるリストをソートしよう、という問題です。同等だけど比較の回数が減るような演算を定義してから分割統治法に持ち込もうという話です。
第6章 小町算
[1 .. 9] に + と × を挿入して結果が 100 になるパターンを探そう、という問題です。要するに、全探索はいやだ、どうにかして改良したい、それも一般的な方法が知りたい、という人のための章です。この章から「融合則」という武器が登場します。
第7章 最小高さ木の構築
なにかリストがあって、そのリストの要素たちが葉になるような木のうち、高さが最小のものを作ろう、という問題です。さらに問題を一般化して、与えられた木を部分木として持つ木のうち高さ最小のものを作る問題も考えます。貪欲アルゴリズムの練習です。
第8章 分解の貪欲アルゴリズム
列の要素をバラバラにして、右側ほど大きな要素になるような複数の列に組み替える、という問題です。章タイトルのとおり、これもやっぱり貪欲アルゴリズムの練習問題です。
第9章 セレブを探せ
あるグループのセレブとは、グループの全員がセレブを知っているけれど、セレブのほうが知っているのはセレブなメンバーだけ、というメンバーです。そういうメンバーを探し出す問題です。ループと不変条件で解くような問題を帰納法で解く問題に、第3章でも登場した4人の学生と一緒に挑みます。
第10章 重複の除去
リストから重複を取り除くだけでなく、結果のリストが辞書順で先頭でくるようなものにしよう、という問題です。まあまあ分かりやすい仕様そのものを、怒涛のプログラム運算で変形していって、複雑だけど効率的なアルゴリズムを手に入れます。

以降の第11章から第30章でも、

  • 文字列照合のアルゴリズムを関数の合成で考えたり、
  • 行列の要素を扱う演算なしに行列式を計算したり、
  • スライディングブロックパズルを全探索せずに効率よく解くアルゴリズムを考えたり、
  • みんな大好き「数独」のソルバーで枝刈りしまくったり、
  • 漸進的な探索をした結果を QuickCheck で確かめたり、
  • データ圧縮に使える算術符号化を開発したり、
  • 有向グラフへのマーク付け方法を考察したり、
  • 定数時間の遷移を繰り返すことでパターンを効率よく生成する方法(ループレスアルゴリズム)をさまざまな問題に適用してみたり、

とにかくバラエティーに富む話題をネタに、関数プログラミングでいかに効率的なアルゴリズムを設計していくかを堪能できます。

DSC_0080.JPG

なお、本書は都合により PDF 版の発売予定が当面ありません。申し訳ありません。これからの季節にぴったりな装丁で紙版の書籍をお楽しみいただけると幸いです!

トラックバックURL

このエントリーのトラックバックURL:
http://www.ohmsha.co.jp/cgi-bin/mt/mt-tb.cgi/6927