Problem with appending element using difference lists in Prolog

user_14770271 0
Viewed 111

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)

difference-lists prolog
2 Answers

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: ----------------------+
user_8844630

Prolog variables cannot be reassigned. You cannot reuse them. I don't know if calling variables "burned" helps much, they aren't burnt, they are bound to a concrete value.

Don't use "write" and friends, unless you are doing some complicated print-style debugging. Try things out on the top level, you will get everything printed out anyway. Here is how you can use this queue implementation. Note that I am using Q0, Q1, Q2, etc because I have trouble counting the underscores once there is more than one underscore.

Enqueueing a, then b at the end of the queue:

?- 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, then b, then popping the first value you enqueued (FIFO order):

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

Pushing at the front twice, then popping (LIFO order):

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

The answer that I linked in the comment below your question (here it is again: https://stackoverflow.com/a/31925828/14411997) explains in some detail how this works. It also has links to other related Q/As and so on.

user_144119970
Related