Making a reverse list

Question

I have the following codes. Trying to make a reverse list. but it doesnt work.

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

I run this in prolog and I get this:

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.

this should give me [3,2,1], instead of [1,2,3]. what is going wrong here??

Answer 1

When a list is empty, its reverse is empty. So

reverse([], []).

In another case, you append the first element of the list at the end of the revese of the rest of the list. so :

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

Answer 2

You almost got it right. What you need is an "accumulator" which collects the result so far and passes it to the return variable at the end of the recursion:

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

Otherwise the reversed list is forgotten as the function returns from the recursive calls. You need to instantiate the accumulator with an empty list when you call reverse/3:

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

If you do the trace you will see that the second argument does not get instantiated until your original list is empty.