筆者:村田
こんにちは。
前回は列のチェック関数を作成し、末尾再帰について紹介して終わったのでした。check-col関数の動作をもう一度おさらいします。第1引数にチェックしたい行の先頭である(3 1)や(4 1)を渡し、第2引数には盤面上に置いたクイーンのリストを渡します。例えば、(1 1)と(2 4)にクイーンがある場合、3行目にクイーンが置けるかをチェックすると、
user=> (check-col '(3 1) '((2 4) (1 1)))
((3 2) (2 4) (1 1))
(3 2)に置けることが分かり、(3 2)を加えた盤面上クイーンリストを返してくれます。今度は行のチェック関数を作りましょう。前回の記事の前半にて、手動でアルゴリズムの動きを確認しましたが、改めて手順をイメージします。->の後は盤面上のクイーンリストを示しています。
1. 1行目はどこに置けるか? -> ((1 1))
2. 2行目はどこに置けるか? -> ((2 3) (1 1))
3. 3行目はどこに置けるか? -> nil -> 置けなかった
4. 2行目に戻って、別の場所に置けるか? -> ((2 4) (1 1))
5. 3行目はどこに置けるか? -> ((3 2) (2 4) (1 1))
関数名と引数はこんな感じです。第1引数は分配束縛して分解しておきます。
(defn check-row [[row col :as pos] queens] ...
次に、引数に渡された位置に基づいて、その行のどの列なら置けるか調べます。
(defn check-row [[row col :as pos] queens]
(if (check-col pos queens) ;; どの列に置けるか?
(置ける場合の処理)
(置けない場合--nilの処理)
と書けます。置ける場合は、次の行のチェックに進めばいいので、行をインクリメントして再帰呼び出しします。
(defn check-row [[row col :as pos] queens]
(if (check-col pos queens)
(check-row (list (inc row) 1) (check-col pos queens)) ;; 再帰呼び出し
(置けない場合--nilの処理)
(list (inc row) 1)の部分は、次の行の先頭ですね。rowが3ならば(4 1)となります。問題はcheck-col関数を2回呼び出している点です。1回目は真偽値判定として、2回目は戻り値のクイーンリストが欲しいからですが、2回もcheck-colを動かすのは効率が悪いです。関数内で一時的に変数を作って、呼び出し結果を取っておきましょう。letフォームを使えば関数内で一時変数を使えます。書式は、
(let [束縛名1 式1 束縛名2 式2...] (束縛名1,2を使った式))
ちょっと具体例が必要ですね。
user=> (let [x 1 y 2] (+ x y 3))
6
xに1、yに2を束縛し、xとyと3を足しています。ところで関数型言語では、変数に「代入」と言わず、変数に「束縛」って言ったりします。オブジェクト指向言語では変数は「入れ物」であり、値を入れたり(代入)、値を入れ替えたり(再代入)できます。関数型言語では、変数はただの「名前」です。何かの値や、関数/式の結果や、関数そのものを指し示します。100という値に一度aという名前を付けたら(束縛)、aはずーっと100となります。そう名前を付けたのですからね。200という値にもaという名前を付ける、ということはできません。まあ、束縛(bind)という言葉から、このニュアンスが伝わるかはさておき、重要なことは再代入(名前の付け替え)はできないということです。
話を戻します。letフォームの[]内は束縛名と式を順番に並べます。この束縛はletフォーム内での一時束縛ですので、letフォームの外側からは参照できません。さて、letフォームを使ってcheck-colの結果を取っておけるようにしましょう。
(defn check-row [[row col :as pos] queens]
(let [newqueens (check-col pos queens)] ;; 結果をnewqueensに束縛
(if newqueens
(check-row (list (inc row) 1) newqueens)
(置けない場合--nilの処理)
letフォームを使うとどんどんネストが深くなってしまいますが仕方ないです。見づらくなったら関数に切り出す、マクロを作るなど対処が必要かもしれません。
次は置けない場合の処理です。一つ前の行に置かれたクイーンを取り出して、他の場所に置けないか続きを調べさせます。
(defn check-row [[row col :as pos] queens]
(let [newqueens (check-col pos queens)]
(if newqueens
(check-row (list (inc row) 1) newqueens)
(let [[row col] (first queens)]
(check-row (list row (inc col)) (rest queens)))))) ;; 一つ前のクイーンの位置を調べ直す
だんだん横に長くなってきますね。インデントは自由に書けます。ifフォームは条件/True処理/False処理のカラムを揃えた方が見やすいと思いますが、letフォームのインデントは浅くした方がいいかもしれません。
5行目でまたもやletフォームで一時束縛しています。queensの先頭を取り出して一つ前のクイーン位置を分配束縛しています。[]が2重になっているので注意。
(let [pos (first queens)] ...)
と書いてもいいですが、この後posのrowとcolを分解したいので、
(let [[row col] (first queens)] ...)
と分配束縛しています。このように分配束縛は関数の引数だけでなくletフォームでも使えます。6行目は (list row (inc col))で、行はそのままで列をインクリメントして再帰呼び出ししています。(rest queens)で盤面上のクイーンリストから一つ前の行のクイーンを除いています。これで一つ前の行のクイーンは一度取り除き、続きの列から置ける場所を探させているというわけです。この辺りのアルゴリズムは再帰も絡んでいてイメージしづらいかもしれません。その場合は、前回記事のようにcheck-rowに手動で引数を渡して実際に動かしてみるといいと思います。REPLでも紙でもいいのですが、複雑なアルゴリズムは手を動かすと理解が深まると思います。
昔話ひとつ。異業種からプログラマになりたての頃です。(26だったかな・・遠い目) C言語の入門書を読み、プログラムを書き始めて最初にハマったのはポインタでは無く(もちろんポインタでもその後"ど"ハマりするわけですが・・)、for文を使って歯抜けになった配列を詰めるというアルゴリズムでした。慣れないviの画面をにらみ、ひたすら頭の中で考えるも、まーったく書けず、先輩に相談しました。こいつ大丈夫か〜と思われながらも、モニタを消され裏紙と鉛筆を渡され、「一度に全部考えず、手順をバラバラにしろ、手を動かせばバラバラにできるだろ〜」と言われました。その後しばらく書いたり消したりして、ようやく手順(アルゴリズム)を書くことができました。今でもアルゴリズムやクラス設計で悩むと、紙を取り出してお絵描きしています。(そしてその時間が一番楽しかったりします) 弊社内では、みんなでアルゴリズムやデータ構造の学習問題に取り組む機会があるのですが、私の場合はたいてい頭にすぐ浮かばず、お絵描きが始まるのです。
え〜、脱線するからpart5までかかってしまうのですが、とにかく、時には紙に自由に絵を描いたり、REPLで気の済むまで実験すると理解が深まったりしますという意見でした。
ところで先程の関数は再帰を使っていますが、停止するか確認していませんでした。アルゴリズムの動作をイメージします。6行目で対象の行を増やしながら再帰を繰り返すと、いつかは盤面をはみ出しますね。この関数もcheck-colと同じように最初に盤面をはみ出していないかチェックするようにします。少しインデントも狭めましょう。
(defn check-row [[row col :as pos] queens]
(if (not (on-board? pos)) queens ;; 盤面のチェック
(let [newqueens (check-col pos queens)]
(if newqueens
(check-row (list (inc row) 1) newqueens)
(let [[row col] (first queens)]
(check-row (list row (inc col)) (rest queens)))))))
お、この関数も末尾再帰になっています。recurフォームに変えて末尾再帰最適化しておきます。
(defn check-row [[row col :as pos] queens]
(if (not (on-board? pos)) queens
(let [newqueens (check-col pos queens)]
(if newqueens
(recur (list (inc row) 1) newqueens) ;; 末尾再帰最適化
(let [[row col] (first queens)]
(recur (list row (inc col)) (rest queens))))))) ;; 末尾再帰最適化
ちょっとテストしてみましょう。今回も盤面サイズは4x4(4-Queens問題)にしておきます。
user=> (def board-size 4)
user=> (check-row '(1 1) nil)
((1 1))
1行1列にクイーンを置くと解答を得られませんでした。1行2列ならどうでしょう。
user=> (check-row '(1 2) nil)
((4 3) (3 1) (2 4) (1 2))
4個置けたので、これが解答の一つとなります。ちなみに1行3列から開始するとどうなるでしょう。
user=> (check-row '(1 3) nil)
((4 2) (3 4) (2 1) (1 3))
これも4-Queens問題の解答ですね。最後の関数は今の手順を自動化する関数です。1行1列目、2列目・・・と順番にテストして結果を検査します。なおテスト結果の検査関数はpart2で最初に作っていましたね。ええ、忘れてますよね。再掲します。
(defn goal? [queens]
(= board-size (count queens)))
それでは最後の関数名は、answerにしたいと思います。さっきの手動テストの通り、この関数もループが必要です。また今回も引数を変えながらanswerを再帰呼び出しすればいいのですが、answerは引数無しでいきたいな〜と。実はclojureの再帰呼び出しは、もっとforループっぽくできます。末尾再帰最適化では、スタックを消費しない単純なジャンプに変換できると言いました。語弊がありそうですが、単純なジャンプなので関数内の狙ったところに飛べます。実際のところ、このあたりはlisp方言の一つであるSchemeを紹介して継続、継続渡し形式(CPS)の話がしたくなるのですが、今回は省きたいと思います。ではclojureでのテクニック、loopフォームを紹介します。
(loop [束縛名1 初期化式1 束縛名2 初期化式2] (束縛名1,2を使った式... recurフォームでloopに戻る))
これも例を見てみましょう。なおREPLは途中で改行しても括弧が閉じるまでフォームを入力できます。
user=> (loop [i 0] ;; iを0に初期化
#_=> (if (= i 10) i ;; iが10ならiを返しておしまい
#_=> (do (println "i ->" i) ;; 途中経過のiを表示(doフォームは副作用を書ける)
#_=> (recur (inc i))))) ;; iが10未満なら+1してloopにジャンプ
i -> 0
i -> 1
i -> 2
...
i -> 9
10
唐突にdoフォームを出してしまいました。詳しくは述べませんが副作用を書くためのフォームです。loopの各ステップでiが変わっていることをprintlnで表示させています。このloopのようなマクロ的構文拡張はlispならでは、clojureの利点なのでしょう。2重ループとかloopで書きたくない感じではありますが。というわけで、これを使ってanswerを書いてみます。
(defn answer []
(loop [[row col :as startpos] '(1 1)]
...
loopの初期値を設定しています。startposとして(1 1)を束縛し、ついでに分配束縛もしています。ふ〜もう少しだ・・・
(defn answer []
(loop [[row col :as startpos] '(1 1)]
(let [queens (check-row startpos nil)] ;; check-rowで(1 1)から調べ、結果をqueensに束縛します
(if (goal? queens) queens ;; 答えが得られた! のでqueensを返しておしまい
(recur (list 1 (inc col)) nil))))) ;; 駄目なら(1 2)のようにcolを増やしてloopへジャンプ
再帰の停止が不十分ですね。答えがずーっと見つからないとcolが増えて無限ループします。盤面を超えても答えが見つからない場合は停止させてnilを返しましょう。
(defn answer []
(loop [[row col :as startpos] '(1 1)]
(if (not (on-board? startpos)) nil ;; startposが盤面になければnilでおしまい
(let [queens (check-row startpos nil)]
(if (goal? queens) queens
(recur (list 1 (inc col)) nil))))))
とりあえず4-Queensでテストしましょう。
user=> (answer)
((4 3) (3 1) (2 4) (1 2))
答えがでましたが、クイーンリストの順番を逆にした方がいいかな。loopフォームの結果をひっくり返します。リストを逆順にする関数は標準ライブラリにあります。(doc reverse)で見てみてください。
user=> (reverse '(1 2 3))
(3 2 1)
使い方を見たところで、まずanswer関数全体の大雑把な構造をおさらいします。
(defn answer []
(loop [...] (... queensを返す))
となっているので
(defn answer []
(reverse (loop [...] (...queensを返す)))
と書けば結果をひっくり返せますね。最終的なanswerは以下の通り。
(defn answer []
(reverse
(loop [[row col :as startpos] '(1 1)]
(if (not (on-board? startpos)) nil
(let [queens (check-row startpos nil)]
(if (goal? queens) queens
(recur (list 1 (inc col)))))))))
user=> (answer)
((1 2) (2 4) (3 1) (4 3))
やはり逆順に並べ替えた方が見やすくなりますね。それではよーやく8-Queensの解答を見れそうです。試してみましょう。
カチャカチャ、ッターン!
user=> (def board-size 8)
user=> (answer)
((1 5) (2 1) (3 4) (4 6) (5 8) (6 2) (7 7) (8 3))
んーたぶん正解だと思います。このリストを引数にして盤面を表示する関数が欲しいところですが、今回はもうゴールしてもいいよね・・。なお、関数型言語では副作用を用いる箇所は少ない方がいいので、answerのような関数は結果を値で返す方がいいです。後でその値を表示するだけの関数を作ればよく、answerのようなロジックを書いている純粋関数と、副作用関数はなるべく分けた方がいいです。今回は手動で確認してみます。下の通りで、答えの一つを無事答えてくれたようです。(アスキーアートだと斜めが見づらいですが)
+-+-+-+-+-+-+-+-+
| | | | |Q| | | |
+-+-+-+-+-+-+-+-+
|Q| | | | | | | |
+-+-+-+-+-+-+-+-+
| | | |Q| | | | |
+-+-+-+-+-+-+-+-+
| | | | | |Q| | |
+-+-+-+-+-+-+-+-+
| | | | | | | |Q|
+-+-+-+-+-+-+-+-+
| |Q| | | | | | |
+-+-+-+-+-+-+-+-+
| | | | | | |Q| |
+-+-+-+-+-+-+-+-+
| | |Q| | | | | |
+-+-+-+-+-+-+-+-+
この問題はまだまだ発展できます。全解答を導きだし、その解答数を求めるのはなかなか面白そうです。それを並行処理で求めるとしたら。むむむ。
[おわりに]
clojureはいかがでしたでしょうか。haskellと似たところも違うところもありますが、関数型言語でプログラミングする過程には似たところがあったと思います。まあ前回の素数の問題も8-Queensも問題の性格が似ているからかもしれません。どちらも副作用は無く、再帰を中心としたアルゴリズム問題で、基本的なリスト操作関数しか使っていません。clojureについてはまた機会があれば触れたいと思います。残念ながら、clojureのパワーは全然引き出せていません。
ほんとは、『奇跡も、魔法もあるんだよ!!』
テーマとしては遅延シーケンスやカリー化を活用した効率的なアルゴリズム・関数設計、Javaとの連携、プロトコルやマルチメソッドでの抽象、clojureと言えばSTMなどの非同期/並行処理の安全な記述、そしてマクロの深淵へ・・・
今回のコード全体を載せて終わりにします。お付き合い頂き有り難うございました。
以上。