Skip to content
2009/03/26 / highmt

素朴なreverseは停止しない

お気楽 Prolog プログラミング入門で少しだけ(リスト操作まで)お勉強。

処理系はSWI-Prologを使用した。

素朴にreverseを定義すると、

my_reverse([], []).
my_reverse([X|Xs], Y) :- my_reverse(Xs, Y1), append(Y1, [X], Y).

とか

my_reverse2(X, Y) :- my_reverse2(X, [], Y).
my_reverse2([], N, N).
my_reverse2([X|Xs], M, N) :- my_reverse2(Xs, [X|M], N).

とかになる。

これは、

my_reverse([a,b,c],X).

みたいな使い方なら問題ないが、

my_reverse(X,[a,b,c]).

みたいに使うと、1つ目の答えを返した後、停止しない(きっと。my_reverse2はわりとすぐにスタックを使い果たす)。
my_reverseの場合、my_reverse(Xs, Y1)のところで
1回目はmy_reverse([], [])により成功するが、
その後ここにバックトラックで戻ってきたときに、XsもY1もフレッシュな値(という言い方でよいのだろうか)になってしまうから。

一方、もともと定義されているreverseのほうは

lists:reverse([], A, A, []).
lists:reverse([B|A], C, D, [_|E]) :- reverse(A, [B|C], D, E).
reverse(A, B) :- reverse(A, [], B, B).

となっていて、第4引数があるおかげで確実に止まるようになっている。

Prologは手続きを書かないといいながら、
やっぱり実行のイメージがないとなかなか使えないんだろうか。
実行時間の見積りとか難しそうだし。

そこでETなんだろうか。

広告
%d人のブロガーが「いいね」をつけました。