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])。谢谢。

- user3186023

---

这里有一个与您所提问非常相似的SO问题链接：https://dev59.com/4FjUa4cB1Zd3GeqPSIR6 - repeat

Answer 1

回文列表是指从前往后和从后往前读取都相同的列表。因此，您提供的示例 [a,b,c,d] 及其反转，如果第一个列表直接跟随第二个列表，则构成回文列表：[a,b,c,d,d,c,b,a]。由于您正在尝试描述特定类型的列表，因此很容易使用 Prolog DCGs 来完成此任务。通过使用它们，您可以定义回文列表如下：

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规则，而且因为它按照公平的顺序产生了结果：空列表、一个元素、两个元素...。使用第二个版本，你会先得到所有有偶数个元素的列表，而这样的列表有无限多个。所以你永远不会看到一个具有奇数个元素的解，使用最通用的查询。

- tas

---

哦，天啊，我完全忘记了在这种类型的问题中使用DCG！非常感谢。 - user3186023

@user3186023：如果这个回答解决了你的问题，请别忘了点击勾选标志；-) - tas