开发者

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 :-).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜