🎬 Fearless Concurrency Threads, Arc>, channels — safe parallelism enforced by the compiler.

📝 Text version (for readers / accessibility)

• std::thread::spawn creates OS threads — closures must be Send + 'static

• Arc> provides shared mutable state across threads safely

• Channels (mpsc) enable message passing — multiple producers, single consumer

• Send and Sync marker traits enforce thread safety at compile time

• Data races are impossible — the type system prevents them before your code runs

Example 277: Circular Buffer — Functional Queue

Difficulty: ⭐⭐ Category: Data Structures OCaml Source: https://dev.realworldocaml.org/

Problem Statement

Implement a functional queue with amortized O(1) enqueue and dequeue operations, using two lists (or vectors). This is the classic "banker's queue" from purely functional data structures.

Learning Outcomes

Implementing persistent-style data structures in Rust using ownership transfer
Amortized analysis: reversing the back list into the front list
Translating OCaml's immutable record updates (`{ q with ... }`) to Rust's `mut self` pattern
Using `Option<(T, Self)>` to return both a value and the updated structure

OCaml Approach

OCaml uses an immutable record with two lists. `enqueue` creates a new record with the element prepended to `back`. `dequeue` pattern-matches on `front`; when empty, reverses `back` into `front`. All operations return new values — the original queue is unchanged.

Rust Approach

Rust uses `Vec<T>` instead of linked lists. The queue takes ownership of `self` in `enqueue`/`dequeue` (consuming the old queue), which mirrors OCaml's functional semantics while allowing in-place mutation. The `remove(0)` on `front` is O(n) but happens rarely due to the amortized reversal strategy.

Key Differences

1. Ownership model: OCaml returns new immutable records; Rust consumes `self` and returns the modified queue — same semantics, but Rust reuses the allocation 2. List vs Vec: OCaml's linked lists have O(1) prepend; Rust's `Vec` has O(1) push but O(n) remove-from-front — a VecDeque would be more efficient but less pedagogical 3. Pattern matching: OCaml matches on list constructors (`h :: t`); Rust checks `is_empty()` and uses `remove(0)` 4. Record update: OCaml's `{ q with back = x :: q.back }` creates a new record; Rust's `mut self` modifies in place

#[derive(Debug, Clone)]
struct Queue<T> {
    front: Vec<T>,
    back: Vec<T>,
}

impl<T> Queue<T> {
    fn new() -> Self {
        Queue { front: Vec::new(), back: Vec::new() }
    }

    fn enqueue(mut self, x: T) -> Self {
        self.back.push(x);
        self
    }

    fn dequeue(mut self) -> Option<(T, Self)> {
        if self.front.is_empty() {
            if self.back.is_empty() {
                return None;
            }
            self.back.reverse();
            std::mem::swap(&mut self.front, &mut self.back);
        }
        let head = self.front.remove(0);
        Some((head, self))
    }
}

fn drain<T: std::fmt::Debug>(mut queue: Queue<T>) -> Vec<T> {
    let mut result = Vec::new();
    while let Some((x, rest)) = queue.dequeue() {
        result.push(x);
        queue = rest;
    }
    result
}

fn main() {
    let q = Queue::new().enqueue(1).enqueue(2).enqueue(3);
    let drained = drain(q);
    println!("Drained: {:?}", drained);

    // Interleaved operations
    let q = Queue::new().enqueue(1).enqueue(2);
    let (val, q) = q.dequeue().unwrap();
    println!("Dequeued: {}", val);
    let q = q.enqueue(3);
    println!("Remaining: {:?}", drain(q));
}

/* Output:
   Drained: [1, 2, 3]
   Dequeued: 1
   Remaining: [2, 3]
*/

type 'a queue = { front: 'a list; back: 'a list }

let empty = { front = []; back = [] }
let is_empty q = q.front = [] && q.back = []

let enqueue x q = { q with back = x :: q.back }

let dequeue q = match q.front with
  | h :: t -> Some (h, { q with front = t })
  | [] -> match List.rev q.back with
    | [] -> None
    | h :: t -> Some (h, { front = t; back = [] })

let to_list q = q.front @ List.rev q.back

let () =
  let q = empty |> enqueue 1 |> enqueue 2 |> enqueue 3 in
  assert (to_list q = [1; 2; 3]);
  let rec drain q = match dequeue q with
    | None -> []
    | Some (x, q') -> x :: drain q'
  in
  assert (drain q = [1; 2; 3]);
  (* Test interleaved operations *)
  let q2 = empty |> enqueue 1 |> enqueue 2 in
  let (v, q2) = match dequeue q2 with Some p -> p | None -> assert false in
  assert (v = 1);
  let q2 = enqueue 3 q2 in
  assert (drain q2 = [2; 3]);
  print_endline "ok"

📊 Detailed Comparison

OCaml vs Rust: Circular Buffer — Functional Queue

Side-by-Side Code

OCaml

🐪 Show OCaml equivalent

type 'a queue = { front: 'a list; back: 'a list }

let empty = { front = []; back = [] }
let is_empty q = q.front = [] && q.back = []
let enqueue x q = { q with back = x :: q.back }

let dequeue q = match q.front with
| h :: t -> Some (h, { q with front = t })
| [] -> match List.rev q.back with
 | [] -> None
 | h :: t -> Some (h, { front = t; back = [] })

let to_list q = q.front @ List.rev q.back

Rust (idiomatic)

#[derive(Debug, Clone)]
pub struct Queue<T> {
 front: Vec<T>,
 back: Vec<T>,
}

impl<T> Queue<T> {
 pub fn new() -> Self { Queue { front: Vec::new(), back: Vec::new() } }
 pub fn is_empty(&self) -> bool { self.front.is_empty() && self.back.is_empty() }
 pub fn enqueue(mut self, x: T) -> Self { self.back.push(x); self }

 pub fn dequeue(mut self) -> Option<(T, Self)> {
     if self.front.is_empty() {
         if self.back.is_empty() { return None; }
         self.back.reverse();
         std::mem::swap(&mut self.front, &mut self.back);
     }
     let head = self.front.remove(0);
     Some((head, self))
 }
}

Rust (functional/recursive drain)

pub fn drain_recursive<T>(queue: Queue<T>) -> Vec<T> {
 match queue.dequeue() {
     None => Vec::new(),
     Some((x, rest)) => {
         let mut result = vec![x];
         result.extend(drain_recursive(rest));
         result
     }
 }
}

Type Signatures

Concept	OCaml	Rust
Queue type	`'a queue` (record with two lists)	`Queue<T>` (struct with two Vecs)
Empty check	`val is_empty : 'a queue -> bool`	`fn is_empty(&self) -> bool`
Enqueue	`val enqueue : 'a -> 'a queue -> 'a queue`	`fn enqueue(self, x: T) -> Self`
Dequeue	`val dequeue : 'a queue -> ('a * 'a queue) option`	`fn dequeue(self) -> Option<(T, Self)>`
To list	`val to_list : 'a queue -> 'a list`	`fn to_vec(&self) -> Vec<&T>`

Key Insights

1. Consuming self mirrors immutability: Rust's `fn dequeue(self)` takes ownership, preventing use of the old queue — this enforces the same "one version at a time" discipline as OCaml's immutable approach, but through the type system rather than runtime copying 2. `std::mem::swap` for efficient reversal: Instead of OCaml's `List.rev` which allocates a new list, Rust reverses `back` in place and swaps it into `front` with zero allocation 3. Tuple return pattern: Both languages return `Option<(T, Queue)>` — the element and the remaining queue. This is natural in OCaml; in Rust it works because `Self` is moved, not copied 4. Record update vs mutation: OCaml's `{ q with back = x :: q.back }` creates a new record sharing most fields; Rust's `mut self` modifies the existing struct in place — same semantics from the caller's perspective 5. Amortized cost: Both implementations achieve amortized O(1) per operation — each element is reversed at most once. The Rust version additionally benefits from cache-friendly Vec layout

When to Use Each Style

Use idiomatic Rust when: You need a production queue — use `VecDeque` from std which provides O(1) push/pop on both ends with a ring buffer. The two-Vec approach is primarily pedagogical.

Use recursive Rust when: Teaching functional data structure concepts — the recursive `drain` mirrors OCaml's recursive traversal pattern and makes the "peel one element at a time" structure explicit.