Finding the Palindrome of a List using Prolog :- E

Question

I've been programming with java for the past 3 years, and I have just started learning Prolog. I downloaded SWI-Prolog to run my code on and trace, but I'm having trouble with this particular question.

/*concatinates 2 Lists together*/
 conc([],L,L).
 conc([X|T],L2,[X|T1]):-
     conc(T,L2,T1).

/*Finds the reverse a List*/    
reverse([],[]).
reverse([H|T],ReversedList):-
    reverse(T,Reverse),
    conc(Reverse,[H],ReversedList).

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

for example if I enter

palindrome([m,a,d,a,m]). 

L is [m,a,d,a,m] & L1 should be [m,a,d,a,m] returned from the reverse predicate.

L = L1 and output should be true. However an error is printed that I don't understand

ERROR: Type error: `[]' expected, found `[m,a,d,a,m]' (a list) ("x" must hold one character)
ERROR: In:
ERROR:    [9] [m,a|...]is[m,a|...]
ERROR:    [8] palindrome([m,a|...]) at c:/users/d/desktop/trial.pl:97
ERROR:    [7] <user>

My code works only if I change the predicate to:

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

I don't understand why since the logic is the same... L = L1 is the same as calling L1, L to begin with.

Also, this is the code for the predicate without using the reverse function. I'm having trouble understanding why we have the palidrome1([_]) base case & why if I don't place a bracket around [First] for the conc function, it returns false.

palindromel( [] ).
palindromel( [_] ).
palindromel( [First | Rest]) :-
    conc( Middle, [First], Rest), /*Do I have to put First in a list bracket?*/
    palindromel( Middle).

Any help would be appreciated.

Answer 1

However an error is printed that I don't understand.

The error that is causing the line is

L is L1

is/2 says:

-Number is +Expr

True when Number is the value to which Expr evaluates. 
Typically, is/2 should be used with unbound left operand. 
If equality is to be tested, =:=/2 should be used.

Since the left side is not a number and the right side is not an expression is/2 cannot be used.

---

I don't understand why since the logic is the same.

Actually the logic is not the same. is/2 is not the same as unification, =/2.

The reason

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

works because there is just one variable for both arguments to reverse/2. As such the input to reverse/2 and the result of reverse/2 must unify. In this case because the input and the output are the same if they are a palindrome, they can be unified.

Another way to see this is with this variation

palindrome(L1):-
    reverse(L1,L2),
    L1 = L2.

This time I used two different variables for reverse/2 but then did the unification as a separate step. The first way

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

is the same as this variation but in the first way the unification is factored out by using reverse(L,L).

---

I'm having trouble understanding why we have the palidrome1([_]) base case.

When I start creating code to solve a problem I work the problem out manually in my head or on paper. I start with the simplest cases and work toward the more complex. For palindromes, the simplest case is a word with no letters.

So if the input is an empty list [] the palindrome is an empty list []

palindromel( [] ).

The next harder case is a word with one letter which would be [_].

palindromel( [_] ).

The next harder case is a word with two letters which would be [A,A].

palindromel( [A,A] ).

and so on

 palindromel( [A,B,A] ).
 palindromel( [A,B,B,A] ).
 palindromel( [A,B,C,B,A] ).
 palindromel( [A,B,C,C,B,A] ).

To avoid having to create an endless list of clauses, recursion is used. However for palindrome the two easy cases become base cases for recursion and the rest are done using the base cases with the recursive clause.

if I don't place a bracket around [First] for the conc function, it returns false.

The reason I asked about "Prolog Programming for Artificial Intelligence" by Bratko is that in his book he has the students create conc/3 but doesn't note that it is really append/3. If you are using the book do yourself a favor and use append/3 instead as it has no bugs and odds are somewhere along conc/3 will fail while append/3 will work.

append/3 appends two list to create a third list. If you don't put [] around a single character then it is not a list but a character and append/3 or conc/3 will fail.