OCaml演習第2回課題メモ

幅優先探索の効率的なやり方-- grafi 2013-04-18 16:05:00

副作用を使ってキューを作る

変更可能なバリアント（別にレコードでもいいけど）を使って、Cで連結リストを作る場合と同様にリストを実装し、先頭と末尾への参照を保持しておけばできそうです。関数論理型プログラミングの演習としてはどうなんだ。

副作用を使わずにキューを作る

純粋関数型プログラミングでキューを実現するには色々考えることがあるのですが、幅優先探索だけなら一番簡単なやり方で十分です。リストを二つ用意して、頭の要素を入れるリストが空になったら、尻の要素を入れるリストをまとめてひっくり返して頭の要素のリストとすることで、追加された要素の数のオーダーでしか計算が起こらないようにします。ググればそれっぽいのは出てきます。

キューを作らない

元々alpicolaがやってたのですが。

　　　　　１
　　　　／　＼
　　　／　　　＼
　　２　　　　　３
　／　＼　　　／　＼
４　　　５　６　　　７
　　　　　／　＼
　　　　８　　　９

という木を考えます。

うまく木のリストを処理しながら再帰して、

([1]@([2;3]@([4;5;6;7]@([8;9]@[]))))

という計算を行わせれば勝利です。木の深さに対するfold_rightみたいな形ですね。

末尾再帰を意識して書くと、多分

(((([]@[1])@[2;3])@[4;5;6;7])@[8;9])

となります。fold_leftみたいな形ですね。右結合と左結合でどういう違いが出るかは考えれば分かると思います。リストはモノイドだから結合則を満たしているけど、参照の書き換えを使わないと気楽に結合できません。でも参照の書き換えを使わない方がコンパイラは最適化しやすいんでしょうきっと。

さて、要素のレベルごとにリストを作るというのでいいのですが、幅優先探索はキューの操作として見れば、「キューの先頭の要素を取り出す」→「その要素から何らかの方法で得られる要素をキューの末尾に入れる」という操作の繰り返しでしかありません。ただのキューの操作を最適化するために、何で木の中でのレベルなんて概念なんか必要なのだろう、とぼくは気になったので、思ったところを適当に書きます。何かあればツッコミおねがいします。

「副作用を使わずにキューを作る」で作るキューを、(front,rear)とします。

このキューを用いて上の木に対する幅優先探索を行うことを考えると、

([1],[])→([2;3],[])→([4;5;6;7],[])→([8;9],[])→([],[])

という風にキューの状態が移り変わることが分かります。結局レベルごとに処理してるじゃないですかー。つまり、各レベルの要素のリストを繋げるというやり方と、副作用を使わずにキューを作るやり方では、実質的に同じことをやっていたことになります（実際には、キューを使った探索だと末尾再帰的に見かけた要素をリストに蓄えて後でreverseするのが自然でしょうし、左結合型に近い気はします）。

なぜこんなことになるのかを二項関係を使って考えてみます。集合とリストを同一視しますがご容赦ください。木のノードaがノードbを子として持つことを、a(R)bとして表現します。aがcを孫として持つのはa(R^2)c、aがdをひ孫として持つのはa(R^3)d、と表現できるように、一般の場合の累乗を定義します。集合Aに対して、R^n(A)={b|∃a∈A. a(R^n)b}とします。

このとき、キューが(A,{})となっている状態から幅優先探索を行うと、キューの中身の遷移は

(R^0(A),{})→(R^1(A),{})→(R^2(A),{})→…

となります。

二項関係を木のノードに対して考えているので、 a(R)b⇔level(a)+1=level(b)が成り立ちます。また、幅優先探索の開始時のキューは、({t},{}) s.t. level(t)=0です。なので、帰納的に、キューの遷移が木の中でのレベルごとになることは納得できるかと思います。あるスタックの操作をDFSであるとみなしたときに木に対応するというのは形式言語理論のプッシュダウンオートマトンあたりで出て来ましたが、あるキューの操作をBFSであるとみなしたら木に対応するのでしょう（ループがあったときにどうなるかとかは考えてないですが）。

再帰型を使ってfix

コンビネータはSchemeでやったのと同様。型付けを1時間くらい考えてみてから諦めてWikipedia見るのが良いんじゃないでしょうか。型を使ったトリックに慣れてない人が思いつけるのかな…。

matchののネスト

exprの評価関数を作る際にmatchをネストすることになるかと思いますが，OCamlはインデントなどお構いなしにパースするのでどのmatchに対するパターンマッチかが分からなくなって謎の型エラーが出ます。

match foo with
| Bar ->
    begin match boo with
    | Zee -> ...
    | Goo -> ...
    end
| Poo -> ...

と書けばいいようです。参考: http://d.hatena.ne.jp/camlspotter/20101212/1292165692

発展3

サラッと書けそうなのと、アリっぽいけど純粋関数的には書けなさそうなのと、どう考えても無理だろってのはあります。

「純粋関数的に書けなさそう」はカリーハワード同型が直観主義論理に対応するから排中律が云々、ということと対応するはずです。11erのWikiにも色々書いてます。

じゃあ例外や副作用を使うことでどう論理的に強力になるのかということですが、Wikibooksに何かそれっぽいことが書いています、が良くわかりません。日本語が怪しいので、英語で見たほうが良い気がします。元ネタとして挙げられてる記事を見るのがいいかも。何にせよロジックちゃんと知らないときちんと考察するのは厳しそう。

FLProgClassCategory