Problem with appending element using difference lists in Prolog

Question

I found this Prolog code in this answer, which implements a queue using difference lists:

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

doing something like this it works as expected:

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

and I get

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

also interestingly if I observe the value of Q with this snippet:

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

I get:

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

which I suppose it should be like this, since the difference results to empty list, so they are somewhat equivalent.

The problem is, after the command

queue_last(Q, 999, Q_)

I cannot reuse Q to create a Q__, ex:

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

because the binding of queue_last(queue(X, Q, [L|Q0]), L, queue(s(X), Q, Q0)). fails.

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

How can I solve this problem ? Is there some workaround ? (always using diff lists)

Answer 1

I cannot reuse Q to create a Q__

That's because you must use the "threaded out" new structure that you call Q_. The old Q is a burner and must be discarded. It doesn't correctly describe a "difference list" anymore.

?- 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

After the empty_queue(Q1) call, this is Q1:

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

After the queue_last(Q1, 999, Q2) call, this is Q1 and Q2:

Q1 (invalid)

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

Q2 (valid)

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

After the queue_last(Q2, 888, Q3) call, this is Q1, Q2 and Q3:

Q1 (invalid)

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

Q2 (invalid)

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

Q3 (valid)

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