prolog - 制作反向列表

Question

我有以下代码。试图做一个反向列表。但它不起作用。

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.

这应该给我 [3,2,1]，而不是 [1,2,3]。这里出了什么问题？

Answer 1

当列表为空时，其反向为空。所以

reverse([], []).

在另一种情况下，您将列表的第一个元素附加到列表其余部分的末尾。所以 ：

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

Answer 2

你几乎做对了。您需要的是一个“累加器”，它收集到目前为止的结果并在递归结束时将其传递给返回变量：

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

否则，当函数从递归调用返回时，会忘记反向列表。调用时需要用空列表实例化累加器reverse/3：

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

如果您进行跟踪，您将看到第二个参数在您的原始列表为空之前不会被实例化。