Prolog - Palindrome Functor

Question

I am trying to write a predicate palindrome/1 in Prolog that is true if and only if its list input consists of a palindromic list.

for example:

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

is true.

Any ideas or solutions?

Selfemployed

you realise you can delete it yourself? - ok question has now been edited - it originally said "Please delete this"... – Blankly

Sorry, this question has answers and cannot be deleted. – Selfemployed

Answer 1

A palindrome list is a list which reads the same backwards, so you can reverse the list to check whether it yields the same list:

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

Gaspard

Thanks ... SO basically, I have to create a .pl file add this predicate to it and consult it into GNU prolog. right? – Selfemployed

Answer 2

Looks that everybody is voting for a reverse/2 based solution. I guess you guys have a reverse/2 solution in mind that is O(n) of the given list. Something with an accumulator:

 reverse(X,Y) :- reverse(X,[],Y).

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

But there are also other ways to check for a palindrome. I came up with a solution that makes use of DCG. One can use the following rules:

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

Which solution is better? Well lets do some little statistics via the profile command of the Prolog system. Here are the results:

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

Bye

P.S.: Port statistics done with new plugable debugger of Jekejeke Prolog:
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 facilities. For more info see, "Code Profiler" column:
http://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations

Niemann

I'm not sure, but it may be the case that reverse is a primitive, so that counting CERFs wouldn't be appropriate. And since it sounded like OP was new to Prolog, it seems just mean to throw a whole new syntax at him/her :). Nice addition to the topic, though. – Spectrophotometer

Answer 3

This sure sounds like a homework question, but I just can't help myself:

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

Technically, prolog functor don't "return" anything.

Spectrophotometer

Prolog will reply "yes", indicating it has successfully satisfied your query. And to load this program, you can do so directly from the prompt (using 'assert'), though it is much easier to put it in a file and consult that file. – Spectrophotometer

Answer 4

Another way, doing it with DCG's:

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

You can check for a palindrome like this:

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

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

Pointing

Answer 5

You can use :

palindrome([]).
palindrome([_]).
palindrome([X|Xs]):-append(Xs1,[X],Xs), palindrome(Xs1).

Orson