At the Checkout

A functional-programming simulation of a store's checkout counters, written entirely in Racket. Customers arrive with their baskets, counters get delayed by unforeseen circumstances, queues grow and shrink, and the store opens or closes registers to keep waiting times under control: all modeled as pure, side-effect-free computation.

The Story

Every shopper has stood in a supermarket, basket in hand, scanning the row of registers and trying to guess which line will move fastest. Behind that everyday decision is a small optimization problem: which counter has the shortest wait, which ones only accept express customers, and how does the answer change the moment someone new joins a line or a register grinds to a halt.

This project builds that world from scratch, one layer of abstraction at a time. It starts as a fixed set of four checkout counters and a handful of straightforward list operations. It grows into a store with a dynamic number of fast and slow lanes, governed by curried functions and higher-order abstractions instead of repeated logic. It then gains a proper sense of time, so that customers actually progress through their queues and leave the store as minutes pass rather than everything happening instantaneously. Finally, the humble list underneath each queue is replaced by a purpose-built, amortized O(1) queue abstract data type: first as a simple two-stack structure, then reimplemented with lazy streams for real algorithmic performance, all without touching a single line of the simulation logic built on top of it.

The project is organized as four progressive stages, each building directly on the one before it, mirroring how a real system evolves: get something working, generalize it, make it respect the passage of time, then make it fast.

Features

Etapa 1: Four Fixed Counters

• Models a store with exactly four checkout counters, each tracking its index, total wait time, and customer queue.
• Distinguishes between express counters (limited to customers with few items) and regular counters open to everyone.
• min-tt finds the counter with the shortest total wait time, breaking ties by lowest index.
• add-to-counter enqueues a customer together with their item count and updates the counter's wait time accordingly.
• serve processes a stream of requests: customers joining a queue, or counters being hit with a delay, always routing each customer to the most advantageous eligible counter.

Etapa 2: Dynamic Counters and Higher-Order Functions

• Removes the fixed count of four counters in favor of two independently sized collections: fast counters and slow counters.
• Introduces an exit-time field on each counter, tracking how long until its front customer finishes checking out.
• Leans on curried functions, anonymous functions, and built-in Racket functionals to eliminate duplicated logic from Stage 1.
• update applies an arbitrary transformation to the counter at a given index within a list of counters.
• remove-first-from-counter checks out the front customer, correctly adjusting the counter's wait and exit times.
• serve now also processes checkout completions and requests to open new slow counters whenever the average wait time across all counters exceeds a threshold.

Etapa 3: A Real Queue and the Passage of Time

• Introduces a hand-built abstract data type for a FIFO queue (empty-queue, queue-empty?, enqueue, dequeue, top), implemented internally as two stacks for amortized O(1) operations, and used everywhere the simulation previously relied on plain lists.
• Rebuilds every earlier function to interact with the store's state exclusively through this queue interface, respecting a strict abstraction barrier.
• Models time explicitly: requests can now include a number of minutes elapsing between events, during which customers advance through their queues and, when their time is up, leave the store.
• pass-time-through-counter is a curried function that advances a single counter's clock by a given number of minutes.
• serve returns not only the updated counters but also the ordered list of customers who exited the store during the simulated interval.

Etapa 4: Lazy Streams and Store Management

• Reimplements the queue TDA's internal representation using a lazy stream for one of its two stacks, preserving the exact same public interface so every function built in Stage 3 continues to work unmodified.
• Maintains a size invariant between the two internal stacks and performs lazy rotations by moving elements one at a time as they're consumed rather than all at once to guarantee true amortized constant-time operations.
• Adds the ability to open and close individual counters at runtime, with customers redistributed out of a closing counter (except the one currently being served).
• Updates counter-assignment and store-wide averaging logic to consider only currently open counters.

Design Notes

• Purely functional throughout. No mutation, no side effects: every operation returns a new version of the store's state. This is enforced not just as a style choice but as a hard constraint of the assignment.
• Progressive abstraction. Each stage is a strict superset of the previous one's behavior, built by generalizing data representations (fixed counters to dynamic lists, lists to a queue ADT, eager stacks to lazy streams) without breaking the public behavior relied upon by earlier code.
• Abstraction barriers are respected on purpose. From Stage 3 onward, the simulation logic never inspects the internal representation of a queue directly. This is precisely what makes the Stage 4 performance upgrade a drop-in replacement.

Repository Structure

.
├── etapa1/         fixed counters, basic queueing and delays
├── etapa2/         dynamic counters, higher-order functions
├── etapa3/         queue ADT (list-based) and time simulation
│   └── queue.rkt   Queue abstract data type implementation
├── etapa4/         queue ADT (stream-based), open/close counters
│   └── queue.rkt   Lazy-stream queue abstract data type implementation
└── README.md

Running the Project

Each stage's folder includes a checker.rkt file used for testing against the reference behavior described in the assignment. Open the relevant stage's file in DrRacket or run it from the command line:

racket checkerN.rkt

replacing N with the stage number.

Background

This project was built as coursework for a functional programming course, following an assignment titled At the Checkout, structured around Racket. The assignment progresses in lockstep with the course itself: each stage introduces exactly the language features covered in the preceding lecture and lab: structures and pattern matching, first-class functions and functionals, abstract data types, and lazy evaluation with streams, so the codebase doubles as a record of those concepts being put into practice.