🎬 How Rust Iterators Work Lazy evaluation, chaining, collect(), and zero-cost abstractions.

📝 Text version (for readers / accessibility)

• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed

• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection

• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops

• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably

• Chaining replaces nested loops with a readable, composable pipeline

097: Zipper — Functional List Cursor

Difficulty: 3 Level: Intermediate A data structure that marks a position in a list for O(1) local edits — focus + context, no index arithmetic.

The Problem This Solves

When you need to navigate and edit a position inside a list repeatedly — a text editor cursor, a game board traversal, a tree walk — the naive approach is to keep an integer index and slice. But every edit requires rebuilding the whole structure around that index. A Zipper splits the list into three parts: elements to the left (reversed), the focused element, and elements to the right. Moving left or right, replacing the focus, inserting, or deleting are all O(1) — no rebuilding, no index bounds to manage. The Zipper originated in OCaml/Haskell as a functional answer to "how do you efficiently walk and edit a position in an immutable data structure."

The Intuition

Imagine holding a bead curtain. Your hand is the focus. Beads to your left fall behind you (reversed in memory for O(1) access). Beads to your right hang in front. Moving left: take the nearest bead from your left pile, make it the new focus, push old focus onto the right. Moving right: mirror operation. The reversed-left invariant is the key insight. The top of `left` (the last element pushed) is always the immediate left neighbor of `focus` — so `left.pop()` and `left.push()` are the move operations.

How It Works in Rust

#[derive(Debug, Clone)]
pub struct Zipper<T> {
 left: Vec<T>,   // reversed: top = nearest to focus
 focus: T,
 right: Vec<T>,  // normal order: front = nearest to focus
}

impl<T: Clone> Zipper<T> {
 pub fn from_vec(v: Vec<T>) -> Option<Self> {
     let mut iter = v.into_iter();
     let focus = iter.next()?;       // first element becomes focus
     Some(Zipper { left: vec![], focus, right: iter.collect() })
 }

 pub fn go_right(&self) -> Option<Self> {
     let mut right = self.right.clone();
     if right.is_empty() { return None; }
     let new_focus = right.remove(0);      // take from front of right
     let mut left = self.left.clone();
     left.push(self.focus.clone());         // push old focus onto left
     Some(Zipper { left, focus: new_focus, right })
 }

 pub fn go_left(&self) -> Option<Self> {
     let mut left = self.left.clone();
     let new_focus = left.pop()?;           // pop from top of reversed-left
     let mut right = self.right.clone();
     right.insert(0, self.focus.clone());   // push old focus onto right
     Some(Zipper { left, focus: new_focus, right })
 }

 pub fn set_focus(&self, value: T) -> Self {
     // Replace focus: O(1) — only touch one field
     Zipper { left: self.left.clone(), focus: value, right: self.right.clone() }
 }

 pub fn to_vec(&self) -> Vec<T> {
     // Reconstruct: reverse left, add focus, add right
     let mut v: Vec<T> = self.left.iter().rev().cloned().collect();
     v.push(self.focus.clone());
     v.extend(self.right.iter().cloned());
     v
 }
}

The clone-based approach is idiomatic for functional style. For high-performance use cases, use `VecDeque` with split positions.

What This Unlocks

Text editors: cursor movement and insertion without rebuilding the buffer.
Tree traversal: extend Zipper to trees — walk up, down, left, right with a "breadcrumb" context stack.
Game boards: navigate cells and modify them locally without full-board copies.

Key Differences

Concept	OCaml	Rust
Record type	`type 'a t = { left: 'a list; focus: 'a; right: 'a list }`	`struct Zipper<T> { left: Vec<T>, focus: T, right: Vec<T> }`
Functional update	`{ z with focus = v }`	`.set_focus(v)` clones and replaces
Left invariant	Reversed list	Reversed `Vec` (same)
Move right	`List.hd right`, cons to left	`right.remove(0)`, push to left
Immutable by default	Yes	Via clone; or use `&mut self` for in-place

//! # Zipper — Functional List Cursor
//!
//! A zipper provides O(1) navigation and update at the focus point.
//! OCaml's record with `{ left; focus; right }` maps directly to a Rust struct.

// ---------------------------------------------------------------------------
// Approach A: Struct with Vec (idiomatic Rust)
// ---------------------------------------------------------------------------

#[derive(Debug, Clone, PartialEq)]
pub struct Zipper<T> {
    left: Vec<T>,  // reversed — top is nearest to focus
    focus: T,
    right: Vec<T>,
}

impl<T: Clone> Zipper<T> {
    pub fn from_vec(v: Vec<T>) -> Option<Self> {
        let mut iter = v.into_iter();
        let focus = iter.next()?;
        Some(Zipper {
            left: vec![],
            focus,
            right: iter.collect(),
        })
    }

    pub fn focus(&self) -> &T {
        &self.focus
    }

    pub fn go_right(&self) -> Option<Self> {
        let mut right = self.right.clone();
        if right.is_empty() {
            return None;
        }
        let new_focus = right.remove(0);
        let mut left = self.left.clone();
        left.push(self.focus.clone());
        Some(Zipper { left, focus: new_focus, right })
    }

    pub fn go_left(&self) -> Option<Self> {
        let mut left = self.left.clone();
        let new_focus = left.pop()?;
        let mut right = self.right.clone();
        right.insert(0, self.focus.clone());
        Some(Zipper { left, focus: new_focus, right })
    }

    pub fn update<F: FnOnce(&T) -> T>(&self, f: F) -> Self {
        Zipper {
            left: self.left.clone(),
            focus: f(&self.focus),
            right: self.right.clone(),
        }
    }

    pub fn to_vec(&self) -> Vec<T> {
        let mut result: Vec<T> = self.left.iter().cloned().collect();
        result.push(self.focus.clone());
        result.extend(self.right.iter().cloned());
        result
    }
}

// ---------------------------------------------------------------------------
// Approach B: VecDeque-based for O(1) operations
// ---------------------------------------------------------------------------

use std::collections::VecDeque;

#[derive(Debug, Clone)]
pub struct ZipperDeque<T> {
    left: Vec<T>,
    focus: T,
    right: VecDeque<T>,
}

impl<T: Clone> ZipperDeque<T> {
    pub fn from_vec(v: Vec<T>) -> Option<Self> {
        let mut dq: VecDeque<T> = v.into();
        let focus = dq.pop_front()?;
        Some(ZipperDeque { left: vec![], focus, right: dq })
    }

    pub fn go_right(&mut self) -> bool {
        if let Some(new_focus) = self.right.pop_front() {
            let old = std::mem::replace(&mut self.focus, new_focus);
            self.left.push(old);
            true
        } else {
            false
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_basic_navigation() {
        let z = Zipper::from_vec(vec![1, 2, 3, 4, 5]).unwrap();
        let z = z.go_right().unwrap();
        let z = z.go_right().unwrap();
        assert_eq!(*z.focus(), 3);
    }

    #[test]
    fn test_update() {
        let z = Zipper::from_vec(vec![1, 2, 3, 4, 5]).unwrap();
        let z = z.go_right().unwrap().go_right().unwrap();
        let z = z.update(|x| x * 10);
        assert_eq!(z.to_vec(), vec![1, 2, 30, 4, 5]);
    }

    #[test]
    fn test_go_left() {
        let z = Zipper::from_vec(vec![1, 2, 3]).unwrap();
        let z = z.go_right().unwrap().go_right().unwrap();
        let z = z.go_left().unwrap();
        assert_eq!(*z.focus(), 2);
    }

    #[test]
    fn test_boundary() {
        let z = Zipper::from_vec(vec![1]).unwrap();
        assert!(z.go_right().is_none());
        assert!(z.go_left().is_none());
    }

    #[test]
    fn test_empty() {
        assert!(Zipper::<i32>::from_vec(vec![]).is_none());
    }

    #[test]
    fn test_to_vec_preserves_order() {
        let z = Zipper::from_vec(vec![1, 2, 3, 4, 5]).unwrap();
        assert_eq!(z.to_vec(), vec![1, 2, 3, 4, 5]);
    }
}

type 'a zipper = { left: 'a list; focus: 'a; right: 'a list }

let of_list = function
  | [] -> failwith "empty"
  | h :: t -> { left = []; focus = h; right = t }

let go_right z = match z.right with
  | [] -> None
  | h :: t -> Some { left = z.focus :: z.left; focus = h; right = t }

let go_left z = match z.left with
  | [] -> None
  | h :: t -> Some { left = t; focus = h; right = z.focus :: z.right }

let update f z = { z with focus = f z.focus }
let to_list z = List.rev z.left @ [z.focus] @ z.right

let () =
  let z = of_list [1;2;3;4;5] in
  let z = Option.get (go_right z) in
  let z = Option.get (go_right z) in
  let z = update (fun x -> x * 10) z in
  List.iter (Printf.printf "%d ") (to_list z)

📊 Detailed Comparison

Comparison: Zipper — OCaml vs Rust

Core Insight

OCaml's zipper is a textbook functional data structure: a record with three fields, navigated by pattern matching on lists. Rust's version faces the clone-vs-mutate dilemma: immutable zippers require cloning vectors on every move, while mutable zippers with `VecDeque` are more efficient but lose the functional purity.

OCaml

🐪 Show OCaml equivalent

type 'a zipper = { left: 'a list; focus: 'a; right: 'a list }

let go_right z = match z.right with
| [] -> None
| h :: t -> Some { left = z.focus :: z.left; focus = h; right = t }

let update f z = { z with focus = f z.focus }

Rust — Immutable

pub fn go_right(&self) -> Option<Self> {
 let mut right = self.right.clone();
 if right.is_empty() { return None; }
 let new_focus = right.remove(0);
 let mut left = self.left.clone();
 left.push(self.focus.clone());
 Some(Zipper { left, focus: new_focus, right })
}

Comparison Table

Aspect	OCaml	Rust
Type	`'a zipper` record	`Zipper<T>` struct
Polymorphism	Built-in `'a`	Generic `<T: Clone>`
Record update	`{ z with focus = ... }`	Must clone fields manually
List ops	O(1) cons/head	O(n) `remove(0)` on Vec
Navigation cost	O(1)	O(n) clone or O(1) mutable
Option wrapping	`Some { ... }`	`Some(Zipper { ... })`

Learner Notes

Clone cost: OCaml's list cons is O(1) because it's just pointer manipulation. Rust's `Vec::clone` copies all elements — significant difference
`VecDeque`: Rust's double-ended queue gives O(1) `pop_front`/`push_front`, making mutable zippers efficient
Functional record update: OCaml's `{ z with field = ... }` is concise; Rust has no equivalent — you must construct a new struct
Ownership choice: Immutable zipper = clone on every move (safe, slow). Mutable zipper = `&mut self` (fast, less composable)
The zipper pattern is less common in Rust because iterators and indices often suffice