prolog - 在 Prolog 中使用差异列表附加元素的问题

Question

我在 this answer 中找到了这个 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)). 的绑定(bind)失败。

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

我该如何解决这个问题？有什么解决方法吗？ (总是使用差异列表)

Answer 1

I cannot reuse Q to create a Q__

那是因为您必须使用称为Q_ 的“threaded out”新结构。旧的 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) 调用之后，这是 Q1 和 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: ----------------------+