prolog - 理解差异列表(Prolog)

Question

我无法理解差异列表，尤其是在这个谓词中:

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

有人可以帮我跟踪正在发生的事情吗？

Answer 1

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

将此谓词的参数视为差异列表，第一个子句表示，来自 A 的列表。至 A (即，一个空列表)是一个回文。

第二个子句说，一个单元素列表是一个回文，无论那个元素是什么。

不要 panic ! 差异列表只是具有明确结束“指针”的列表

一个普通的列表，比如 [1,2,3] , 是它的开始和结束之间的差异；普通列表的结尾总是一个空列表，[] .也就是说，对于一个列表[1,2,3]我们应该称这个谓词为 palindrome( [1,2,3], []) — 即检查差异列表是否[1,2,3] - []是回文。

从操作的角度来看，差异列表只不过是一个(可能是开放式的)列表，其中明确维护了“结束指针”，例如:A - Z哪里A = [1,2,3|Z]和 Z = [] .确实，[1,2,3|[]]与 [1,2,3] 相同.但是当 Z尚未实例化，列表 A仍然是开放式的 - 它的“结束指针”Z可以实例化为任何东西(但只有一次，当然，没有回溯)。

如果我们要实例化 Z后来到一个开放式列表，比如，Z = [4|W] ，我们会得到一个新的、扩展的差异列表 A - W哪里A = [1,2,3,4|W] .旧的会变成A - Z = [1,2,3,4|W] - [4|W] ，即仍然代表前缀 [1,2,3]开放式列表 [1,2,3,4 ...] .一旦关闭，例如与 W = [5] ，所有对数变量对仍然代表它们对应的差异列表(即 A - Z ， A - W ...)，但是 A不再是开放式的，所以不能再扩展了。

而不是使用 -仿函数，习惯上只使用 diff 列表定义的两个部分作为谓词的单独参数。当我们总是使用/对待它们时，就好像它们是一对的两个部分，那么它们在概念上就形成了一对。这是同一件事。

继续。第三个条款说，对于 [C|A]-D成为回文，A-B必须是回文，并且 B必须是 [C|D] . A, D, B是列表，C是列表的一个元素。这可能令人困惑；让我们用 V反而。另外，使用 Z和 Y而不是 D和 B ，提醒我们列表的“结束”:

palindrome([V|A], Z):- palindrome(A, Y), Y=[V|Z].

V ................. V ----
  ^                 ^ ^
  |                 | |
  |                 | Z
  A                 Y = [V|Z]

确实，当...... core是一个回文，放两个V围绕它给了我们另一个回文。