エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

バックトラッキング、C++で、Prologも、Haskellでも

C++ Haskell Prolog プログラミング

「第7回オフラインリアルタイムどう書くの問題」を解いていて気がついたこと、学んだことを明日のじぶんのために、記録。


いろいろ問題をコネているうちに、この問題はパタンマッチングで解けることに気がつきました。正確に言うと、最初にC++で解いたコードを読み直していて、パタンマッチングとバックトラッキングそのものだということに気がつきました。

マッチングに失敗したら条件を替えてもう一度最初からマッチングを試みる、というバックトラッキング。
以下、C++とPrologとHaskellでどうするか、整理してみたものです。

設問

まず、パタンマッチングの部分だけが見やすくなるように、「どう書く」の問題からいろいろ取り去ってより簡単な問題を作りました。

  1. 要素を格納する順序付きのコンテナを考える。先頭の位置は0とする。
  2. コンテナ中にある指定された要素が3つ連続している場所がある場合、最初の3つ連続した要素の最初の要素の位置を返す。
  3. 要素が3つ連続した場所がない場合、要素が2つ連続している最初の場所の最初の要素の位置を返す。
  4. 要素が2つ連続した場所がない場合、最初の要素の位置を返す。
  5. 要素がコンテナ中に見つからない場合、-1を返す。


コンテナを文字列として、検索する要素を「A」とすると、次のようになります。

コンテナの内容 戻り値
AAAAAAAAAAAA 0
AA-AAA-AAA-A 3
-AA-AA-AAA-- 7
-AA-AA-AA-AA 1
-A--A--A--AA 10
-A--A--A--A- 1
------------ -1


では。取りかかります。


ちなみに。ここで使ったコードの全体はGitHubに格納していますので、必要に応じて参照してください。

C++で

C++でのコードはいたって簡単です。forループで検索をかけて、見つかったら途中で関数を脱出、見つからなかったら、条件を替えて最初からforループで検索をやりなおす。この最初からループをやりなおす、がバックトラッキングになっています。

template<typename ITEM, typename CONTAINER>
int search(const ITEM& item, const CONTAINER& container)
{
    for(int i = 0; i < container.size() - 2; ++i)
    {
        if((container[i] == item) && (container[i + 1] == item) && (container[i + 2] == item))
        {
            return i;
        }
    }

    for(int i = 0; i < container.size() - 1; ++i)
    {
        if((container[i] == item) && (container[i + 1] == item))
        {
            return i;
        }
    }

    for(int i = 0; i < container.size(); ++i)
    {
        if(container[i] == item)
        {
            return i;
        }
    }

    return -1;
}

Prologで

「マッチングに失敗したらやりなおし」という部分に気がついたとき、最初に頭に浮かんだのが「だったらPrologで書けそうだな」ということでした。
まだProlog力が充分に鍛えられていないのでコードがスパッと浮かんでくるところまでいたっていないのですが、試行錯誤しつつ目的のコードにたどり着きました。

エントリはsearchです。バックトラッキングはProlog自身が持っているのでコードとしては明記してません。逆になにも指定しないと可能なかぎりバックトラッキングが発生するので、3つ連続があったばあい、3つ連続を検出すると同時に2つ連続も検出してしまいます。そのためそれぞれにカット（!）を指定してバックトラッキングを止める必要があります。

search3(C, [C,C,C|_], 0).
search3(C, [X|XS], POS) :- search3(C, XS, POS1), POS is POS1 + 1.

search2(C, [C,C|_], 0).
search2(C, [X|XS], POS) :- search2(C, XS, POS1), POS is POS1 + 1.

search1(C, [C|_], 0).
search1(C, [X|XS], POS) :- search1(C, XS, POS1), POS is POS1 + 1.

search(C, XS, POS) :- search3(C, XS, POS), !.
search(C, XS, POS) :- search2(C, XS, POS), !.
search(C, XS, POS) :- search1(C, XS, POS), !.
search(_, _, -1)   :- !.

Haskellで

PrologでできるならHaskellでもできるだろう…と何の根拠もなく着手したまではよかったのですが、末尾まで検索して見つからなかったときに検索結果をチャラにして最初から検索する、という部分が当初思いつかず。最初のデータを持ち回って、失敗したらその持ち回ったデータを突っ込んで続きを検索させるとかやってみたんですが、ものすごい不格好。というか、それ絶対どっか間違ってる。


で。Maybeを使うだろうというところまではすぐに思いついたものの、関数の値がJust nだったらその値を採用し、Nothingだったら次の関数を評価する、というしくみが思いつかず。思いつかないものの、Haskellはそのようなしくみを持っているはず、と検索をした結果みつけました。答えは手元にありました。

「すごいHaskellたのしく学ぼう！」の第13章「モナドがいっぱい」で解説されているmplusがまさに探している関数でした。

$ ghci
Prelude> :m Control.Monad
Prelude Control.Monad> Just 5 `mplus` Just 2
Just 5
Prelude Control.Monad> Nothing `mplus` Just 2
Just 2


1つめの値がNothingでなければ、2つめの値が何であっても、式全体の値は1つめの値になります。
1つめの値がNothingであれば、2つめの値が式全体の値になります。
まさに望んでいる動作。


もうひとつ。
再帰的に値を計算していくばあい、次のような形で書くのとになるのですが。ここでも関数の値はJust nかNothingかになるとすると、このままでは単純には計算できません。

f (x:xs) = 1 + (f xs)

これについても同書の第7章で、fmapという関数が解説されていました。

Prelude> fmap (1+) (Just 5)
Just 6
Prelude> fmap (1+) Nothing
Nothing

まさに望んでいる動作。


これで準備が整いました。これらをあわせてコードにしてみました。
まだ不細工感があるのは、わたしがまだ理解していないなにかがあるからかと。

import Control.Monad

search3 _ [_,_] = Nothing
search3 c (x1:x2:x3:xs) = if (c == x1) && (c == x2) && (c == x3) then Just 0 else fmap (1+) (search3 c (x2:x3:xs))

search2 _ [_] = Nothing
search2 c (x1:x2:xs) = if (c == x1) && (c == x2) then Just 0 else fmap (1+) (search2 c (x2:xs))

search1 _ [] = Nothing
search1 c (x1:xs)  = if c == x1 then Just 0 else fmap (1+) (search1 c xs)

search c xs = let Just n = (search3 c xs) `mplus` (search2 c xs) `mplus` (search1 c xs) `mplus` (Just (-1)) in n

いつか読むはずっと読まない：「知っている」から「わかる」へ

今回の問題――Haskellでバックトラッキングを実装する、ということをするずっと以前にこの本を通して読んでいました。つまり、問題を解くのに必要な知識はすべて持っていたわけです。それでもそれをひきだしからすぐに取り出すということができませんでした。
外を検索しているうちに「あれ、これ、知っている」と気がつきました。

そこから実際に動くコードになるまで、なぜそれでよいのか理解するまではすぐでした。「知っている」から「わかる」へとシフトした瞬間でした。


「わかる」とは、いったん体内に入ったものが再び出てくるときに起こることなのかもしれません。入るだけだとただ「知っている」だけ。出力されないから使うことができない。それが出力されて初めて「わかる」状態になって、知識を使える状態になるのかな、と。そんなことを思ったバックトラッキングでした。


あと。「すごいHaskell楽しく学ぼう！」はすごいです。というか、すごいということを再確認。初心者も、そうでなくても、読んだ方がいいと思う。


すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!