Prolog palindrome

I'm trying to write a palindrome function in Prolog. I know I could just use something like

palindrome(List) :- reverse(List, List).

But I'm trying to figure out a way without using the built in reverse. I've created my own reverse rule:

rev([], []).
rev([H|T], X) :- rev(T, Y), append(Y, [H], X).

And what I'd like is, given a list, say [a,b,c,d], I'd like to do something like "X = rev([a,b,c,d]), but I'm really not sure whether this is possible in Prolog.

If it is, the way I would write my palindrome function would be something like:

palindrome(List) :- append(L1, rev(L1), List).

Is it possible to do what I'm trying to do - i.e. X = rev([a,b,c,d])?.

Thanks.

Solution

Palindromes are lists that read the same from front to back and from back to front. So the example you have given, [a,b,c,d] and it's reversal, constitute a palindrome if the first is directly followed by the second: [a,b,c,d,d,c,b,a]. Since you are trying to describe specific kinds of lists, it is very tempting to use Prolog DCGs for the task. With them you can define palindromes like so:

palindrome(X) :-
   phrase(palindrome,X).

palindrome -->   % base case for even number of elements
   [].
palindrome -->   % base case for odd number of elements
   [A].
palindrome -->   % general case: a palindrome is
   [A],          % some element A...
   palindrome,   % ... followed by a palindrome ...
   [A].          % ... followed by element A

The most general query is producing palindromes with variables for each position:

   ?- palindrome(P).
P = [] ? ;
P = [_A] ? ;
P = [_A,_A] ? ;
P = [_A,_B,_A] ? ;
P = [_A,_B,_B,_A] ? ;
P = [_A,_B,_C,_B,_A] ?
...

Or alternatively you can test if a specific list is a palindrome:

   ?- palindrome("rats live on no evil star").
yes

   ?- palindrome([1,2,3,2,1]).
yes

   ?- palindrome([a,b,c,d]).
no

   ?- palindrome([a,b,c,d,d,c,b,a]).
yes

If you insist on using list reversal you can define the relation like so:

list([]) -->
   [].
list([X|Xs]) -->
   [X],
   list(Xs).

invlist([]) -->
   [].
invlist([X|Xs]) -->
   invlist(Xs),
   [X].

palindrome -->    % a paindrome is
   list(L),       % a list followed
   invlist(L).    % by its reversal
palindrome -->    % a palindrome is
   list(L),       % a list followed by
   [_A],          % some element
   invlist(L).    % then by the reversed list

The first of the above queries produces the answers in a different order now, namely the solutions with an even number of elements first:

   ?- palindrome(P).
P = [] ? ;
P = [_A,_A] ? ;
P = [_A,_B,_B,_A] ? ;
P = [_A,_B,_C,_C,_B,_A] ? 
...

The other example queries yield the same result. However, the first definition seems to be clearly preferable to me. Not only because it is shorter as there is no need for additional DCG rules but also because it is producing the results in a fair order: empty list, one element, two elements, ... With the second version you get all the lists with an even number of elements first and there are infinitely many of those. So you never get to see a solution with an odd number of elements with the most general query.