Prolog和可变变量中的差异列表

Question

差异列表是否可以“解决”变量在序言中不可变的事实？

即如果我实现使用差异列表追加：

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

然后运行：

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

在某种程度上，X已用作可变变量。就我们的意图和目的而言，它已经改变了吗？

换句话说，我们能够修改X（可变），而不必构造新列表（例如Z（不可变）），这使得差异列表具有吸引力。那么为什么不仅仅拥有可变变量呢？

更新：

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

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

Answer 1

差异列表是用来绕过另一个限制的：您需要遍历整个列表以“追加”到其末尾（想像一个单链表，其中您有指向第一个元素的指针，但没有指向前哨的指针）。

在代码中：由于列表[a, b, c]是（传统上）嵌套的术语.(a, .(b, .(c, [])))，因此在列表d的末尾添加a 意味着“剥离”每个术语，然后用代替[]末尾（中心）.(d, [])。因此，要实现append/3：

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

传统上是这样实现的。

这是涵盖该主题的另一个答案。

这个答案没有涉及到的问题是，出于效率方面的考虑，万一您可能希望追加到列表的末尾，“返回”列表的库谓词可能会提供谓词的差异列表版本。示例为read_pending_codes/3和read_pending_chars/3，或者为的四参数版本findall/4。

DCG是使用差异列表的便捷方法，而无需显式传递列表和尾部的两个参数。

实施队列

队列的三个最基本的操作：清空队列，向后推，从前弹出：

%% 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仅允许您向后推：一旦推入元素，就无法（固定时间）访问队列中的该元素。

该queue/3术语的第一个论点是防止Richard O'Keefe所谓的“ hallucinating”变量，也就是说，从队列中弹出的元素要多于推入该变量的元素。将上面的谓词中的第一个参数忽略掉，看看会发生什么是很有趣的：

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

而不是失败。