昨日はPlayもくもく会に行ってきました。色々と教えていただいてありがとうございます。

で、その中でたまたまprologのお話になったので、
prologの魅力が簡単に分かるような「prolog向きの」サンプルを書いてみたいと思います。

ちなみに、prologは頑張れば関数型言語向きの事もそれなりに出来たりはしますが、
向き不向きが激しい言語なので使い道は選びます。

prologは「ルールは分かるけど解き方はわからない」ものを解くプログラムが簡単に書けます。

今回はルール説明が要らないであろう、「ハノイの塔」でやりたいと思います。

prologでハノイの塔

一応簡単に説明すると、地面に刺さった3本の棒といくつかの大きさの違う円盤を使ったゲームです。

円盤は左端の棒に大きいものから順に上に行くほど小さくなるように刺さっています。
プレイヤーは1回につき1枚の円盤を他の棒に移動させることができます。
ただし、円盤の上にはその円盤より大きい円盤は乗せることができません。
全ての円盤を右端の棒に移動させればゲームクリアです。

大体こんな感じのはずです。
実装にはgplorogを使います。他はわからないので。

棒の実装

難しいのは嫌なので、棒をリスト、円盤を数値にしてしまいます。円盤がゼロの棒を[]、小さい円盤がひとつささった棒を[1]、
複数個刺さっていたら[1, 2, 3]とか[2, 3, 5, 8]とかですね。

hanoi_tower([]).           % 空の塔
hanoi_tower([_|[]]).       % 1つの円盤が入った塔
hanoi_tower([H1, H2|T]) :- % 2つ以上の円盤が入った塔
  H1 < H2,
  hanoi_tower([H2|T]).

ここでやったことは単純に1本の棒の可能性を列挙しただけです。
|が最初の要素と後続のリストをわける記号になります。
lispで言うcarとcdr、haskellのheadとtailですね。 _(アンダースコア)は何らかの値が入るけど使わないので名前を付けないってやつです。

なので、棒(=hanoi_tower)は空([])か1つの円盤([_|[]])か2つ以上の円盤です。

2つ以上の時は上の円盤は下のより小さくないといけないので、大小比較をしています。
動作確認をしてみましょう。

$ gprolog --consult-file hanoi.pl

で指定したプログラムを読み取ってREPLを開けます。

| ?- hanoi_tower([]).

yes
| ?- hanoi_tower([1]).

true ? a

no
| ?- hanoi_tower([10]).

true ? a

(3 ms) no
| ?- hanoi_tower([1, 2, 3]).

true ? a

no
| ?- hanoi_tower([1, 3, 2]).

no

作れるはずのリストにtrueが返って来て居たら成功です。

棒のセットの実装

これも簡単にリストのリストで実装します。
[[1, 2, 3], [4, 5], []]こんなのです。

hanoi_set(X) :-
  X = [L, M, R],
  hanoi_tower(L),
  hanoi_tower(M),
  hanoi_tower(R).

読み方としては、

hanoi_setであるXは要素数3のリスト[L, M, R]である。
Lはhanoi_towerである。
Mはhanoi_towerである。
Rはhanoi_towerである。

こんな感じです。

同じくREPLで確認します。

| ?- hanoi_set([[1, 2, 3], [4, 5], []]).

true ? a

no
| ?- hanoi_set([[1, 3], [2, 4, 5], []]).

true ? a

no
| ?- hanoi_set([[1, 3], [2, 4, 5], [7, 6]]).

no

多分大丈夫かと。

移動ルールを実装

ついに移動ルールを実装します。
ルール名をhanoiとしましょう。引数を3つとって、元の状態、移動ルール、異動後の状態とします。

prologに慣れていないと何を言っているの？となりますが、
普通のプログラミング言語なら最後の引数は戻り値なんだと思えば大体あってると思います。

hanoi([[1, 2, 3], [], []], left_to_middle, X).

とした時に、Xに[[2, 3], [1], []]と入っていてほしいということです。

異動の種類としてはleft_to_middle, left_to_right, middle_to_left, middle_to_right, right_to_left, right_to_middleの6種類ですね。

hanoi(X, left_to_middle, Y) :-
  hanoi_set(X),
  [XL, XM, XR] = X,
  [H|T] = XL,
  Y = [T, [H|XM], XR],
  hanoi_set(Y).

Xはhanoi_setで
Xのそれぞれの列がXL, XM, XRで
XLの一番上をH, それ以外をTとした時
Yは左からT, [H|XM], XRとなっていて
Yはhanoi_setの条件を満たしている(= ルール上可能な移動である)

| ?- hanoi([[1, 2, 3], [], []], left_to_middle, Y).

Y = [[2,3],[1],[]] ? a

no
| ?- hanoi([[2, 3], [1], []], left_to_middle, Y).

no
| ?- hanoi([[], [1], []], left_to_middle, Y).

no

他もまあ同様に実装できます。(が、省略します。)

hanoi(X, left_to_right, Y) :-
hanoi(X, middle_to_left, Y) :-
hanoi(X, middle_to_right, Y) :-
hanoi(X, right_to_left, Y) :-
hanoi(X, right_to_middle, Y) :-

複数回の移動に対応する

先ほどのhanoiは移動処理が単純な変数なので、1回の移動しか表現できません。

そこで、移動処理もリストにしてみましょう。
まず、移動0回の場合は空のリスト[]で移動前と移動後が当然同じですね。

hanoi(X, [], X) :- hanoi_set(X).

それ以外の場合は、先頭の移動をやった後次の移動を実行です。
リストのリストという場合を検証しなくてよいように、リストに入れられる値を制限します。

% handを定義
hand(left_to_middle).
hand(left_to_right).
hand(middle_to_left).
hand(middle_to_right).
hand(right_to_left).
hand(right_to_middle).

hanoi(X, M, Y) :-
  maplist(hand, M), % `M`に入るのはhandを満たす値のみ。
  [H|T] = M,
  hanoi(X, H, Z),
  hanoi(Z, T, Y).

移動方法がリストだった場合は先頭をH, 残りをTとします。
Xに対し、Hという移動を実行したものをZとします。
Yは、Zに対して残りのTの移動を全部実行したものです。

| ?- hanoi([[1, 2, 3], [], []], [left_to_middle, left_to_right], Y).

Y = [[3],[1],[2]] ? a

no
| ?- hanoi([[1, 2, 3], [], []], [left_to_middle, middle_to_right], Y).

Y = [[2,3],[],[1]] ? a

no

これで、ルールの実装は大体終わった気がします。

仕上げ

さて、ここで答えを求めたいので、prologさんの性格に合わせて少しだけ手間をかけてあげます。

prologさんはすぐに無限ループをしたがるので、回数制限を設けてあげます。
考え方が面倒ですが、N回以下なら試すとしたいのでN以下の数値のリストを作るrangeを作成しましょう。

range(Min, Max, List) :-
  integer(Min),
  integer(Max),
  Min < Max,
  List = [Min|T],
  N is Min + 1,
  range(N, Max, T).
range(X, X [X]).

isという演算子が初めて出てきましたが、まあ、意味的には予想通りです。
この場合N = Min + 1とは出来ない事に注意が必要です。

これでrange(0, 5, X).でX = [0,1,2,3,4,5]が取得できます。

hanoi(X, M, N, Y) :- % 移動回数は最大N回まで
  range(0, N, R),
  hanoi(X, M, R, Y).
hanoi(X, M, [H|_], Y) :- % H回の移動で出来る組み合わせ
  length(M, H),
  hanoi(X, M, Y).
hanoi(X, M, [_|T], Y) :- 
  hanoi(X, M, T, Y).

完了です。
試してみましょう。

| ?- hanoi([[1], [], []], M, 1, [[], [], [1]]).

M = [left_to_right] ? a

(1 ms) no
| ?- hanoi([[1, 2], [], []], M, 1, [[], [], [1, 2]]).

(1 ms) no
| ?- hanoi([[1, 2], [], []], M, 2, [[], [], [1, 2]]).

no
| ?- hanoi([[1, 2], [], []], M, 3, [[], [], [1, 2]]).

M = [left_to_middle,left_to_right,middle_to_right] ? a

(2 ms) no
| ?- hanoi([[1, 2, 3], [], []], M, 7, [[], [], [1, 2, 3]]).

M = [left_to_right,left_to_middle,right_to_middle,left_to_right,middle_to_left,middle_to_righ,left_to_right] ? a

(1591 ms) no

こういう感じで結果がでます。

解き方を気にせず答えを求められるのが素晴らしいところですね。

ちなみに

このプログラムのままだと、円盤が4つ以上あるハノイの塔にチャレンジするとものすごく時間がかかります。
チューニング方は色々あるのですが、まあ、単純に可能性が無い奴はすぐエラーにしてしまうという方法で実行速度を上げることができます。

それは今回は扱わないと言うことで。

来世から頑張る！！

技術ブログを目指して

簡単に分かるPrologの魅力