理解差异列表（Prolog）

Question

我在理解差异列表方面遇到了困难，特别是在这个谓词中：

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

有人能帮我理解正在发生的事情吗？

- user2796815

---

第一个子句似乎是错误的，它表示“身份”。 - CapelliC

@CapelliC：不是身份，而是空列表。 - false

@false 我不明白... A 不是可以和任何东西统一吗，而不仅仅是空列表吗？这不是一个普遍的身份关系吗？ - Shon

@false 我认为可能存在一些误解？我相信CapelliC的评论是在指出在这里写的方式第一个子句定义了身份。你是不是在说，在理想情况下，如果回文在正确实现的不同上下文中，这个子句应该为空列表？ - Shon

@aBathologist：OP的程序是DCG的扩展。请看我的第一条评论。因此，必须将其用作palindrom(A,[])。 - false

Answer 1

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

将这个谓词的参数视为差分列表，第一个子句表示从 A 到 A 的列表（即空列表）是一个回文。第二个子句表示一个元素的列表是一个回文，无论这个元素是什么。

不要惊慌！差分列表只是带有显式结尾指针的列表。

一个普通的列表，比如 [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]。旧的差分列表仍然表示一个开放式列表的前缀 [1,2,3]，即 A - Z = [1,2,3,4|W] - [4|W]。一旦关闭，例如使用 W = [5]，所有对数变量的配对仍然表示它们相应的差分列表（即 A - Z，A - W ...），但是 A 不再是开放式的，因此不能再扩展了。

习惯上，不使用 - 函数，而是将差分列表定义的两个部分作为谓词的两个单独参数。当我们始终将它们视为一对并将其视为一对时，它们在概念上形成一对。这是同样的事情。

继续。第三个条款表示，要使 [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]

实际上，当 ...... 核心是回文时，在其周围放置两个 V 可以得到另一个回文。

- Will Ness

---

在 ?- phrase(n,[a],[b]). 中，你的 "endpointer" 指向哪里，其中 n, [b] --> [a]？ - false

@false这不是我们应该这样称呼它。[a]-[b]不是差异列表。 OP的'palindrome'是常规的Prolog谓词，而不是DCG规则，对吗？ - Will Ness

如果您不接受这个例子，请相应地扩展它，以便可以使用phrase/2进行调用。您的解释基于一个非常特定的属性，而并非每个DCG或差异列表都具有该属性；因此不能解释它们的本质。并且：我不同意您的说法，即[a]-[b]不是差异列表。毕竟，在DCG中会出现这样的差异，并且DCG使用差异列表。 - false

@false 我没有准备好用任何严谨的方式来捍卫我的类比。它对我很有帮助。如果DCG规则接受[a]-[b]，那么我可以看到它们不仅仅是diff-lists。palindrome([a],[b])会失败，我认为这没有问题。当然，我可能是错的，如果有人能向我展示在哪里以及为什么，我将不胜感激。 - Will Ness

在AoP中，这让我非常困惑。因为我之前使用过编码，但是我不确定这是否是特定于Wisdom-Prolog的（至少在第一版中有宣传）。 - false

@false 你说得对，AoP是我理解的基础。把[b]-[a]视为差异列表对我来说是新的。 :) [b,a]-[a] 我可以理解，但不是这个。 - Will Ness

Answer 2

以下是先前讨论的精华，并增加了一项小但重要的简化。首先，应该在问题背景下理解原始问题，这可以被表述为定义一个Prolog谓词，检查列表是否为回文，或更一般地生成回文。我们希望探索使用差异列表的实现，因此可以开始如下：

% List is a palindrome if List - [] is a palindrome:
palindrome( List ) :- palindrome(List, []).  

（正如在其他地方解释的那样，如果一个列表List是由两个列表Front和Back连接而成，则Front可以被视为List和Back的差异，也就是说，Front可以被看作等同于(List-Back)。）

（要定义palindrome/2，我们从两个“基本情况”开始，一个空列表和一个单例：）

% The empty list (L-L) is a palindrome:
palindrome(L, L).

% A singleton list, ([X|L] - L), is a palindrome:
palindrome([X|L], L). 

让我们现在转向一般情况。

如果一个拥有超过一个元素的列表要成为回文，那么它看起来像这样：E ... E

其中 ... 是一个（可能为空的）回文。

加上一个尾巴Tail，我们的列表必须长成这样：E ... E Tail

将这个正常列表写成[E|Rest]后，我们可以看到如果(Rest - [E|Tail])是回文的话，原始列表([E|Rest] - Tail)就是回文的。

或者用我们的谓词palindrome/2的术语来说。

palindrome( [E|Xs], Tail ) :- palindrome(Xs, [E|Tail]).

很容易看出这与原始表述等效。

就是这样！现在我们可以生成回文模板，例如：

?- palindrome( X ).
X = [] ;
X = [_G1247] ;
X = [_G1247, _G1247] ;
X = [_G1247, _G1253, _G1247] ;
X = [_G1247, _G1253, _G1253, _G1247] 
....

- peak