3

我在这个答案中找到了这个 Prolog 代码，它使用差异列表实现了一个队列：

%% 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)).

做这样的事情它按预期工作：

..., empty_queue(Q), queue_last(Q, 999, Q_), writeln(Q_), ....

我得到

queue(s(0),[999|_3076],_3076)

如果我观察Q这个片段的价值，也很有趣：

empty_queue(Q), writeln(Q), queue_last(Q, 999, Q_), writeln(Q)

我得到：

queue(0,_3750,_3750)
queue(0,[999|_3758],[999|_3758])

我想应该是这样的，因为差异导致空列表，所以它们有点等价。

问题是，在命令之后

queue_last(Q, 999, Q_)

我不能重用Q创建一个Q__，例如：

empty_queue(Q), queue_last(Q, 999, Q_), queue_last(Q, 888, Q__)

因为绑定queue_last(queue(X, Q, [L|Q0]), L, queue(s(X), Q, Q0)).失败。

L = 888, L = 999 (tries to be both)

我怎么解决这个问题 ？有一些解决方法吗？（总是使用差异列表）

4

2 回答 2

1

Prolog 变量不能被重新分配。你不能重复使用它们。我不知道调用变量“烧毁”是否有很大帮助，它们没有被烧毁，它们被绑定到一个具体的值。

不要使用“write”和朋友，除非你正在做一些复杂的打印式调试。在顶层尝试一下，无论如何您都会打印出所有内容。这是您如何使用此队列实现的方法。请注意，我正在使用Q0, Q1,Q2等，因为一旦有多个下划线，我就无法计算下划线。

Enqueueing a，然后b在队列的末尾：

?- empty_queue(Q0), queue_last(Q0, a, Q1), queue_last(Q1, b, Q2).
Q0 = queue(0, [a, b|_15096], [a, b|_15096]),
Q1 = queue(s(0), [a, b|_15096], [b|_15096]),
Q2 = queue(s(s(0)), [a, b|_15096], _15096).

Enqueueing a，然后b，然后弹出您入队的第一个值（FIFO顺序）：

?- empty_queue(Q0), queue_last(Q0, a, Q1), queue_last(Q1, b, Q2), 
    queue_head(Q2, Popped, Q3).
Q0 = queue(0, [a, b|_17772], [a, b|_17772]),
Q1 = queue(s(0), [a, b|_17772], [b|_17772]),
Q2 = queue(s(s(0)), [a, b|_17772], _17772),
Popped = a,
Q3 = queue(s(0), [b|_17772], _17772).

在前面推两次，然后弹出（后进先出顺序）：

?- empty_queue(Q0), queue_head(Q1, x, Q0), queue_head(Q2, y, Q1), 
    queue_head(Q2, Popped, Q3).
Q0 = queue(0, _21688, _21688),
Q1 = Q3, Q3 = queue(s(0), [x|_21688], _21688),
Q2 = queue(s(s(0)), [y, x|_21688], _21688),
Popped = y.

我在您的问题下方的评论中链接的答案（这里又是：https ://stackoverflow.com/a/31925828/14411997 ）详细解释了它是如何工作的。它还具有指向其他相关 Q/A 等的链接。

于 2021-06-07T07:56:13.587 回答
1

我不能重用Q创建一个Q__

那是因为您必须使用您调用的“线程化”新结构Q_。旧Q的是燃烧器，必须丢弃。它不再正确描述“差异列表”。

?- empty_queue(Q1), 
   queue_last(Q1, 999, Q2), 
   queue_last(Q2, 888, Q3).

Q1 = queue(0,[999,888|_14714],[999,888|_14714]),   % Useless
Q2 = queue(s(0),[999,888|_14714],[888|_14714]),    % Burnt
Q3 = queue(s(s(0)),[999,888|_14714],_14714).       % Correct, valid

通话后empty_queue(Q1)，这是Q1：

queue
├── arg 0: 0
├── arg 1: ----+---> <empty cell #1>
|              |
└── arg 2: ----+

通话后queue_last(Q1, 999, Q2)，这是Q1and Q2：

Q1（无效的）

queue
├── arg 0: 0
├── arg 1: ----+---->[|]
|              |     / \
|              |  999  <empty cell #2>
|              |
└── arg 2: ----+

Q2（有效的）

queue
├── arg 0: s(0)
├── arg 1: --------->[|]
|                    / \
|                 999  <empty cell #2>
|                          ^
|                          |
└── arg 2: ----------------+

通话后queue_last(Q2, 888, Q3)，这是Q1,Q2和Q3:

Q1（无效的）

queue
├── arg 0: 0
├── arg 1: ----+---->[|]
|              |     / \
|              |  999   [|]
|              |       /   \
└── arg 2: ----+    888    <empty cell #3>

Q2（无效的）

queue
├── arg 0: s(0)
├── arg 1: --------->[|]
|                    / \
|                 999  [|]<------------------+
|                      /  \                  |
|                   888   <empty cell #3>    |
|                                            |
└── arg 2: ----------------------------------+

Q3（有效的）

queue
├── arg 0: s(s(0))
├── arg 1: --------->[|]
|                    / \
|                 999  [|]
|                      /  \              
|                   888   <empty cell #3>
|                                ^
|                                | 
└── arg 2: ----------------------+
于 2021-06-06T14:19:39.253 回答