Four Holes in a Queue

01 — the file

What is given, and what is left to write

Four function bodies are missing, ordered so that each may use the one before it. Taken out of order, two unknowns are being debugged at once.

02 — the representation

Two lists pretending to be one

A cons-list is the lecture's: None is the empty list, and (head, tail) is a node whose tail is another cons-list. Nothing else. A queue is a pair of them.

Cons-lists are only cheap at one end — a head may be added or removed in constant time, and reaching the last element costs a full walk. A FIFO queue needs both ends. The trick is to keep two lists pointing in opposite directions, so that both ends of the queue are somebody's head.

front holds the oldest elements in the order they will leave. back holds the newest elements reversed — the most recently enqueued one is its head. So the sequence the queue actually represents is:

contents(front, back)  =  front  ++  reverse(back)

invariant:   front is None  ⟹  back is None

03 — todo 1

_rev(lst) — reverse a cons-list

The only piece of real list work in the file. Everything else is a rearrangement of pointers.

def _rev(lst):
    """TODO 1: reverse a cons-list, returning a new cons-list.

    _rev((1, (2, (3, None))))  ==  (3, (2, (1, None)))

    An imperative while-loop over local variables is fine — the lists
    themselves must not be touched (they can't be: tuples are immutable).
    """

Take the docstring's permission seriously. Recursion is not required here, and on a large maze it would yield a RecursionError rather than a path. The shape required is the standard accumulator walk: carry a second cons-list that starts empty, and keep moving the head of the input onto the head of the accumulator until the input is exhausted. Each step is one (head, tail) allocation.

The accumulator is the return value once the input runs out. Note what doesn't happen in that table: no node of the input is ever altered. The old list is still intact at step 3 — a new spine was built alongside it.

Check yourself before moving on

_rev(None) must give None, not crash and not (None, None). Reversing twice must give back an equal list. If in doubt, try those two cases in a REPL before touching _make.

04 — todo 2

_make(front, back) — the smart constructor

This is the heart of the data structure. It is also four lines. Every other function builds queues by calling it, and never by writing a tuple literal — that is the whole reason the invariant holds everywhere.

def _make(front, back):
    """TODO 2: smart constructor.

    Return a queue (front, back) — but restore the invariant first:
    if `front` is empty, the reversed `back` must BECOME the front.
    Every other function builds queues only through _make, so the
    invariant will hold everywhere. This is where the O(n) work hides.
    """

Two cases, and the branch is on front alone:

• Front is non-empty. Nothing to fix. Return the pair as it stands — and return the very front object that was passed in, not a copy of it. A test checks this with assertIs.
• Front is empty. The invariant demands the back be empty too, so move it: the reversal of back becomes the new front, and the new back is empty. If back was also empty this quietly produces EMPTY, which is exactly right — no special case needed.

05 — todo 3

enqueue(q, x) — add at the back

One cons and one call. A version longer than two lines is probably doing work that belongs to _make.

def enqueue(q, x):
    """TODO 3: return a new queue with x added at the back. O(1).

    Do not rebuild anything: cons x onto back, keep front AS IS (shared!).
    """

Unpack the queue, put x at the head of the back list, and hand both halves to _make. Do not build the pair yourself: enqueueing onto EMPTY would leave an empty front with a one-element back, which is precisely the state the invariant forbids. _make is what catches that.

q1 = from_iter([1, 2, 3])
q2 = enqueue(q1, 4)

# q2's front IS q1's front —
# the same object, not a copy
front2 is front1   → True

def enqueue(q, x):
    # walks the front, or reverses,
    # or rebuilds the pair by hand
    ...

front2 is front1   → False

And the O(1) claim survives the _make call, which is worth a second of thought. _make only reverses when the front is empty — and when the front is empty, the invariant says the back was empty too, so the list being reversed holds exactly the one element just consed. Constant work, always.

06 — todo 4

dequeue(q) — take from the front

The one operation that returns two things, because a persistent structure cannot surrender the value by mutating itself.

def dequeue(q):
    """TODO 4: return (value, new_queue); raise IndexError if empty.

    Take the head of front; rebuild the rest through _make.
    """

Three moves. Refuse the empty queue with an IndexError — peek above shows the exact idiom, message and all. Otherwise the head of the front is the value, and the queue returned is built from the front's tail and the untouched back, passed through _make. That call is where the front can run dry and trigger the flip.

The return order matters and is not symmetric: callers all over the lab write x, q = dequeue(q), value first. Get it backwards and every test in B_FifoContract fails in a confusing way.

Why the old queue still works afterwards

Nothing in those three moves writes anywhere. The node holding the old head is still there, still pointing at the same tail; we have merely stopped referring to it. That is why test_fan_out can dequeue the same version twice and get the same answer both times, then push the two results in different directions. One present, several futures.

07 — the tests

What each test class asks

The classes are named A_, B_, C_ so that unittest runs them in that order. Read a failure as a question about the design, not as a broken assertion.

08 — the cost

Amortised O(1), and the assumption inside it

Every operation is constant time except one, which is linear. The claim is that the linear one is rare enough to pay for itself.

The banker's argument. Charge every enqueue two coins: one for the cons it actually performs, one deposited on the element itself. An element sits in the back holding its coin. When the front finally runs dry and _make reverses, each element in the back spends its own coin to pay for its own move. No element is ever reversed twice, so n operations cost O(n) in total — constant amortised.

The argument is airtight, and it quietly assumes something the rest of this lab exists to break: that each version of the queue is used once. Coins are spent when an element moves; if a version whose reversal is still pending is retained and dequeued repeatedly, every one of those calls performs the same O(n) reversal and there is only one deposit to pay for all of them.

09 — run it

The working loop

When progress stalls

• Everything fails with NotImplementedError. Expected — that is the starting state. Work top to bottom; A_Basics cannot go green until all four are in, because from_iter calls enqueue.
• test_structural_sharing alone fails. Something rebuilt the front. Look for a _rev call on a path where the front was not empty.
• The invariant test fails. Some queue was constructed as a bare tuple instead of through _make. Search the file for return (.
• RecursionError on the large maze. A recursive _rev. The docstring's suggestion of a loop was not decorative.
• Values are right but shifted by one. dequeue rebuilt from front instead of from front[1].

Next: architecture.html — where this queue sits in the maze solver, and what changes when it is exchanged for a stack.