了解差异列表(序言) [英] Understanding difference lists (Prolog)
问题描述
我在理解差异列表时遇到了麻烦，尤其是在该谓词中:
palindrome(A, A).
palindrome([_|A], A).
palindrome([C|A], D) :-
palindrome(A, B),
B=[C|D].
有人可以帮助我跟踪发生的事情吗?
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].旧的将变为A - Z = [1,2,3,4|W] - [4|W]，即仍表示开放式列表[1,2,3,4 ...]的前缀[1,2,3].一旦关闭，例如使用W = [5]，所有成对的logvar仍然代表它们对应的差异列表(即A - Z，A - W ...)，但是A不再是开放式的，因此不能再进行扩展. /p>
习惯使用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可以得到另一个回文馆.
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].
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"
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.
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).
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.
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.
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]
Indeed, when the ...... core is a palindrome, putting two Vs around it gives us another palindrome.
这篇关于了解差异列表(序言)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
