How do I write a palindrome program while using different lists?

Question

I tried to write a palindrome program by using lists. However, I have to use difference lists and output should be:

The i^th element of the list is the same of (n-i+1)^th element of the list and n is the length of the list. For example, [a,X,c,b,Y] should give X = b and Y = a.

So far I have implemented:

% length of the list 
len([], 0).
len([H|T], B) :-
   len(T, NT),
   B is NT + 1.

% return the ith element of the list 
match([H|_], 0, H) :-
   !.
match([_|T], N, H) :-
   N > 0,
   N1 is N-1,
   match(T, N1, H).

How do I complete this?

Answer 1

Use definite clause grammars!

DCG, a major Prolog feature, makes using difference lists easy—enabling you to write concise and efficient code with little effort!

Want to know more? Just follow the dots:

• DCG has its own tag on StackOverflow, dcg.

• en.wikipedia.org has an extensive article on DCG.

• For a jumpstart, read the DCG primer by Markus Triska!

Without any further ado, let's get to the code:

palindrome --> [].
palindrome --> [_].
palindrome --> [X], palindrome, [X].

% Alternatively, we could also use the following more compact definition:
palindrome --> [] | [_] | [X], palindrome, [X].

Done. Let's run a few queries! First, the query the OP gave:

?- phrase(palindrome, [a,X,c,b,Y]).
   X = b, Y = a
;  false.

In German, "corn" is called "mais". If we put "siam" (the old name of "the Kingdom of Thailand") in front, we get a delicious palindrome:

?- set_prolog_flag(double_quotes, chars).
true.

?- phrase(palindrome, "siammais").
   true
;  false.

?- phrase(palindrome, "siamais").       % or kick one middle 'm' character
   true                                 % ... for an odd-length palindrome
;  false.

At last, let's not forget about the most general query:

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

---

On the prolog-toplevel we can use the built-in Prolog predicate listing/1 to peek at the code the DCG was "translated" to—at this level the internal use of difference-lists becomes apparent:

?- listing(palindrome//0).
palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
    palindrome(A, B),
    B = [C|D].

true.