list - Prolog回文

Question

我正在尝试在 Prolog 中编写一个回文函数。我知道我可以使用类似的东西

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

但我正在尝试找出一种不使用内置反向的方法。我已经创建了自己的反向规则:

rev([], []).
rev([H|T], X) :- rev(T, Y), append(Y, [H], X).

我想要的是，给定一个列表，比如 [a,b,c,d]，我想做类似“X = rev([a,b,c,d]),但我真的不确定这在 Prolog 中是否可行。

如果是，我编写回文函数的方式将类似于:

palindrome(List) :- append(L1, rev(L1), List).

是否有可能做我想做的事 - 即 X = rev([a,b,c,d])?。

谢谢。

Answer 1

回文是从前到后和从后到前阅读相同内容的列表。因此，您给出的示例 [a,b,c,d] 如果第一个紧跟第二个，则构成回文:[a,b,c, d,d,c,b,a]。由于您正在尝试描述特定类型的列表，因此使用 Prolog DCG 来完成任务非常诱人。有了它们，您可以像这样定义回文:

palindrome(X) :-
   phrase(palindrome,X).

palindrome -->   % base case for even number of elements
   [].
palindrome -->   % base case for odd number of elements
   [A].
palindrome -->   % general case: a palindrome is
   [A],          % some element A...
   palindrome,   % ... followed by a palindrome ...
   [A].          % ... followed by element A

最一般的查询是为每个位置生成带有变量的回文:

   ?- palindrome(P).
P = [] ? ;
P = [_A] ? ;
P = [_A,_A] ? ;
P = [_A,_B,_A] ? ;
P = [_A,_B,_B,_A] ? ;
P = [_A,_B,_C,_B,_A] ?
...

或者您可以测试特定列表是否为回文:

   ?- palindrome("rats live on no evil star").
yes

   ?- palindrome([1,2,3,2,1]).
yes

   ?- palindrome([a,b,c,d]).
no

   ?- palindrome([a,b,c,d,d,c,b,a]).
yes

如果你坚持使用列表反转，你可以像这样定义关系:

list([]) -->
   [].
list([X|Xs]) -->
   [X],
   list(Xs).

invlist([]) -->
   [].
invlist([X|Xs]) -->
   invlist(Xs),
   [X].

palindrome -->    % a paindrome is
   list(L),       % a list followed
   invlist(L).    % by its reversal
palindrome -->    % a palindrome is
   list(L),       % a list followed by
   [_A],          % some element
   invlist(L).    % then by the reversed list

上面的第一个查询现在以不同的顺序产生答案，即首先具有偶数个元素的解决方案:

   ?- palindrome(P).
P = [] ? ;
P = [_A,_A] ? ;
P = [_A,_B,_B,_A] ? ;
P = [_A,_B,_C,_C,_B,_A] ? 
...

其他示例查询产生相同的结果。然而，第一个定义似乎显然更适合我。不仅因为它更短，因为不需要额外的 DCG 规则，而且因为它以公平的顺序产生结果:空列表，一个元素，两个元素，......在第二个版本中你得到所有列表首先是偶数个元素，然后有无穷多个元素。因此，对于最一般的查询，您永远不会看到包含奇数个元素的解决方案。