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

Question

差异列表是否是一种“绕过”prolog 中变量不可变这一事实的方法？

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

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 表示“剥离”每个术语，然后用 替换末尾(中心)的 [] .(d, [])。因此，要实现 append/3:

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

这是 how it is traditionally implemented .

这是another answer其中涵盖了相当广泛的主题。

该答案没有涉及的是，出于效率原因，“返回”列表的库谓词可能会提供谓词的差异列表版本，以防您可能想要附加到列表的末尾。例子是 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 所说的“幻觉”变量，即从队列中弹出的元素多于推送到队列中的元素。有趣的是，忽略上面谓词中的第一个参数，看看会发生什么:

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

而不是失败。