Prologは（たぶん）面白い、あるいは「40 - 32 / 2 = 4!」Prolog篇ふたたび

前回「むずいよ」と音を上げたPrologでの挑戦。半年以上を経ての再挑戦です。

今回使用したPrologの実装はSWI-Prolog。本屋で手に取った参考書がSWI-Prologで解説されていたのでそれにならった次第。

• SWI-Prolog

今のスキルレベルでは数値演算以外をできそうもなかったので、題材は同じです。
コードでやっていることの裏付けはこちらのエントリを参照してみてください。

今回は、できる限り自分で書き下してみました。
このコードは、これまでのコードと一緒にGitHubにもアップしてあります。

• GitHub - mattsan/40-32-2-4

factorial(0, 1).
factorial(X, F) :- X > 0, X1 is X - 1, factorial(X1, F1), F is F1 * X.

for([N], N, N).
for([], Min, Max)  :- Min > Max.
for([N|L], Min, N) :- N > Min, N1 is N - 1, for(L, Min, N1).

cartesian_product(_, [], []).
cartesian_product([], _, []).
cartesian_product(N, M, L)   :- cartesian_product2(N, N, M, L).
cartesian_product2(_, _, [], []).
cartesian_product2([], N0, [_|MS], L) :- cartesian_product2(N0, N0, MS, L).
cartesian_product2([N|NS], N0, [M|MS], [[N, M]|L]) :- cartesian_product2(NS, N0, [M|MS], L).

verify([], _, _, []).
verify([[A, C]|CS], N, F, [[A, B, C]|R]) :-
  B is C * (A - F),
  (A - B) / C =:= N,
  A - (B / C) =:= F,
  verify(CS, N, F, R).
verify([_|CS], N, F, R) :- verify(CS, N, F, R).

unique([],[]).
unique([H|T], [H|U]) :- delete(T, H, V), unique(V, U).

gensets([], _, _, []).
gensets([A|AS], N, F, R0) :-
  Cmax is A div (A - F),
  for(CS, 2, Cmax),
  cartesian_product([A|AS], CS, R1),
  gensets(AS, N, F, R2),
  append(R1, R2, R0).

f(N, R) :-
  factorial(N, F),
  Amin is F + 1,
  Amax is F * 2,
  for(AS, Amin, Amax),
  gensets(AS, N, F, S),
  verify(S, N, F, R0),
  unique(R0, R),
  write(R),
  !.

実行。swiplがSWI-Prologを実行するコマンドです。
consult('40-32div2equal_factorial4.pl').でコードを読み込んでいます。
f(4, R).で答えが4!になるa,b,cの組み合わせのリストを出力させています。

$ swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.0.2)
Copyright (c) 1990-2011 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- consult('40-32div2equal_factorial4.pl').
% 40-32div2equal_factorial4.pl compiled 0.00 sec, 21 clauses
true.

?- f(4, R).
[ [40,32,2],[30,18,3],[25,5,5] ]

論理型言語とは

たとえばリストから重複を削除するuniqueを見てみると。

unique([],[]).
unique([H|T], [H|U]) :- delete(T, H, V), unique(V, U).

• 第1引数も第2引数も空リストであるか、
• 第1引数のリストの「先頭の要素（=H）」と第2引数のリストの「先頭の要素」が等しく、第1引数のリストから「『先頭の要素』と『先頭の要素と同じ値の要素を削除したリスト（=delete(T, H, V)）』」と第2引数のリストから「先頭の要素を削除したリスト（=U）」が等しい

…場合に成功する。

…成功する？「成功する」とは何か。

試してみるとわかるのですが。

?- unique([a,a,a,b,b,c], [a,b,c]).
true.

?- unique([a,a,a,b,b,c], [a,c]).
false.

確かに条件に合うリストを引数に与えると成功するし、条件に合わないリストを引数に与えると失敗します。

「重複をのぞいたリストを得る」ということをしたい場合は、第2引数を変数にします。

?- unique([a,a,a,b,b,c], R).
R = [a, b, c].

すると、成功する場合の値が第2引数の値になります。

…。

説明するための語彙が不足しているのが自分でもわかりすぎて困ります。

Prologプログラミングは新しいネタを探して続けていきたいと思います。

今回の参考書

Prologで学ぶAIプログラミング―「論理プログラミング」「Prolog」の入門から「人工知能」の基礎まで (I・O BOOKS)