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.