Prolog: Test if an arbitrary list is symmetric
Is there a way to test wether an arbitrary list is symmetric?
For example:
?- symmetric([a,b,b,a]).
true.
?- symmetric([a,b,c,a]).
false.
?- symmetric([a,a]).
true.
My attemp was to compare the first element to the last element and if they are equal to remov开发者_StackOverflow中文版e them and proceed with the rest of the list; otherwise fail. Succeed if the list has 2 elements and they are equal. Otherwise fail.
However "finding" the end of the list using this predicate is not really performant:
last(L,[L]).
last(L,[H|T]):-last(L,T).
Does anyone know of a good way to do this? Any help would really be appreciated!
Btw: I don't care for lists with an uneven amount of elements.
I found the answer to my question.
A symmetric list is a palindrome (Sometimes you don't see see the forest for the trees)... And this simple predicate tests for that:
is_palindrome(L) :- reverse(L,L).
But your algorithm was interesting nevertheless. There is a last/2
built-in (at least in SWI Prolog) that doesn't suffer from the performance penalty of your recursive approach. With this, here is a version that implements your idea:
symmetric([]).
symmetric([L]).
symmetric([H|T]):-
last(T,H), % this forces the last element to equal the first
append(T1,[H],T), % this deconstructs the rest list in one without the last elem.
symmetric(T1). % and recurses on that
Interesting is the use of the append/3
predicate, to deconstruct the initial rest list into the rest list without the last element.
EDIT: I realized I can do even without last/2
, just with append/3
. So here is the improved version:
symmetric([]).
symmetric([L]).
symmetric([H|T]):-
append(T1,[H],T), % deconstruct and assure symmetry
symmetric(T1). % and recurse
Now, here append
does both, the deconstruction to get T1, as well as assuring that the last element of the list matches the first :-).
精彩评论