Reversing a List in Prolog

Question

I have finished a homework assignment for my programming class. I was supposed to create a Prolog program that reverses a list. I, however, am having trouble understanding why exactly it works.

%1. reverse a list
%[a,b,c]->[c,b,a]

%reverse(list, rev_List).
reverse([],[]).  %reverse of empty is empty - base case
reverse([H|T], RevList):-
    reverse(T, RevT), conc(RevT, [H], RevList).  %concatenation

What exactly is RevT in this case? I know it is supposed to represent the reverse of T or the rest of the given list, but I don't see how it could have any value as I haven't assigned it to anything. Does it just serve the same purpose as RevList but for each recursive call?

Also, why do I have to use [H] instead of just H in my conc() function call? Doesn't H refer to the head of the list (ex: [H])? Or does it just refer to the item at the head of the list (just H)?

Please help clear this up for me. I am struggling to understand the logic behind this type of programming.

Answer 1

Your solution explained: If we reverse the empty list, we obtain the empty list. If we reverse the list [H|T] , we end up with the list obtained by reversing T and concatenating with [H] . To see that the recursive clause is correct, consider the list [a,b,c,d] . If we reverse the tail of this list we obtain [d,c,b] . Concatenating this with [a] yields [d,c,b,a] , which is the reverse of [a,b,c,d]

Another reverse solution:

 reverse([],Z,Z).

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

call:

?- reverse([a,b,c],X,[]).

For further information please read: http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25