prolog - Prolog - 回文函子

Question

我正在尝试palindrome/1在 Prolog 中编写一个谓词，当且仅当其列表输入由回文列表组成时才为真。

例如：

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

是真的。

有什么想法或解决方案吗？

Answer 1

回文列表是一个向后读取相同的列表，因此您可以反转该列表以检查它是否产生相同的列表：

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

Answer 2

看起来每个人都在投票支持基于 reverse/2 的解决方案。我猜你们心中有一个反向/2 解决方案，即给定列表的 O(n)。带有蓄能器的东西：

 reverse(X,Y) :- reverse(X,[],Y).

 reverse([],X,X).
 reverse([X|Y],Z,T) :- reverse(Y,[X|Z],T).

但是还有其他方法可以检查回文。我想出了一个使用 DCG 的解决方案。可以使用以下规则：

 palin --> [].
 palin --> [_].
 palin --> [Border], palin, [Border].

哪种解决方案更好？好吧，让我们通过 Prolog 系统的 profile 命令做一些小统计。结果如下：

所以也许DCG解决方案在肯定情况下（“雷达”）通常更快，它不必构建整个反向列表，而是直接移动到中间，然后在离开自己的递归期间检查其余部分。但DCG解决方案的缺点是它是不确定的。一些时间测量会告诉更多...

再见

PS：使用 Jekejeke Prolog 的新可插入调试器完成的端口统计：http:
//www.jekejeke.ch/idatab/doclet/prod/en/docs/10_dev/10_docu/02_reference/04_examples/02_count.html

但是其他 Prolog 系统也有类似的功能。有关更多信息，请参阅“代码探查器”专栏：
http ://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations

Answer 3

这听起来确实像是一个家庭作业问题，但我就是忍不住：

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

从技术上讲，prolog 函子不会“返回”任何东西。

Answer 4

另一种方法，用 DCG 来做：

palindrome --> [_].
palindrome --> [C,C].
palindrome --> [C],palindrome,[C].

您可以像这样检查回文：

?- phrase(palindrome,[a,b,a,b,a]).
true.

?- phrase(palindrome,[a,b,a,b,b]).
false.

Answer 5

您可以使用 ：

palindrome([]).
palindrome([_]).
palindrome([X|Xs]):-append(Xs1,[X],Xs), palindrome(Xs1).