Prolog Course Section: Verifying Palindromes for Input Lists

A palindrome is a sequence that reads the same forwards and backwards (e.g., $[r,a,c,e,c,a,r]$). In Prolog, this is naturally expressed with recursion and pattern matching on lists: compare the first and last elements, then recurse on the inner sub-list. This section builds a predicate such as palindrome/1 and a wrapper goal that prints Yes/No.

Key ideas you’ll use:

• Use list decomposition via pattern matching like $[H|T]$.
• Define base cases (empty list, single-element list).
• Recurse by removing matching outer elements.
• Optionally handle the “middle” correctly by stopping when the list becomes length 0 or 1.

⚠️ Note: Prolog can implement palindrome checking either by (1) reversing a list and unifying, or (2) recursively matching from both ends without a full reverse. This course uses a recursive approach that is conceptually clear for learning, while also mentioning a reverse-based option.

1) Core definition (palindrome using outer-element comparison)

In Prolog, list pattern matching lets you reason in terms of “outer” elements. A standard technique is to implement helpers that:

• extract the last element of a list, and
• return the list without that last element (so you can recurse on the inner portion).

Example program

1% --- Helper: last element and the list before it ---
2% last_elem([a,b,c], c, [a,b]).
3last_elem([X], X, []).
4last_elem([H|T], X, [H|Rest]) :-
5    last_elem(T, X, Rest).
6
7% --- Palindrome predicate ---
8% palindrome([]).
9% palindrome([_]).
10palindrome([]).
11palindrome([_]).
12palindrome(List) :-
13    List = [First|_],
14    last_elem(List, Last, WithoutLast),
15    First = Last,
16    % WithoutLast now is the list with last removed; remove the first too by taking its tail
17    WithoutLast = [_|Inner],
18    palindrome(Inner).

How it works

• For $L=[]$ or $L=[_ ]$, palindrome/1 succeeds immediately.
• Otherwise:
  1. Bind the first element to First.
  2. Use last_elem/3 to get Last and WithoutLast.
  3. Require First = Last.
  4. Remove the first element from WithoutLast to obtain the inner list Inner.
  5. Recurse.

keyword In Prolog, = is unification (it can bind variables, or check equality for already-bound terms).

2) Match the exact assignment output: Yes / No

Prolog itself typically answers with true/false, but you can add a wrapper that prints Yes or No based on whether palindrome/1 succeeds.

1check_palindrome(List) :-
2    ( palindrome(List) ->
3        writeln('Yes')
4    ;
5        writeln('No')
6    ).

Example usage

• ?- check_palindrome([r,a,c,e,c,a,r]). prints Yes
• ?- check_palindrome([a,b,c]). prints No

keyword A goal is a predicate call you ask Prolog to prove (e.g., palindrome(List)).

3) Alternative (simpler) approach: compare to reverse

A more compact approach is:

1. Compute the reversed list.
2. Check whether the original equals the reversed list.

However, this can be less instructive because it relies on reverse/2 or a custom reverse implementation.

Pseudocode idea:

• palindrome(L) :- reverse(L, R), L = R.

If you want the “learning” version, prefer the outer-to-inner recursion shown earlier.