Prolog - Palindrome Functor

Question

我试图palindrome/1在Prolog中编写一个谓词,当且仅当它的列表输入包含一个回文列表时才是真的.

例如:

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

是真的.

任何想法或解决方案？

Answer 1

回文列表是向后读取相同内容的列表,因此您可以反转列表以检查它是否产生相同的列表:

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

Answer 2

看起来每个人都投票支持基于反向/ 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 functor不会"返回"任何东西.