了解差异列表 (Prolog) [英] Understanding difference lists (Prolog)

问题描述

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

I'm having trouble understanding difference list, particularly in this predicate:

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

谁能帮我看看发生了什么?

Could anyone help me follow what's happening?

推荐答案

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

将此谓词的参数视为差异列表，第一个子句说，从 A 到 A 的列表(即空列表)是回文.

Seeing the arguments to this predicate as a difference list, the first clause says, a list from A to A (i.e., an empty list) is a palindrome.

第二个子句说，一个单元素列表是一个回文，不管那个元素是什么.

The second clause says, a one-element list is a palindrome, whatever that one element is.

不要惊慌！ 差异列表只是带有明确结束指针"的列表

Don't panic!  Difference lists are just lists with explicit end "pointer"

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

A normal list, say [1,2,3], is a difference between its start and its end; the end of a normal list is always an empty list, []. That is to say, for a list [1,2,3] we are supposed to call this predicate as palindrome( [1,2,3], []) — namely, check whether the difference list [1,2,3] - [] is a palindrome.

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

From the operational point of view, a difference list is nothing but a (possibly open-ended) list with explicitly maintained "end pointer", for example: A - Z where A = [1,2,3|Z] and Z = []. Indeed, [1,2,3|[]] is the same as [1,2,3]. But when Z is not instantiated yet, the list A is still open ended - its "end pointer" Z can be instantiated to anything (but only once, of course, sans the backtracking).

如果我们稍后将 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] 的情况下，所有的 logvar 对仍然代表它们对应的差异列表(即 A - Z、A - W ...)，但是 A 不再是开放式的，所以不能再扩展了.

If we were to instantiate Z later to an open-ended list, say, Z = [4|W], we'd get a new, extended difference list A - W where A = [1,2,3,4|W]. The old one would become A - Z = [1,2,3,4|W] - [4|W], i.e. still representing a prefix [1,2,3] of an open-ended list [1,2,3,4 ...]. Once closed, e.g. with W = [5], all the pairs of logvars still represent their corresponding difference lists (i.e. A - Z, A - W ...), but A is not open-ended anymore, so can't be extended anymore.

不使用 - 函子，习惯上只使用 diff 列表定义的两个部分作为谓词的单独参数.当我们总是把它们当作一对的两个部分来使用/对待时，它们在概念上就形成了一对.都是一样的.

Instead of using the - functor, it is customary to just use both parts of the diff list definition as separate arguments to a predicate. When we always use / treat them as if they were two parts of a pair, then they form a pair, conceptually. It's the same thing.

继续.第三个子句说，[C|A]-D 是回文，AB 必须是回文，B 必须是 <代码>[C|D].A, D, B 是列表，C 是列表的元素.这可能会令人困惑；让我们使用 V 代替.另外，使用 Z 和 Y 代替 D 和 B，以提醒我们 a 的结束"列表:

Continuing. The third clause says, for [C|A]-D to be a palindrome, A-B must be a palindrome, and B must be [C|D]. A, D, B are lists, C is an element of a list. This might be confusing; let's use V instead. Also, use Z and Y instead of D and B, to remind us of "the end" of a list:

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

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

确实，当 ...... 核心是回文时，在其周围放置两个 V 会给我们另一个回文.

Indeed, when the ...... core is a palindrome, putting two Vs around it gives us another palindrome.

这篇关于了解差异列表 (Prolog)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！