1048 Advanced

1048-zipper-vec — Vec Zipper

Functional Programming

Tutorial

The Problem

A zipper is a data structure that provides a "cursor" into a sequence, allowing O(1) local navigation and modification. Introduced by Gérard Huet in 1997 for functional tree navigation, the zipper splits a sequence into three parts: elements to the left of the focus, the currently-focused element, and elements to the right.

The zipper is used in functional text editors (yi, kakoune's core), syntax tree cursors in parser combinators, and game state navigation for undo/redo.

🎯 Learning Outcomes

• Understand the zipper data structure: left (reversed), focus, right

• Implement move_left and move_right as O(1) operations

• Modify the focused element without rebuilding the whole sequence

• Reconstruct the full sequence from the zipper representation

• Connect to OCaml's zipper applications in text editors and tree traversal

Code Example

#![allow(clippy::all)]
// 1048: Vec Zipper — Cursor (Left, Focus, Right)
// A zipper provides O(1) local navigation and modification

/// A zipper over a sequence: left (reversed), focus, right
#[derive(Debug, Clone)]
struct Zipper<T> {
    left: Vec<T>, // reversed: closest to focus is last
    focus: T,
    right: Vec<T>,
}

impl<T: Clone> Zipper<T> {
    /// Create from a non-empty slice
    fn from_slice(data: &[T]) -> Option<Self> {
        if data.is_empty() {
            return None;
        }
        Some(Zipper {
            left: Vec::new(),
            focus: data[0].clone(),
            right: data[1..].to_vec(),
        })
    }

    /// Reconstruct the full sequence
    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
    }

    /// Move focus right
    fn move_right(&mut self) -> bool {
        if self.right.is_empty() {
            return false;
        }
        let old_focus = std::mem::replace(&mut self.focus, self.right.remove(0));
        self.left.push(old_focus);
        true
    }

    /// Move focus left
    fn move_left(&mut self) -> bool {
        if self.left.is_empty() {
            return false;
        }
        let old_focus = std::mem::replace(&mut self.focus, self.left.pop().unwrap());
        self.right.insert(0, old_focus);
        true
    }

    /// Move to start
    fn move_to_start(&mut self) {
        while self.move_left() {}
    }

    /// Move to end
    fn move_to_end(&mut self) {
        while self.move_right() {}
    }

    /// Set focus value
    fn set(&mut self, value: T) {
        self.focus = value;
    }

    // Note: generic modify needs T: Default (see modify_safe below)

    /// Insert element to the right of focus
    fn insert_right(&mut self, value: T) {
        self.right.insert(0, value);
    }

    /// Insert element to the left of focus
    fn insert_left(&mut self, value: T) {
        self.left.push(value);
    }

    /// Delete element to the right of focus
    fn delete_right(&mut self) -> Option<T> {
        if self.right.is_empty() {
            None
        } else {
            Some(self.right.remove(0))
        }
    }

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

// Safe modify without zeroed()
impl<T: Default> Zipper<T> {
    fn modify_safe<F: FnOnce(T) -> T>(&mut self, f: F) {
        let old = std::mem::take(&mut self.focus);
        self.focus = f(old);
    }
}

fn navigation_test() {
    let mut z = Zipper::from_slice(&[1, 2, 3, 4, 5]).unwrap();
    assert_eq!(*z.focus(), 1);

    assert!(z.move_right());
    assert_eq!(*z.focus(), 2);

    assert!(z.move_right());
    assert_eq!(*z.focus(), 3);

    assert!(z.move_left());
    assert_eq!(*z.focus(), 2);

    assert_eq!(z.to_vec(), vec![1, 2, 3, 4, 5]);
}

fn modification_test() {
    let mut z = Zipper::from_slice(&[1, 2, 3, 4, 5]).unwrap();
    z.move_right();
    z.move_right();
    z.set(99);
    assert_eq!(z.to_vec(), vec![1, 2, 99, 4, 5]);

    z.modify_safe(|x| x * 2);
    assert_eq!(*z.focus(), 198);
}

fn editor_test() {
    let mut z = Zipper::from_slice(&['h', 'e', 'l', 'o']).unwrap();
    z.move_right(); // e
    z.move_right(); // l
    z.insert_right('l'); // insert 'l' after current
    assert_eq!(z.to_vec(), vec!['h', 'e', 'l', 'l', 'o']);
}

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

    #[test]
    fn test_navigation() {
        navigation_test();
    }

    #[test]
    fn test_modification() {
        modification_test();
    }

    #[test]
    fn test_editor() {
        editor_test();
    }

    #[test]
    fn test_boundaries() {
        let mut z = Zipper::from_slice(&[1]).unwrap();
        assert!(!z.move_left());
        assert!(!z.move_right());
        assert_eq!(*z.focus(), 1);
    }

    #[test]
    fn test_move_to_extremes() {
        let mut z = Zipper::from_slice(&[1, 2, 3, 4, 5]).unwrap();
        z.move_to_end();
        assert_eq!(*z.focus(), 5);
        z.move_to_start();
        assert_eq!(*z.focus(), 1);
    }
}

(* 1048: Vec Zipper — Cursor with Left, Focus, Right *)
(* A zipper provides O(1) local navigation and modification *)

type 'a zipper = {
  left: 'a list;    (* reversed: closest element first *)
  focus: 'a;
  right: 'a list;
}

(* Construction *)
let of_list = function
  | [] -> None
  | x :: xs -> Some { left = []; focus = x; right = xs }

let to_list z =
  List.rev z.left @ [z.focus] @ z.right

(* Navigation *)
let move_right z =
  match z.right with
  | [] -> None
  | x :: xs -> Some { left = z.focus :: z.left; focus = x; right = xs }

let move_left z =
  match z.left with
  | [] -> None
  | x :: xs -> Some { left = xs; focus = x; right = z.focus :: z.right }

let move_to_start z =
  let rec go z =
    match move_left z with
    | None -> z
    | Some z' -> go z'
  in
  go z

let move_to_end z =
  let rec go z =
    match move_right z with
    | None -> z
    | Some z' -> go z'
  in
  go z

(* Modification at focus *)
let set value z = { z with focus = value }
let modify f z = { z with focus = f z.focus }
let insert_right value z = { z with right = value :: z.right }
let insert_left value z = { z with left = value :: z.left }

let delete_right z =
  match z.right with
  | [] -> None
  | _ :: xs -> Some { z with right = xs }

(* Approach 1: Basic navigation *)
let navigation_test () =
  let z = Option.get (of_list [1; 2; 3; 4; 5]) in
  assert (z.focus = 1);
  let z = Option.get (move_right z) in
  assert (z.focus = 2);
  let z = Option.get (move_right z) in
  assert (z.focus = 3);
  let z = Option.get (move_left z) in
  assert (z.focus = 2);
  assert (to_list z = [1; 2; 3; 4; 5])

(* Approach 2: Modification *)
let modification_test () =
  let z = Option.get (of_list [1; 2; 3; 4; 5]) in
  let z = Option.get (move_right z) in
  let z = Option.get (move_right z) in
  let z = set 99 z in  (* Change 3 to 99 *)
  assert (to_list z = [1; 2; 99; 4; 5]);
  let z = modify (fun x -> x * 2) z in  (* 99 -> 198 *)
  assert (z.focus = 198)

(* Approach 3: Text editor cursor simulation *)
let editor_test () =
  let z = Option.get (of_list ['h'; 'e'; 'l'; 'o']) in
  let z = Option.get (move_right z) in
  let z = Option.get (move_right z) in
  (* Insert 'l' after current position *)
  let z = insert_right 'l' z in
  assert (to_list z = ['h'; 'e'; 'l'; 'l'; 'o'])

let () =
  navigation_test ();
  modification_test ();
  editor_test ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Mutability: Rust's Zipper mutates in place with &mut self; OCaml's zipper returns new values (pure navigation).

Undo support: OCaml's immutable zipper naturally supports undo (keep old zipper in scope); Rust needs explicit state saving.

Left reversal: Both represent the left side reversed for O(1) access to the nearest left neighbor.

Huet's original: Huet's paper used tree zippers for XML/S-expression navigation; this example simplifies to sequences. Tree zippers are more complex but follow the same principle.

OCaml Approach

Huet's original zipper was for trees, but the list zipper is the canonical introduction:

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

let move_right z = match z.right with
  | [] -> None
  | x :: xs -> Some { left = z.focus :: z.left; focus = x; right = xs }

let move_left z = match z.left with
  | [] -> None
  | x :: xs -> Some { left = xs; focus = x; right = z.focus :: z.right }

OCaml's immutable lists make zipper navigation pure: each move returns a new zipper value, leaving the old one intact for undo.

Full Source

#![allow(clippy::all)]
// 1048: Vec Zipper — Cursor (Left, Focus, Right)
// A zipper provides O(1) local navigation and modification

/// A zipper over a sequence: left (reversed), focus, right
#[derive(Debug, Clone)]
struct Zipper<T> {
    left: Vec<T>, // reversed: closest to focus is last
    focus: T,
    right: Vec<T>,
}

impl<T: Clone> Zipper<T> {
    /// Create from a non-empty slice
    fn from_slice(data: &[T]) -> Option<Self> {
        if data.is_empty() {
            return None;
        }
        Some(Zipper {
            left: Vec::new(),
            focus: data[0].clone(),
            right: data[1..].to_vec(),
        })
    }

    /// Reconstruct the full sequence
    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
    }

    /// Move focus right
    fn move_right(&mut self) -> bool {
        if self.right.is_empty() {
            return false;
        }
        let old_focus = std::mem::replace(&mut self.focus, self.right.remove(0));
        self.left.push(old_focus);
        true
    }

    /// Move focus left
    fn move_left(&mut self) -> bool {
        if self.left.is_empty() {
            return false;
        }
        let old_focus = std::mem::replace(&mut self.focus, self.left.pop().unwrap());
        self.right.insert(0, old_focus);
        true
    }

    /// Move to start
    fn move_to_start(&mut self) {
        while self.move_left() {}
    }

    /// Move to end
    fn move_to_end(&mut self) {
        while self.move_right() {}
    }

    /// Set focus value
    fn set(&mut self, value: T) {
        self.focus = value;
    }

    // Note: generic modify needs T: Default (see modify_safe below)

    /// Insert element to the right of focus
    fn insert_right(&mut self, value: T) {
        self.right.insert(0, value);
    }

    /// Insert element to the left of focus
    fn insert_left(&mut self, value: T) {
        self.left.push(value);
    }

    /// Delete element to the right of focus
    fn delete_right(&mut self) -> Option<T> {
        if self.right.is_empty() {
            None
        } else {
            Some(self.right.remove(0))
        }
    }

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

// Safe modify without zeroed()
impl<T: Default> Zipper<T> {
    fn modify_safe<F: FnOnce(T) -> T>(&mut self, f: F) {
        let old = std::mem::take(&mut self.focus);
        self.focus = f(old);
    }
}

fn navigation_test() {
    let mut z = Zipper::from_slice(&[1, 2, 3, 4, 5]).unwrap();
    assert_eq!(*z.focus(), 1);

    assert!(z.move_right());
    assert_eq!(*z.focus(), 2);

    assert!(z.move_right());
    assert_eq!(*z.focus(), 3);

    assert!(z.move_left());
    assert_eq!(*z.focus(), 2);

    assert_eq!(z.to_vec(), vec![1, 2, 3, 4, 5]);
}

fn modification_test() {
    let mut z = Zipper::from_slice(&[1, 2, 3, 4, 5]).unwrap();
    z.move_right();
    z.move_right();
    z.set(99);
    assert_eq!(z.to_vec(), vec![1, 2, 99, 4, 5]);

    z.modify_safe(|x| x * 2);
    assert_eq!(*z.focus(), 198);
}

fn editor_test() {
    let mut z = Zipper::from_slice(&['h', 'e', 'l', 'o']).unwrap();
    z.move_right(); // e
    z.move_right(); // l
    z.insert_right('l'); // insert 'l' after current
    assert_eq!(z.to_vec(), vec!['h', 'e', 'l', 'l', 'o']);
}

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

    #[test]
    fn test_navigation() {
        navigation_test();
    }

    #[test]
    fn test_modification() {
        modification_test();
    }

    #[test]
    fn test_editor() {
        editor_test();
    }

    #[test]
    fn test_boundaries() {
        let mut z = Zipper::from_slice(&[1]).unwrap();
        assert!(!z.move_left());
        assert!(!z.move_right());
        assert_eq!(*z.focus(), 1);
    }

    #[test]
    fn test_move_to_extremes() {
        let mut z = Zipper::from_slice(&[1, 2, 3, 4, 5]).unwrap();
        z.move_to_end();
        assert_eq!(*z.focus(), 5);
        z.move_to_start();
        assert_eq!(*z.focus(), 1);
    }
}

(* 1048: Vec Zipper — Cursor with Left, Focus, Right *)
(* A zipper provides O(1) local navigation and modification *)

type 'a zipper = {
  left: 'a list;    (* reversed: closest element first *)
  focus: 'a;
  right: 'a list;
}

(* Construction *)
let of_list = function
  | [] -> None
  | x :: xs -> Some { left = []; focus = x; right = xs }

let to_list z =
  List.rev z.left @ [z.focus] @ z.right

(* Navigation *)
let move_right z =
  match z.right with
  | [] -> None
  | x :: xs -> Some { left = z.focus :: z.left; focus = x; right = xs }

let move_left z =
  match z.left with
  | [] -> None
  | x :: xs -> Some { left = xs; focus = x; right = z.focus :: z.right }

let move_to_start z =
  let rec go z =
    match move_left z with
    | None -> z
    | Some z' -> go z'
  in
  go z

let move_to_end z =
  let rec go z =
    match move_right z with
    | None -> z
    | Some z' -> go z'
  in
  go z

(* Modification at focus *)
let set value z = { z with focus = value }
let modify f z = { z with focus = f z.focus }
let insert_right value z = { z with right = value :: z.right }
let insert_left value z = { z with left = value :: z.left }

let delete_right z =
  match z.right with
  | [] -> None
  | _ :: xs -> Some { z with right = xs }

(* Approach 1: Basic navigation *)
let navigation_test () =
  let z = Option.get (of_list [1; 2; 3; 4; 5]) in
  assert (z.focus = 1);
  let z = Option.get (move_right z) in
  assert (z.focus = 2);
  let z = Option.get (move_right z) in
  assert (z.focus = 3);
  let z = Option.get (move_left z) in
  assert (z.focus = 2);
  assert (to_list z = [1; 2; 3; 4; 5])

(* Approach 2: Modification *)
let modification_test () =
  let z = Option.get (of_list [1; 2; 3; 4; 5]) in
  let z = Option.get (move_right z) in
  let z = Option.get (move_right z) in
  let z = set 99 z in  (* Change 3 to 99 *)
  assert (to_list z = [1; 2; 99; 4; 5]);
  let z = modify (fun x -> x * 2) z in  (* 99 -> 198 *)
  assert (z.focus = 198)

(* Approach 3: Text editor cursor simulation *)
let editor_test () =
  let z = Option.get (of_list ['h'; 'e'; 'l'; 'o']) in
  let z = Option.get (move_right z) in
  let z = Option.get (move_right z) in
  (* Insert 'l' after current position *)
  let z = insert_right 'l' z in
  assert (to_list z = ['h'; 'e'; 'l'; 'l'; 'o'])

let () =
  navigation_test ();
  modification_test ();
  editor_test ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_navigation() {
        navigation_test();
    }

    #[test]
    fn test_modification() {
        modification_test();
    }

    #[test]
    fn test_editor() {
        editor_test();
    }

    #[test]
    fn test_boundaries() {
        let mut z = Zipper::from_slice(&[1]).unwrap();
        assert!(!z.move_left());
        assert!(!z.move_right());
        assert_eq!(*z.focus(), 1);
    }

    #[test]
    fn test_move_to_extremes() {
        let mut z = Zipper::from_slice(&[1, 2, 3, 4, 5]).unwrap();
        z.move_to_end();
        assert_eq!(*z.focus(), 5);
        z.move_to_start();
        assert_eq!(*z.focus(), 1);
    }
}

Deep Comparison

Vec Zipper — Comparison

Core Insight

A zipper splits a data structure into context + focus, enabling O(1) local operations. OCaml's list zipper is elegant (two lists, one reversed). Rust's version uses Vec but faces ownership friction — std::mem::take/replace needed to move the focus value.

OCaml Approach

• { left: 'a list; focus: 'a; right: 'a list } — classic zipper

• left is reversed: closest element at head

• Navigation: cons focus onto one side, pop from other

• Immutable — each move returns a new zipper

• Shares structure with original list

Rust Approach

• { left: Vec<T>, focus: T, right: Vec<T> } — Vec-based

• Mutable: move_right/move_left modify in place

• std::mem::replace / std::mem::take for ownership transfer

• remove(0) on right Vec is O(n) — could use VecDeque for O(1)

• Default trait bound needed for safe modify

Comparison Table

Feature	OCaml	Rust
Left storage	List (reversed)	Vec (push/pop at end)
Right storage	List	Vec (insert/remove at 0)
Move cost	O(1)	O(1) left, O(n) right*
Mutability	Immutable	Mutable
Focus transfer	Pattern match	`std::mem::replace`
Sharing	Structural sharing	No (owned)

*Right-side O(n) can be fixed with VecDeque or reversed Vec.

Exercises

Implement find_right<F: Fn(&T) -> bool>(pred: F) -> bool that moves the focus right until the predicate is satisfied.

Add insert_after(&mut self, value: T) that inserts a new element immediately to the right of the focus.

Implement a simple line editor using Zipper<char> where the focus represents the cursor position.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust