Prolog program firstlast without recursion?

Question

How would I write a prolog program like the one below that succeeds if the list has the same first and last element but without recursion using the append predicate only?

firstlast([H,H]).
firstlast([F,_|T]) :- firstlast([F|T]).

Sample queries:

?- firstlast([1,2,3,1]).
Yes

?- firstlast([1,2,3]).
No

Answer 1

I think your predicate is missing an edge-case: the singleton list: in a list with exactly one elements, the first and last element are the same.

firstlast([_]).
firstlast([H,H]).
firstlast([F,_|T]) :- firstlast([F|T]).

You can use append/3 to obtain the last element with:

last(L, Last) :-
    append(_, [Last], L).

This work since appending the [Last] to an certain list can only result in a list with Last as last element. Since that list is L, and append/3 can work in that direction, we thus can obtain the last element. For example:

?- append(_, [Last], [1,4,2,5]).
Last = 5 ;
false.

I think with this hint, you should be able to solve the problem without recursion.

Answer 2

You'll need to use a pre-defined Prolog predicate of some kind if you aren't going to use recursion. A simple solution could use reverse/2.

firstlast([H|T]) :- reverse([H|T], [H|_]).

This creates a nice, general solution:

| ?- first_last(L).

L = [_] ? ;

L = [A,A] ? ;

L = [A,_,A] ? ;

L = [A,_,_,A] ? ;

L = [A,_,_,_,A] ?
...

If you want to ensure that the list has at least two elements, then use an additional element:

firstlast([X,Y|T]) :- reverse([X,Y|T], [X|_]).

Yielding:

| ?- firstlast(L).

L = [A,A] ? ;

L = [A,_,A] ? ;

L = [A,_,_,A] ? ;

L = [A,_,_,_,A] ?
...