6

我无法理解差异列表，特别是在这个谓词中：

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

任何人都可以帮助我了解正在发生的事情吗？

4

2 回答 2

7 
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 - ZwhereA = [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不再是开放式的，因此不能再扩展。

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

继续。第三个子句说，for [C|A]-Dto be a palindrome, A-Bmust be a palindrome, and Bmust be [C|D]. A, D, B是列表，C是列表的一个元素。这可能会令人困惑；让我们V改用。此外，使用ZandY代替DandB来提醒我们列表的“结尾”：

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

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

事实上，当......核心是回文时，V在它周围加上两个 s 会给我们另一个回文。

于 2013-12-07T12:41:08.523 回答
1

以下是一个摘要，希望能提炼出前面讨论的精华，并添加一个小而重要的简化。

首先，应该在手头问题的上下文中理解原始问题，可以将其表述为定义一个 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 ) 是回文，或者根据我们的谓词回文/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] 
....
于 2014-03-01T01:30:40.850 回答