Understanding difference lists (Prolog)

Question

I'm having trouble understanding difference list, particularly in this predicate:

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

Could anyone help me follow what's happening?

Answer 1

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

Seeing the arguments to this predicate as a difference list, the first clause says, a list from A to A (i.e., an empty list) is a palindrome.

The second clause says, a one-element list is a palindrome, whatever that one element is.

---

Don't panic!  Difference lists are just lists with explicit end "pointer"

A normal list, say [1,2,3], is a difference between its start and its end; the end of a normal list is always an empty list, []. That is to say, for a list [1,2,3] we are supposed to call this predicate as palindrome( [1,2,3], []) — namely, check whether the difference list [1,2,3] - [] is a palindrome.

From the operational point of view, a difference list is nothing but a (possibly open-ended) list with explicitly maintained "end pointer", for example: A - Z where A = [1,2,3|Z] and Z = []. Indeed, [1,2,3|[]] is the same as [1,2,3]. But when Z is not instantiated yet, the list A is still open ended - its "end pointer" Z can be instantiated to anything (but only once, of course, sans the backtracking).

If we were to instantiate Z later to an open-ended list, say, Z = [4|W], we'd get a new, extended difference list A - W where A = [1,2,3,4|W]. The old one would become A - Z = [1,2,3,4|W] - [4|W], i.e. still representing a prefix [1,2,3] of an open-ended list [1,2,3,4 ...]. Once closed, e.g. with W = [5], all the pairs of logvars still represent their corresponding difference lists (i.e. A - Z, A - W ...), but A is not open-ended anymore, so can't be extended anymore.

Instead of using the - functor, it is customary to just use both parts of the diff list definition as separate arguments to a predicate. When we always use / treat them as if they were two parts of a pair, then they form a pair, conceptually. It's the same thing.

---

Continuing. The third clause says, for [C|A]-D to be a palindrome, A-B must be a palindrome, and B must be [C|D]. A, D, B are lists, C is an element of a list. This might be confusing; let's use V instead. Also, use Z and Y instead of D and B, to remind us of "the end" of a list:

palindrome([V|A], Z):- palindrome(A, Y), Y=[V|Z].

V ................. V ----
  ^                 ^ ^
  |                 | |
  |                 | Z
  A                 Y = [V|Z]

Indeed, when the ...... core is a palindrome, putting two Vs around it gives us another palindrome.

Answer 2

The following is a summary that hopefully distills the best of the previous discussion, and adds one small but significant simplification.

First, the original question should be understood in the context of the problem at hand, which can be formulated as defining a Prolog predicate which will check whether a list is a palindrome, or more generally to generate palindromes. We wish to explore an implementation using difference lists, so we can begin as follows:

% List is a palindrome if List - [] is a palindrome:
palindrome( List ) :- palindrome(List, []).  

(As explained elsewhere, if a list, List, is the concatenation of two lists Front and Back, then Front can be viewed as being the difference between List and Back, that is, Front can be regarded as equivalent to (List - Back).)

To define palindrome/2, we begin with the two "base cases", an empty list and a singleton:

% The empty list (L-L) is a palindrome:
palindrome(L, L).

% A singleton list, ([X|L] - L), is a palindrome:
palindrome([X|L], L). 

Let us now turn to the general case.

If a list with more than one element is to be a palindrome, then it will look like this: E ... E

where ... is a (possibly empty) palindrome.

Tacking on a tail, Tail, our list must look like: E ... E Tail

Writing this regular list as [E|Rest], we can now see that the original list ( [E|Rest] - Tail ) is a palindrome if (Rest - [E|Tail]) is a palindrome, or in terms of our predicate palindrome/2:

palindrome( [E|Xs], Tail ) :- palindrome(Xs, [E|Tail]).

It's easy to see that this is equivalent to the original formulation.

That's it! Now we can, for example, generate templates for palindromes:

?- palindrome( X ).
X = [] ;
X = [_G1247] ;
X = [_G1247, _G1247] ;
X = [_G1247, _G1253, _G1247] ;
X = [_G1247, _G1253, _G1253, _G1247] 
....