Prolog 和可变变量中的差异列表 [英] Difference lists in Prolog and mutable variables

问题描述

差异列表是一种绕过"变量在序言中不可变这一事实的手段吗?

Are difference lists a means to 'get-around' the fact that variables are immutable in prolog?

即如果我使用差异列表实现附加:

I.e. if I implement append using difference lists:

diff_append(OpenList, Hole, L2) :-
    Hole = L2.

然后运行:

X=[a,b,c|Hole], diff_append(X, Hole, [d,e,f]).

在某种程度上，X 已被用作可变变量.为了我们的意图和目的，它已经改变了吗?

The X, in a way, has been used as a mutable variable. For our intents and purposes it has been changed?

换句话说，事实上我们已经能够修改 X(可变)而不是必须构造一个新列表，比如说 Z(不可变)，这使得差异列表具有吸引力.那么为什么不只有可变变量呢?

In other words, the fact that we have been able to modify X (mutable) rather than having to construct a new list, say Z (immutable) is what makes difference lists attractive. So why not just have mutable variables?

更新:

diff_append2(OpenList-Hole,L2):-
    Hole=L2.

X=[a,b,c|Ho]-Ho,diff_append2(X,[d,e,f]).

推荐答案

差异列表更适合用来解决另一个限制:您需要遍历整个列表以追加"到它的末尾(想想单链表你有一个指向第一个元素的指针，但没有指向哨兵)

Difference lists are rather used to get around another limitation: that you need to traverse the whole list to "append" to its end (think of a singly linked list where you have a pointer to the first element, but not to the sentinel).

在代码中:因为列表 [a, b, c] 是(传统上)嵌套项 .(a, .(b, .(c, [])))，在它的末尾添加一个 d 意味着在用 替换末尾(中心)的 [] 之前剥离"每个术语.(d, []).因此，要实现 append/3:

In code: since a list [a, b, c] is (traditionally) the nested term .(a, .(b, .(c, []))), adding a d to the end of it means "peeling off" each term before replacing the [] at the end (the center) with .(d, []). So, to implement append/3:

append([], L, L).
append([H|T], L, [H|R]) :-
    append(T, L, R).

这是 传统上是如何实现的.

这是另一个答案，其中涵盖了相当广泛的主题.

This is another answer which covers the topic quite extensively.

这个答案没有涉及到的是，返回"列表的库谓词可能会提供谓词的差异列表版本，出于效率原因，以防您可能想要附加到列表的末尾.例如 read_pending_codes/3 和 read_pending_chars/3，或 findall/4.

Something that that answer doesn't go into is that library predicates that "return" lists might offer a difference-list version of the predicate, for efficiency reasons, in case you might want to append to the end of the list. Examples would be read_pending_codes/3 and read_pending_chars/3, or the four-argument version of findall/4.

DCG 是一种处理差异列表的便捷方式，无需显式传递列表和尾部的两个参数.

DCGs are a convenient way of working with difference lists without explicitly passing around the two arguments for the list and the tail.

队列的三个最基本的操作:创建一个空队列，推到后面，从前面弹出:

The three most basic operations for a queue: making an empty queue, pushing to the back, and popping from the front:

%% empty_queue(-Queue)
% make an empty queue
empty_queue(queue(0, Q, Q)).

%% queue_head(?Queue, ?Head, ?Queue0)
% Queue, with Head removed, is Queue0
queue_head(queue(s(X), [H|Q], Q0), H, queue(X, Q, Q0)).

%% queue_last(+Queue0, +Last, -Queue)
% Queue0, with Last at its back, is Queue
queue_last(queue(X, Q, [L|Q0]), L, queue(s(X), Q, Q0)).

正如人们应该注意到的，queue_head/3 会让你从队列的前端弹出或推送到队列的前端.queue_last/3 只能让你推到后面:一旦你推了一个元素，你就没有(恒定时间)访问队列中它之前的元素.

As one should notice, queue_head/3 will let you pop from the front or push to the front of the queue. queue_last/3 only lets you push to the back: once you have pushed an element, you don't have (constant time) access to the element before it in the queue.

queue/3 术语的第一个参数是为了防止 Richard O'Keefe 所说的幻觉"变量，即从队列中弹出的元素比推送到它的元素多.有趣的是从上面的谓词中省略第一个参数，看看会发生什么:

The first argument to the queue/3 term is there to prevent what Richard O'Keefe calls "hallucinating" variables, that is, popping from a queue more elements than have been pushed to it. It is interesting to leave out that first argument from the predicates above and see what happens:

?- empty_queue(Q0), queue_head(Q0, H, Q1).
Q0 = queue([H|_G341], [H|_G341]),
Q1 = queue(_G341, [H|_G341]).

而不是失败.

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