问题描述
我无法理解差异列表,尤其是在这个谓词中:
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
必须是 .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 V
s around it gives us another palindrome.
这篇关于了解差异列表 (Prolog)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!