Adventures in Prolog - Computations with lists VII

Again, as I am quite busy these days, I will present some not recent predicates, just to keep the flow going. Quite recently, I have seen the world of depth, breadth and intelligent search in Prolog. For this, I am working on an implementation of the 8-queens problem. Unfortunately, this is nothing to show off at the moment. But probably in 2 weeks or so, I will be able to show present it here and demonstrate how elegantly one may solve problems using Prolog.

Today's post is about the detection of a palindrome using Prolog. A palindrome is defined as some word that can be read from start to end or end to start and it will not change. For example, the word ANNA is a palindrome.

Now, using the idea that a palindromic word is a word that can be read back and forth and does not change, we come with the following ...

Let X be some word. If X is the empty word then it is a palindrome. If X is not the empty word then let Y be the reverse of X. If Y equals X, X is a palindromic word. Instead of focussing on words, we focus on lists.

%palin/1 X is a palindrome
palin([]).
palin(X) :- revList(X, Y), X = Y.

A more succinct version of the above would avoid the additional test of equality, i.e. lead to the following predicate:

palin(X) :- revList(X, X).

Which clearly is the the same, i.e. if reversing X leads to X, then clearly, X has to be palindromic. revList is a binary predicate that takes a list as input and outputs the reverse list.

Adventures in Prolog - Computations with lists VI

Today's post is merely to get the flow going and the blog updated. That is it is about the simple concatenation of two lists. Just like the append predicate appends some element at the end of a list, concatenate_list joins two lists by recursively reducing one list until it is the empty list.

%concatenate_list/3
concatenate_list([], List, List).
concatenate_list([H1¦T1], [H2¦T2], [H1¦T3]) :-
concatenate_list(T1, [H2¦T2], T3).