了解差异列表(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].

看到这个谓词的参数作为差异列表,第一个子句说,来自Ato A(即空列表)的列表是回文.

第二个条款说,一个元素列表是一个回文,无论一个元素是什么.

别恐慌!  差异列表只是具有显式结束"指针"的列表

比方说[1,2,3],正常的清单是它的开始和结束之间的差异; 普通列表的结尾总是一个空列表[].也就是说,对于列表,[1,2,3]我们应该将此谓词称为palindrome( [1,2,3], [])- 即检查差异列表[1,2,3] - []是否为回文.

从操作的角度来看,差异列表只是一个(可能是开放式的)列表,具有明确维护的"结束指针",例如:A - Zwhere 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],logvars的所有对仍然代表及其相应的差异表(即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]

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