Converting a Prolog Function to a Difference List Functor

Question

I am working on my homework for Prolog (SWI) but cannot figure out how to do this:

I have a functor:

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

which indicates whether the given list is a palindrome.

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

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

Can someone please explain this to me?

Answer 1

For this list of length n, your solution needs some O ( n ² ) conclusions: n (actually n / 2 ) for palindrome / 1 and i for each append/3 that just searches and compares the end.

The easiest way to reformulate your definition is using grammars (DCGs), which are a convenient way to use difference lists. Please note that each grammar rule corresponds to a sentence 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 using listing(palindrome) .

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

So now this is your definition using difference lists.

Answer 2

Just write it yourself. You

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

Add append(AB,BC,AC) for diff lists, so calling append gives us Z2=[A|Z3], Z3=Z, Middle=T and so (writing out the two halves of the diff-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 convenient interface for difference lists.