Functional Queues / Finger Trees

Why Functional Queues / Finger Trees Matters

In purely functional programming and persistent data structure design, imperative in-place mutations of head and tail array indices are prohibited. Standard persistent singly linked lists support $O(1)$ head insertion and removal (push_front and pop_front), but appending an element to the back requires traversing or copying the entire list in $O(N)$ time. When implementing persistent breadth-first search (BFS), task schedulers, undo/redo logs, or immutable sequence abstractions (such as Haskell's Data.Sequence or Scala's immutable collections), maintaining pure persistent queues with $O(1)$ operational bounds is an essential requirement.

Functional Queues (such as Okasaki's Banker's Queue) solve this problem by splitting the queue into two singly linked lists: a front list for dequeuing and a rear list for enqueuing. New elements are prepended to rear in $O(1)$ time, while removals extract elements from front in $O(1)$ time. When front becomes empty, the algorithm reverses rear and assigns it to front in $O(N)$ time. Because every enqueued element is reversed at most once during its lifetime, the amortized cost per operation is strictly $O(1)$. Finger Trees generalize this two-list architecture into a deeply nested tree structure with 2-3 node "fingers" at the prefix and suffix, extending $O(1)$ amortized access to both ends while enabling $O(\log N)$ concatenation and splitting.

Core Concepts and Terminology

Understanding functional queues and finger trees requires formalizing persistent, immutability-preserving queue invariants.

1. Front List ($F$): A singly linked list containing elements in dequeue order. The head of $F$ is the front of the queue.
2. Rear List ($R$): A singly linked list containing recently enqueued elements in reverse arrival order. New elements are prepended to $R$.
3. Rebalance / Pivot Step: When $F$ becomes empty during a dequeue operation, $R$ is reversed ($F' = \text{reverse}(R)$) and $R$ is reset to empty ($R' = \text{nil}$).
4. Structural Sharing: The property wherein new persistent queue versions reuse nodes from existing versions without duplicating unchanged memory.
5. Finger Tree Digits (Prefix/Suffix): In 2-3 Finger Trees, the left (prefix) and right (suffix) digits hold 1 to 4 elements acting as "fingers" into the ends of the sequence, while the deep spine recursively holds nested 2-3 tree nodes.

How Functional Queues / Finger Trees Works, Step by Step

A Functional Queue executes two primary operations: Enqueue and Dequeue.

1. Enqueue Operation ($O(1)$ Worst-Case)

1. Create a new queue handle (Front, Cons(new_elem, Rear)).
2. Return the new queue version handle. Memory complexity is $O(1)$ due to pointer sharing.

2. Dequeue Operation ($O(1)$ Amortized)

1. Empty Check: If both Front and Rear are empty, throw an underflow exception.
2. Rebalance Check: If Front is empty: Reverse Rear to construct Front' = reverse(Rear). Set Rear' = nil.

1. Extract Head: The dequeued value is Front.head.
2. Construct Next Version: The remaining queue version is (Front.tail, Rear).

The control flow diagram below outlines the operation logic for functional queue pop and enqueue handling:

flowchart TD
A[Start: Functional Queue Operation] --> B{Operation Type?}
B -- Enqueue x --> C[New Rear = Cons x, Rear]
C --> D[Return new Queue Version Front, New Rear]
B -- Dequeue --> E{Is Front empty?}
E -- No --> F[Extracted Value = Front.head]
F --> G[Return Extracted Value and Queue Version Front.tail, Rear]
E -- Yes --> H{Is Rear empty?}
H -- Yes --> I[Throw Queue Underflow Exception]
H -- No --> J[New Front = reverse Rear]
J --> K[New Rear = nil]
K --> F

Worked Example with a Full Trace

Let us trace a sequence of operations starting from an empty functional queue $Q_0 = ([], [])$:

1. $Q_1 = Q_0.\text{enqueue}(10) \implies \text{Front} = [], \text{Rear} = [10]$
2. $Q_2 = Q_1.\text{enqueue}(20) \implies \text{Front} = [], \text{Rear} = [20, 10]$
3. $Q_3 = Q_2.\text{enqueue}(30) \implies \text{Front} = [], \text{Rear} = [30, 20, 10]$
4. $(\text{val}_1, Q_4) = Q_3.\text{dequeue}() \implies$ Front is empty! Rebalance $\text{Rear} \implies \text{Front}' = [10, 20, 30], \text{Rear}' = []$. Pop $10 \implies \mathbf{\text{val}_1 = 10}, Q_4 = ([20, 30], [])$.
5. $Q_5 = Q_4.\text{enqueue}(40) \implies \text{Front} = [20, 30], \text{Rear} = [40]$
6. $(\text{val}_2, Q_6) = Q_5.\text{dequeue}() \implies$ Front is non-empty. Pop $20 \implies \mathbf{\text{val}_2 = 20}, Q_6 = ([30], [40])$.

Implementation in Python, C++, and Java

The complete, runnable code implementations below construct an immutable persistent functional queue (FunctionalQueue). All three language implementations follow identical logic, perform identical sample operations, and print identical terminal output.

class Node:
    def __init__(self, val, next_node=None):
        self.val = val
        self.next = next_node


class FunctionalQueue:
    def __init__(self, front=None, rear=None):
        self._front = front
        self._rear = rear

    def is_empty(self):
        return self._front is None and self._rear is None

    def enqueue(self, val):
        new_rear = Node(val, self._rear)
        return FunctionalQueue(self._front, new_rear)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue underflow: empty queue")

        curr_front = self._front
        curr_rear = self._rear

        # Rebalance if front is empty
        if curr_front is None:
            rev_front = None
            curr = curr_rear
            while curr is not None:
                rev_front = Node(curr.val, rev_front)
                curr = curr.next
            curr_front = rev_front
            curr_rear = None

        val = curr_front.val
        next_front = curr_front.next
        return val, FunctionalQueue(next_front, curr_rear)

    def peek(self):
        if self.is_empty():
            raise IndexError("Queue underflow: empty queue")
        if self._front is not None:
            return self._front.val
        # If front is empty, the head is the last element in rear
        curr = self._rear
        last_val = None
        while curr is not None:
            last_val = curr.val
            curr = curr.next
        return last_val


if __name__ == "__main__":
    q0 = FunctionalQueue()
    q1 = q0.enqueue(10)
    q2 = q1.enqueue(20)
    q3 = q2.enqueue(30)

    val1, q4 = q3.dequeue()
    q5 = q4.enqueue(40)
    val2, q6 = q5.dequeue()

    print(f"Dequeued from Q3: {val1}")
    print(f"Dequeued from Q5: {val2}")

    # Demonstrate persistence: q2 still retains its original head
    val_q2, _ = q2.dequeue()
    print(f"Dequeued from historical version Q2: {val_q2}")

#include <iostream>
#include <memory>
#include <stdexcept>

template <typename T>
class FunctionalQueue {
private:
    struct Node {
        T val;
        std::shared_ptr<const Node> next;
        Node(T val, std::shared_ptr<const Node> next = nullptr)
            : val(val), next(next) {}
    };

    std::shared_ptr<const Node> front;
    std::shared_ptr<const Node> rear;

public:
    FunctionalQueue() : front(nullptr), rear(nullptr) {}

    FunctionalQueue(std::shared_ptr<const Node> f, std::shared_ptr<const Node> r)
        : front(f), rear(r) {}

    bool isEmpty() const {
        return front == nullptr && rear == nullptr;
    }

    FunctionalQueue enqueue(T val) const {
        auto new_rear = std::make_shared<const Node>(val, rear);
        return FunctionalQueue(front, new_rear);
    }

    std::pair<T, FunctionalQueue> dequeue() const {
        if (isEmpty()) {
            throw std::underflow_error("Queue underflow: empty queue");
        }

        auto curr_front = front;
        auto curr_rear = rear;

        if (curr_front == nullptr) {
            std::shared_ptr<const Node> rev_front = nullptr;
            auto curr = curr_rear;
            while (curr != nullptr) {
                rev_front = std::make_shared<const Node>(curr->val, rev_front);
                curr = curr->next;
            }
            curr_front = rev_front;
            curr_rear = nullptr;
        }

        T val = curr_front->val;
        auto next_front = curr_front->next;
        return {val, FunctionalQueue(next_front, curr_rear)};
    }
};

int main() {
    FunctionalQueue<int> q0;
    auto q1 = q0.enqueue(10);
    auto q2 = q1.enqueue(20);
    auto q3 = q2.enqueue(30);

    auto res1 = q3.dequeue();
    int val1 = res1.first;
    auto q4 = res1.second;

    auto q5 = q4.enqueue(40);
    auto res2 = q5.dequeue();
    int val2 = res2.first;
    auto q6 = res2.second;

    std::cout << "Dequeued from Q3: " << val1 << "\n";
    std::cout << "Dequeued from Q5: " << val2 << "\n";

    // Demonstrate persistence
    auto res_q2 = q2.dequeue();
    std::cout << "Dequeued from historical version Q2: " << res_q2.first << "\n";

    return 0;
}

public class Main {

    static class Node<T> {
        final T val;
        final Node<T> next;

        Node(T val, Node<T> next) {
            this.val = val;
            this.next = next;
        }
    }

    static class FunctionalQueue<T> {
        private final Node<T> front;
        private final Node<T> rear;

        public FunctionalQueue() {
            this.front = null;
            this.rear = null;
        }

        public FunctionalQueue(Node<T> front, Node<T> rear) {
            this.front = front;
            this.rear = rear;
        }

        public boolean isEmpty() {
            return front == null && rear == null;
        }

        public FunctionalQueue<T> enqueue(T val) {
            Node<T> newRear = new Node<>(val, this.rear);
            return new FunctionalQueue<>(this.front, newRear);
        }

        public static class Result<T> {
            public final T value;
            public final FunctionalQueue<T> queue;

            public Result(T value, FunctionalQueue<T> queue) {
                this.value = value;
                this.queue = queue;
            }
        }

        public Result<T> dequeue() {
            if (isEmpty()) {
                throw new IllegalStateException("Queue underflow: empty queue");
            }

            Node<T> currFront = this.front;
            Node<T> currRear = this.rear;

            if (currFront == null) {
                Node<T> revFront = null;
                Node<T> curr = currRear;
                while (curr != null) {
                    revFront = new Node<>(curr.val, revFront);
                    curr = curr.next;
                }
                currFront = revFront;
                currRear = null;
            }

            T val = currFront.val;
            Node<T> nextFront = currFront.next;
            return new Result<>(val, new FunctionalQueue<>(nextFront, currRear));
        }
    }

    public static void main(String[] args) {
        FunctionalQueue<Integer> q0 = new FunctionalQueue<>();
        FunctionalQueue<Integer> q1 = q0.enqueue(10);
        FunctionalQueue<Integer> q2 = q1.enqueue(20);
        FunctionalQueue<Integer> q3 = q2.enqueue(30);

        FunctionalQueue.Result<Integer> res1 = q3.dequeue();
        int val1 = res1.value;
        FunctionalQueue<Integer> q4 = res1.queue;

        FunctionalQueue<Integer> q5 = q4.enqueue(40);
        FunctionalQueue.Result<Integer> res2 = q5.dequeue();
        int val2 = res2.value;

        System.out.println("Dequeued from Q3: " + val1);
        System.out.println("Dequeued from Q5: " + val2);

        // Demonstrate persistence
        FunctionalQueue.Result<Integer> resQ2 = q2.dequeue();
        System.out.println("Dequeued from historical version Q2: " + resQ2.value);
    }
}

Complexity, Correctness, and Invariants

The formal justification for functional queue amortized complexity uses the Banker's Method (accounting method) or Physicist's Method (potential method).

Define the potential function $\Phi(Q)$ of a functional queue $Q = (F, R)$ as the length of the rear list:

$$\Phi(Q) = \vert{}R\vert{}$$

• Enqueue Operation: Actual cost $c_i = O(1)$. $\Delta\Phi = \Phi(Q_i) - \Phi(Q_{i-1}) = +1$.

Amortized cost $\hat{c}_i = c_i + \Delta\Phi = 1 + 1 = 2 = O(1)$. Dequeue Operation (Without Rebalance): Actual cost $c_i = O(1)$. $\Delta\Phi = 0$. Amortized cost $\hat{c}_i = O(1)$. Dequeue Operation (With Rebalance): Actual cost $c_i = 1 + \vert{}R\vert{}$ (to reverse $R$). Potential change $\Delta\Phi = 0 - \vert{}R\vert{} = -\vert{}R\vert{}$. Amortized cost $\hat{c}_i = (1 + \vert{}R\vert{}) + (-\vert{}R\vert{}) = 1 = O(1)$.

Variants, Pitfalls, and Optimizations

Functional Variants

1. Lazy / Real-Time Queues (Okasaki):

In persistent applications where an old queue version with an empty Front list is dequeued repeatedly across multiple threads, simple un-memoized rebalancing executes $O(N)$ list reversals repeatedly, destroying amortized bounds. Real-Time Queues solve this by maintaining Front as a lazy stream and incrementally reversing $R$ over subsequent operations, guaranteeing $O(1)$ worst-case persistence. 2. 2-3 Finger Trees (Hinze & Paterson): By replacing linear lists with digits and a nested 2-3 tree spine, Finger Trees provide $O(1)$ amortized push_front, pop_front, push_back, and pop_back, while supporting sequence splitting and concatenation in $O(\log N)$ time.

Practice Problems and Real-World Use

Functional Queues and Finger Trees are implemented extensively across pure functional language runtimes, persistent data structures, and compiler infrastructure: