Testing for Palindromes in Prolog

May 5, 2021 5-minute read

There are at least two common algorithms to determine if characters in a string form a palindrome;

Loop over the string using two indices. The first index starts at "zero" and increases by one character each loop. The second index starts at "string length minus one" and decreases by one character each loop. Compare the characters at each index and if equal continue looping. If not equal then exit, the string is not a palindrome. Continue looping until the first index is equal or greater than the second index, at this point the word is a palindrome.
Create a copy of and reverse the input string and if equal to the the original then the string is a palindrome.

Both algorithms require explicit conditional comparisons in the code. But we can accomplish the same result in a way that requires only pattern matching and implicit comparisons.

We want to equate the characters from the first half of the input string with a mirror of the characters in the second half of the string. If equal, then the string is a palindrome.

We can accomplish this by removing each character from the head of the input and adding characters to the head of a target, effectively reversing the input, comparing the target with the input as we go. Ending as soon as the input and target match, or we run out of characters from input. This is described in the example below.

A Palindrome

1
2
3
palindrome([a, b, b, a], []).   % not equal
palindrome([b, b, a], [a]).     % not equal
palindrome([b, a], [b, a]).     % equal

Because we are implementing this in Prolog, we prefer that the input is in the form of a list. It is straightforward to break an atom or string into a list of characers using the built in prolog predicate string_chars.

Let’s define the cases.

We suppose that an empty list and a list with a single element are both palindromes.

1
2
3
4
5
6
7
8
%% Palindrome Use Cases
%%
%% In = [], palindrome(In).                  % True
%% In = [a], palindrome(In).                 % True
%% In = [a, b], palindrome(In).              % False
%% In = [a, b, b, a], palindrome(In).        % True
%% In = [a, b, a], palindrome(In).           % True
%% In = [a, b, c], palindrome(In).           % False

This is where creating a solution using a declarative pattern matching language such as Prolog is interesting. All we need to test for an empty list is to define a "fact" as follows, which takes care of the first use case.

Fact for an Empty List

1
palindrome([], []).

To handle our first example, [a, b, b, a], and in fact, any use case having an even number of characters, we define a "rule" that evaluates to true when the same parameters are passed to both arguments.

Rule for an even number of characters

1
palindrome(Input, Input).

Notice that palindrome([], []) is a more specific case of palindrome(Input, Input) and therefore we can do away with the former. So palindrome(Input, Input) handles use cases #1, #3 and #4. But how to handle an odd number of characters for a palindrome like [k, a, y, a, k]?

Kayak

1
2
palindrome([y, a, k], [a, k]).
palindrome([a, k], [y, a, k]).

To handle an odd number of characters, we need a pattern that ignores the "head" and compares the "rest".

Rule for an odd number of characters

1
2
3
4
palindrome([_|T], T).

% This results in the following pattern
% palindrome([_|a, k], [a, k]).

So wiht just two predicates, we have handled all our use cases.

Now we need to define the predicate that moves characters from the Input to the Target list. Removing elements from, and adding elements to the head of a list is straighforward using pattern matching.

Adding to a list

1
2
3
4
5
6
7
8
?- A = [].
[]

?- A = [a | []].
A = [a]

?- A = [a | [b, b, a]].
A = [a, b, b, a].

Removing from a list

1
2
?- [_|T] = [a, b, b, a].
T = [b, b, a].

We can see how the predicate recurses through the list, removing characters from the input and building up the target list in reverse.

Recurse through the list

1
2
3
4
5
6
7
8
palindrome([Head|Tail], Acc) :-
    palindrome(Tail, [Head|Acc]).

% palindrome([a|b, b, a], []) :-
%    palindrome([b, b, a], [a]).

% palindrome([b|b, a], [a]) :-
%    palindrome([b, a], [b, a]).

As palindrome recurses, Prolog will attempt to match to a defined predicate. Which is why ordering of rules and predicates in the source file is important.

Finally, lets create the entry point.

Palindrome

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
%% palindrome("kayak")
palindrome(Input) :-
   string_chars(Input, CharList),   % Convert Input to a list of characters
   palindrome(CharList, []).        % Test for "palindromity"

%% And the rest of code, previously defined
palindrone(List, List).             % ([], []) and ([a, b], [a, b])
palindrome([_|Tail], Tail).         % ([_|[]], [[]]) and ([_| b, a], [b, a])
palindrome([Head|Tail], Acc) :-     % Recurse to reverse the Input.
    palindrom(Tail, [Head|Acc]).