Prolog -回文函数式

Question

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

例如：

?- 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解的缺点是它具有不确定性。一些时间测量会告诉我们更多。

再见

附注:使用Jekejeke Prolog的新plugable调试器完成的端口统计：

http://www.jekejeke.ch/idatab/doclet/prod/en/docs/10_dev/10_docu/02_reference/04_examples/02_count.html

但其他Prolog系统也有类似的功能。有关详细信息，请参阅"Code Profiler“列：

http://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations

Answer 3

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

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

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