-1

This is how to get palindrome using a reverse operation.

predicates

palin(list)
findrev(list,list,list)
compare(list,list)

clauses

palin(List1):-
    findrev(List1,[],List2),
    compare(List1,List2).

findrev([],List1,List1).

findrev([X|Tail],List1,List2):-
    findrev(Tail,[X|List1],List2).

compare([],[]):-
    write("\nList is Palindrome").

compare([X|List1],[X|List2]):-
    compare(List1,List2).    

compare([X|List1],[Y|List2]):-
    write("\nList is not Palindrome").

But I want to do it without reverse operation. Can somebody please help me.

Samitha Chathuranga
  • 1,689
  • 5
  • 30
  • 57
  • I don't give a solution but Consider **palin(List):- findrev(List,[],List).** For your question, you can use append([H|Tail], [H], Pal) and use recursivity on Tail. – joel76 Dec 15 '14 at 10:20
  • 2
    Why do you want to do it without reversing? What approach are you going to take, not in code, but at least in words? –  Dec 15 '14 at 10:55

5 Answers5

4

Why not

pal([]).
pal([_]).
pal(Pal) :-
    append([H|T], [H], Pal),
    pal(T).
joel76
  • 5,565
  • 1
  • 18
  • 22
  • append([H|T], [H], Pal) removes the first and last element of Pal, assuming that they are identicals (if not pal fails). and I keep on recursivily with T. – joel76 Jan 10 '18 at 08:17
4

In my opinion, the most elegant way is to use a DCG, as shown here:

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

Most general query:

?- phrase(palindrome, Ps).

Concrete example:

?- phrase(palindrome, [a,b,b,a]).
true .
Community
  • 1
  • 1
mat
  • 40,498
  • 3
  • 51
  • 78
2

Just match first and last elements.

first([F|L], F, L). % better inlined, but for clarity...
last(Es, L, R) :- append(R, [L], Es). % again...

palin([]).
palin([_]).
palin(L) :-
  first(L, E, X), last(X, E, Y), palin(Y).
CapelliC
  • 59,646
  • 5
  • 47
  • 90
1

Here's one option:

palindrome( Xs ) :- palindrome( Xs , [] , Xs ) .

palindrome( []     , Z , X ) .
palindrome( [X|Xs] , T , Z ) :- palindrome( Xs , [X|T] , Z ) .

Though it's really just rolling its own implementation of reverse/2.

Another option, using append/3:

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

A third option, avoiding append/3 completely:

palindrome( []      ) .                    % The empty list is a palindrome
palindrome( [X]     ) .                    % A single-element list is a palindrome.
palindrome( [X,Y|Z] ) :-                   % A list of more than one element is a palindrome, IF...
  first( Xs , X , L1 ) ,                   % The first element and
  last(  L1 , X , L2 ) ,                   % The last element are identical, AND
  palindrome(T2)                           % what's left over is a palindrome, too.
  .

first( [X|Xs] , X , Xs ) .      % getting the first item from a list is trivial.

last( [X]     , X , []    ) .   % getting the last item from a single element list is trivial, too.
last( [X,Y|Z] , L , [X|R] ) :-  % otherwise...add the head of the list to the leftovers list,
   last( [Y|Z] , L , R )        % - and recurse down on the tail
   .                            %
Nicholas Carey
  • 71,308
  • 16
  • 93
  • 135
0

A lot of these answers use last or append, which are expensive operations.

You can do half of a reverse and then check equality. The question stipulated not to use reverse, but this only uses a reverse like process, not a full reverse.

palindrome(Xs):- palindrome(Xs,[]).

palindrome(Xs, Xs).                    % [1,2,2,1] will get to pal([1,2],[1,2])
palindrome([X|Xs],Xs).                 % captures a case like [a,b,c,b,a]
palindrome([X|Xs],Ys):- palindrome(Xs, [X|Ys]).      % reverse-like process

One thing possibly missing from the above is cuts. Although no necessary here, should be used for good practice:

palindrome(Xs):- palindrome(Xs,[]).

palindrome(Xs, Xs):- !.                    % Don't need to redo after positive match
palindrome([X|Xs],Xs):- !.                 
palindrome([X|Xs],Ys):- palindrome(Xs, [X|Ys]).

Typical trace for a palindrome:

[trace] 88 ?- pal([1,2,1]).
   Call: (6) pal([1, 2, 1]) ? creep
   Call: (7) pal([1, 2, 1], []) ? creep
   Call: (8) pal([2, 1], [1]) ? creep
   Exit: (8) pal([2, 1], [1]) ? creep         % Matches rule - palindrome([X|Xs],Xs).
   Exit: (7) pal([1, 2, 1], []) ? creep
   Exit: (6) pal([1, 2, 1]) ? creep
true .

And a non-palindrome:

[trace] 87 ?- pal([1,2,3]).
Call: (6) pal([1, 2, 3]) ? creep
   Call: (7) pal([1, 2, 3], []) ? creep
   Call: (8) pal([2, 3], [1]) ? creep
   Call: (9) pal([3], [2, 1]) ? creep
   Call: (10) pal([], [3, 2, 1]) ? creep
   Fail: (10) pal([], [3, 2, 1]) ? creep      % Fails as [] doesn't equal [3,2,1] and can't be pulled apart
   Fail: (9) pal([3], [2, 1]) ? creep
   Fail: (8) pal([2, 3], [1]) ? creep
   Fail: (7) pal([1, 2, 3], []) ? creep
   Fail: (6) pal([1, 2, 3]) ? creep
false.
Whiskee
  • 63
  • 6