prologでreverse

つかれた。

reverse(X,Y):-rev(X,[],Y).
rev([X|Xs],Z,Y):-rev(Xs,[X|Z],Y).
rev([],X,X).

答えをYに積んでいくパターン

[trace]  ?- reverse([1,2,3,4],X).
   Call: (7) reverse([1, 2, 3, 4], _G348) ? creep
   Call: (8) rev([1, 2, 3, 4], [], _G348) ? creep
   Call: (9) rev([2, 3, 4], [1], _G348) ? creep
   Call: (10) rev([3, 4], [2, 1], _G348) ? creep
   Call: (11) rev([4], [3, 2, 1], _G348) ? creep
   Call: (12) rev([], [4, 3, 2, 1], _G348) ? creep
   Exit: (12) rev([], [4, 3, 2, 1], [4, 3, 2, 1]) ? creep
   Exit: (11) rev([4], [3, 2, 1], [4, 3, 2, 1]) ? creep
   Exit: (10) rev([3, 4], [2, 1], [4, 3, 2, 1]) ? creep
   Exit: (9) rev([2, 3, 4], [1], [4, 3, 2, 1]) ? creep
   Exit: (8) rev([1, 2, 3, 4], [], [4, 3, 2, 1]) ? creep
   Exit: (7) reverse([1, 2, 3, 4], [4, 3, 2, 1]) ? creep
X = [4, 3, 2, 1].

このパターンを忘れるなかれ。

a([X|Xs],Z):-a(Xs,[X|Z]).
a([],_).

[trace]  ?- a([1,2,3],[]).
   Call: (7) a([1, 2, 3], []) ? creep
   Call: (8) a([2, 3], [1]) ? creep
   Call: (9) a([3], [2, 1]) ? creep
   Call: (10) a([], [3, 2, 1]) ? creep
   Exit: (10) a([], [3, 2, 1]) ? creep
   Exit: (9) a([3], [2, 1]) ? creep
   Exit: (8) a([2, 3], [1]) ? creep
   Exit: (7) a([1, 2, 3], []) ? creep
true.

traceを使わずにwriteでprintするデバッグもある。

reverse(X,Y):-rev(X,[],Y).
rev([X|Xs],Z,Y):-write([X|Xs]),write(','),writeln(Z),rev(Xs,[X|Z],Y).
rev([],X,X).

?- reverse([1,2,3],X).
[1, 2, 3],[]
[2, 3],[1]
[3],[2, 1]
X = [3, 2, 1].

formatでもいい。

reverse(X,Y):-rev(X,[],Y).
rev([X|Xs],Z,Y):-format('~p,\t~p\n',[[X|Xs],Z]),rev(Xs,[X|Z],Y).
rev([],X,X).