2

私は次のコードを持っています。逆のリストを作成しようとしています。しかし、それは機能しません。

reverse([],[H|T]).
reverse([H|T],Z) :- reverse(T,[H|Z]).

私はこれをプロローグで実行し、これを取得します：

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

これにより、[1,2,3]ではなく[3,2,1]が表示されます。ここで何が問題になっていますか？

4

2 に答える 2

7

リストが空の場合、その逆は空です。それで

reverse([], []).

別のケースでは、リストの残りの部分のレビューの最後にリストの最初の要素を追加します。それで ：

reverse([H|T],Z) :-
    reverse(T,Z1),
    append(Z1, [H], Z).
于 2013-02-25T15:58:32.307 に答える
2

あなたはほとんどそれを正しくしました。必要なのは、これまでの結果を収集し、再帰の最後にそれを戻り変数に渡す「アキュムレータ」です。

reverse([],Z,Z).
reverse([H|T],Z,Acc) :- reverse(T,Z,[H|Acc]).

そうしないと、関数が再帰呼び出しから戻るときに、逆のリストが忘れられます。次を呼び出すときに、空のリストを使用してアキュムレータをインスタンス化する必要がありますreverse/3。

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

トレースを実行すると、元のリストが空になるまで2番目の引数がインスタンス化されないことがわかります。

于 2013-02-25T17:18:17.430 に答える