Convert Prolog functor to functor with difference lists

Question

I'm working on my homework for Prolog (SWI) but can't figure out how to get this done:

I have the functor:

palindrome([]).
palindrome([_]).
palindrome([A|T]) :-
      append(Middle,[A],T),
      palindrome(Middle).

which tells if a given list is a palindrome.

For my homework I have to write a functor palindrome/2 without append/3 and with difference lists.

I know a difference list is a form of [Y|X]-X, but I don't understand how to use this and how this can replace the append functor.

Can somebody please explain this to me?

Answer 1

For a given list of length n, your solution needs some O(n²) inferences: n (actually n/2) for palindrome/1 and i for each append/3 which simply searches and compares the end.

The most straight forward way to reformulate your definition uses grammars (DCGs) that are a convenient way to use difference-lists. Note that each grammar rule corresponds to a clause in your program.

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

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

For convenience, here is the same grammar written more compactly:

palindrome --> [] | [_] | [A], palindrome, [A].

Now, how are these grammar rules implemented? The easiest way is to look at the actual definition with listing(palindrome).

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

So this is now your definition using difference-lists.

Answer 2

Just write it down yourself. You have

palindrome([]).           % palindrome(Z-Z).
palindrome([_]).          % palindrome([_|Z]-Z).
palindrome([A|T]) :-      % palindrome([A|T]-Z):-
  append(Middle,[A],T),   %   append(Middle-Z2,[A|Z3]-Z3,T-Z),
  palindrome(Middle).     %   palindrome(Middle-Z2).

Append for dif-lists is append(A-B,B-C,A-C), so the append call gives us Z2=[A|Z3], Z3=Z, Middle=T, and so (writing out the two halves of a dif-list as two arguments for the predicate),

palindrome(Z,Z).
palindrome([_|Z],Z).
palindrome([A|T],Z) :-
  palindrome(T, [A|Z]).

Now you can run it

10 ?- palindrome(X,[]).

X = [] ;
X = [_G340] ;
X = [_G340, _G340] ;
X = [_G340, _G346, _G340] ;
X = [_G340, _G346, _G346, _G340] ;
....

11 ?- X=[a,b,c|_],palindrome(X,[z]).

X = [a, b, c, b, a, z] ;
X = [a, b, c, c, b, a, z] ;
X = [a, b, c, _G460, c, b, a, z] ;
X = [a, b, c, _G460, _G460, c, b, a, z] ;
....

16 ?- palindrome([1,2,2,1,0],Z).

Z = [1, 2, 2, 1, 0] ;
Z = [2, 2, 1, 0] ;
Z = [0] ;
No

Of course, DCG rules provide a comfortable interface to difference-lists.