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

Prolog lists are simple data structures: ./2

• The empty list is the atom [].
• A list of one element, [a], is actually this structure: .(a,[]).
• A list of two elements, [a,b] is actually this structure: .(a,.(b,[]))
• A list of three elements, [a,b,c] is actually this structure: .(a,.(b,.(c,[])))
• and so on.

The square bracket notation is syntactic sugar to spare you from spending your life typing parentheses. Not to mention that it's easier on the eyes.

From this, we get the notion of the head of the list (the datum in the outermost ./2 structure) and the tail of the list (the sublist contained in that outermost ./2 data structure.

This is essentially, the same data structure you see for a classic singly-linked list in C:

struct list_node
{
  char payload ;
  struct list_node *next ;
}

where the next pointer is either NULL or another list structure.

So, from that, we get the simple [naive] implementation of reverse/2:

reverse( [] , []    ) .  % the empty list is already reversed.
reverse[ [X] , [X]  ) .  % a list of 1 item is already reversed. This special case is, strictly speaking, optional, as it will be handled by the general case.
reverse( [X|Xs] , R ) :- % The general case, a list of length >= 1 , is reversed by
  reverse(Xs,T) ,        % - reversing its tail, and
  append( T , [X] , R )  % - appending its head to the now-reversed tail
  .                      %

This same algorithm would work for reversing a singly-linked list in a more conventional programming language.

However, this algorithm is not very efficient: it exhibits O(n²) behavior, for starters. It's also not tail recursive, meaning that a list of sufficient length will cause a stack overflow.

One should note that to append an item to a prolog list requires traversing the entire list, prepending is a trivial operation, due to the structure of a prolog list. We can prepend an item to an existing list as simply as:

prepend( X , Xs , [X|Xs] ) .

A common idiom in prolog is to use a worker predicate with an accumulator. This makes the reverse/2 implementation much more efficient and (possibly) a little easier to understand. Here, we reverse the list by seeding our accumulator as an empty list. We iterate over the source list. As we encounter item in the source list we prepend it to the reversed list, thus producing the reversed list as we go.

reverse(Xs,Ys) :-            % to reverse a list of any length, simply invoke the
  reverse_worker(Xs,[],Ys) . % worker predicate with the accumulator seeded as the empty list

reverse_worker( []     , R , R     ).    % if the list is empty, the accumulator contains the reversed list
reverse_worker( [X|Xs] , T , R     ) :-  % if the list is non-empty, we reverse the list
  reverse_worker( Xs , [X|T] , R )       % by recursing down with the head of the list prepended to the accumulator
  .

Now you have a reverse/2 implementation that runs in O(n) time. It's also tail recursive, meaning that it can handle a list of any length without blowing its stack.

Answer 2

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