代码之家 › 专栏 › 技术社区 › Chris

序言:测试任意列表是否对称

symmetric prolog list

-1

Chris · 技术社区 · 16 年前

?- symmetric([a,b,b,a]).
true.

?- symmetric([a,b,c,a]).
false.

?- symmetric([a,a]).
true.

但是,使用此谓词“查找”列表末尾并不是真正的性能:

last(L,[L]).
last(L,[H|T]):-last(L,T).

有人知道这样做的好方法吗?任何帮助都将不胜感激!

顺便说一句:我不喜欢元素数量参差不齐的列表。

2 回复 | 直到 16 年前

1

6

Chris 16 年前

我找到了我问题的答案。

对称列表是一个回文列表(有时你看不到森林中的树木)。。。这个简单的谓词测试:

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

2

ThomasH 16 年前

last/2 内置的(至少在SWI Prolog中),不会受到递归方法的性能损失。基于此,以下是一个实现您想法的版本:

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

有趣的是使用 append/3

编辑:我意识到即使没有我也可以 最后/2 ,只是 追加/3 . 下面是改进的版本:

symmetric([]).
symmetric([L]).
symmetric([H|T]):-
    append(T1,[H],T), % deconstruct and assure symmetry
    symmetric(T1).    % and recurse

append 这两种方法都可以,解构得到T1,并确保列表的最后一个元素与第一个匹配:-)。