Reversing a List in Prolog

Question 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

Question 2

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.

Question 3

Consider using a DCG instead, which is much easier to understand:

reverse([])     --> [].
reverse([L|Ls]) --> reverse(Ls), [L].

Example:

?- phrase(reverse([a,b,c]), Ls).
Ls = [c, b, a].

Question 4

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?

Variables in Prolog are 'placeholders' for relations' arguments. What we know, after a successful call, it's exactly that the specified arguments hold for that relation.

Then RevT will have a value, if the call succeed. Specifically, will be the last argument of the call conc(RevT, [H], RevList), when the list is not empty. Otherwise, will be the empty list.

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)?

Yes, H refers to the first item (usually called element) of the list, then we must 'reshape' it to be a list (of just 1 element), as required by conc/3, that is another relation among lists.

Question 5

Just a note on testing reverse/2 predicate definitions, too long to fit a comment.

Reversing a list is the "hello world" example for introducing QuickCheck, which means that you can use it for helping in testing your definition. First, we define a property that holds for the reverse/2 predicate: reversing a list twice must give the original list, which we can translate to:

same_list(List) :-
    reverse(List, Reverse),
    reverse(Reverse, ReverseReverse),
    List == ReverseReverse.

Using Logtalk's lgtunit tool QuickCheck implementation:

% first argument bound:
| ?- lgtunit::quick_check(same_list(+list)).
% 100 random tests passed
yes

% both arguments unbound
| ?- lgtunit::quick_check(same_list(-list)).
% 100 random tests passed
yes

Or simply:

% either bound or unbound first argument:
| ?- lgtunit::quick_check(same_list(?list)).
% 100 random tests passed
yes

But we need another property definition to test with the second argument bound:

same_list_2(Reverse) :-
    reverse(List, Reverse),
    reverse(List, ListReverse),
    Reverse == ListReverse.

We can now do:

% second argument bound:
| ?- lgtunit::quick_check(same_list_2(+list)).
% 100 random tests passed
yes

But note that this property-based/randomized testing do not check for the non-terminating cases as these only occur when backtracking after the first solution.

Question 6

The following is the typical implementation of reverse/2 . It does however have the problem as marked bellow with "non-termination" .

?- ['/dev/tty'] .

reverse(_source_,_target_) :-
reverse(_source_,_target_,[])  .

reverse([],_target_,_target_)  .

reverse([_car_|_cdr_],_target_,_collect_) :-
reverse(_cdr_,_target_,[_car_|_collect_])  .

end_of_file.

.

?- reverse([],Q) .
Q = []

?- reverse([a],Q) .
Q = [a]

?- reverse([a,b],Q) .
Q = [b,a]

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

?- reverse(P,[]) .
P = [] ? ;
%% non-termination ! %%
^CAction (h for help): a

?- reverse(P,[a]) .
P = [a] ? ;
%% non-termination ! %%
^CAction (h for help): a

?- reverse(P,[a,b]) .
P = [b,a] ? ;
%% non-termination ! %%
^CAction (h for help): a

?- reverse(P,[a,b,c]) .
P = [c,b,a] ? ;
%% non-termination ! %%
^CAction (h for help): a

Question 7

:- op(2'1,'fy','#') .
:- op(2'1,'fy','##') .
:- op(2'1,'fy','###') .

'reverse/2' .

/* The following is an implementation of reverse/2 that I just invented that does not suffer from a non-termination problem for reverse(P,[]) . */

'implementation' .

    reverse(_source_,_target_) :-
    reverse(_source_,_target_,_source_,_target_,[],[]) .

    reverse(_source_,_target_,[],[],_target_,_source_)  .

    reverse(_source_,_target_,[_source_car_|_source_cdr_],[_target_car_|_target_cdr_],_source_collect_,_target_collect_) :-
    reverse(_source_,_target_,_source_cdr_,_target_cdr_,[_source_car_|_source_collect_],[_target_car_|_target_collect_])  .

'testing' .

'testing : part 1' .

    /*
    ?- reverse([],Q) .
    Q = []

    ?- reverse([a],Q) .
    Q = [a]

    ?- reverse([a,b],Q) .
    Q = [b,a]

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

'testing : part 2' .

    /*
    ?- reverse(P,[]) .
    P = []

    ?- reverse(P,[a]) .
    P = [a]

    ?- reverse(P,[a,b]) .
    P = [b,a]

    ?- reverse(P,[a,b,c]) .
    P = [c,b,a]
    */

'testing : part 3' .

    /*
    ?- reverse(P,Q) .
    P = Q = [] ? ;
    P = Q = [_A] ? ;
    P = [_A,_B],
    Q = [_B,_A] ? ;
    P = [_A,_B,_C],
    Q = [_C,_B,_A] ? ;
    P = [_A,_B,_C,_D],
    Q = [_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E],
    Q = [_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F],
    Q = [_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G],
    Q = [_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H],
    Q = [_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I],
    Q = [_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J],
    Q = [_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K],
    Q = [_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L],
    Q = [_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M],
    Q = [_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N],
    Q = [_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O],
    Q = [_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P],
    Q = [_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q],
    Q = [_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R],
    Q = [_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S],
    Q = [_S,_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T],
    Q = [_T,_S,_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
    P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T,_U],
    Q = [_U,_T,_S,_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? 
    */