将Prolog仿函数转换为带差异列表的仿函数

Question

我正在为Prolog(SWI)做作业,但无法弄清楚如何完成这项工作:

我有仿函数:

palindrome([]).
palindrome([_]).
palindrome([A|T]) :-
      append(Middle,[A],T),
      palindrome(Middle).

它告诉给定的列表是否是回文.

对于我的作业,我必须编写一个palindrome/2没有append/3和有差异列表的仿函数.

我知道差异列表是一种形式[Y|X]-X,但我不明白如何使用它以及如何替换append仿函数.

有人可以向我解释一下吗？

Answer 1

对于长度为n的给定列表,您的解决方案需要一些O(n ²)推论:对于/ 1,n(实际上是n/2),对于每个只需搜索并比较结束的i.palindromeappend/3

重新定义您的定义的最直接的方法是使用语法(DCG),这是使用差异列表的便捷方式.请注意,每个语法规则对应于程序中的一个子句.

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

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

为方便起见,这里写的语法更紧凑:

palindrome --> [] | [_] | [A], palindrome, [A].

现在,这些语法规则是如何实现的？最简单的方法是查看实际定义listing(palindrome).

?- listing(palindrome).
palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
   palindrome(A, B),
   B=[C|D].

所以现在这是使用差异列表的定义.