prolog - 将 Prolog 仿函数转换为具有差异列表的仿函数

Question

我正在为 Prolog (SWI) 做作业，但不知道如何完成:

我有仿函数:

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

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

对于我的作业，我必须写一个仿函数 palindrome/2没有 append/3并带有差异列表。

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

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

Answer 1

对于给定的长度为 n 的列表，您的解决方案需要一些 O(n2) 推理:n(实际上是 n/2)对于 palindrome/1 和 i 每个 append/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].

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