Prologue - Palindrome

Question

I am trying to write the predicate palindrome/1 in Prolog, which is true if and only if its entry in the list consists of a palindrome list.

eg:

 ?- palindrome([1,2,3,4,5,4,3,2,1]). 

truly.

Any ideas or solutions?

Answer 1

A palindrome list is a list that reads the same back so you can cancel the list to check if it gives the same list:

 palindrome(L):- reverse(L, L). 

Answer 2

It seems that everyone is voting for a solution based on the opposite / 2. I think you guys have the inverse / 2 solution, i.e. O (n) of this list. Something with a battery:

  reverse(X,Y) :- reverse(X,[],Y). reverse([],X,X). reverse([X|Y],Z,T) :- reverse(Y,[X|Z],T). 

But there are other ways to test a palindrome. I came up with a solution that uses DCG. You can use the following rules:

  palin --> []. palin --> [_]. palin --> [Border], palin, [Border]. 

Which solution is better? Well, let's get some statistics through the Prolog system team profile. Here are the results:

So, perhaps the DCG solution is often faster in the positive case ("radar"), it does not have to collect the entire reverse list, but moves directly to the middle, and then checks the rest, leaving its own recursion. But the disadvantage of the DCG solution is that it is not deterministic. Some measurements of time will tell more ...

Bye

PS: port statistics with the new Jekejeke Prolog pluggable debugger:
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/10_dev/10_docu/02_reference/04_examples/02_count.html

But other Prolog systems have similar capabilities. For more information, see the Code Profiler column:
http://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations

Answer 3

It probably sounds like a homework question, but I just can't help myself:

 palindrome(X) :- reverse(X,X). 

Technically, a prolog functor returns nothing.

Answer 4

Another way: do it with DCG:

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

You can check the palindrome as follows:

 ?- phrase(palindrome,[a,b,a,b,a]). true. ?- phrase(palindrome,[a,b,a,b,b]). false. 

Answer 5

Check out this solution.

 palin(L):- palin(L,[]). palin(L,L). palin([_|T],T). palin([H|T],list):- palin(T,[H|list]).