097 Advanced

097 — Zipper

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "097 — Zipper" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Implement a list zipper — a functional cursor data structure that provides O(1) navigation (left/right) and O(1) update at the focus position. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Implement a list zipper — a functional cursor data structure that provides O(1) navigation (left/right) and O(1) update at the focus position. The zipper stores left (reversed prefix), focus (current element), and right (suffix). Compare with OCaml's idiomatic record-based zipper.

🎯 Learning Outcomes

• Model a zipper as { left: Vec<T>, focus: T, right: Vec<T> } where left is reversed

• Implement go_right: pop from right, push current focus to left

• Implement go_left: pop from left, push current focus to front of right

• Use update(f) -> Self for pure functional modification at the focus

• Reconstruct the full list with to_vec by reversing left + focus + right

• Map Rust's struct-based zipper to OCaml's record with list fields

Code Example

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 })
}

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 }

Key Differences

Aspect	Rust	OCaml
Left field	`Vec<T>` (reversed)	`'a list` (reversed, by convention)
Push to left	`left.push(focus)`	`focus :: left`
Pop from left	`left.pop()`	`h :: t` pattern
Record update	`Zipper { left, focus: …, right }`	`{ z with focus = … }`
Navigation result	`Option<Self>`	`'a zipper option`
Clone requirement	`T: Clone`	Value semantics (no explicit clone)

The zipper is the functional programmer's cursor. Instead of indices into a mutable array, it carries the context around the focus as a data structure. Navigation is O(1); reconstruction is O(n). Zippers generalise to trees (Huet zipper), enabling efficient functional editors.

OCaml Approach

OCaml's zipper uses immutable list fields: { left: 'a list; focus: 'a; right: 'a list }. go_right matches z.right as h :: t, returning { left = z.focus :: z.left; focus = h; right = t }. { z with focus = f z.focus } updates in place. to_list is List.rev z.left @ [z.focus] @ z.right. The OCaml version is more concise because list cons :: and pattern matching are built in.

Full Source

#![allow(clippy::all)]
//! # 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)

✓ Tests Rust test suite

#[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]);
    }
}

Deep 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

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

Exercises

Add insert_after(value: T) -> Self that inserts a new element immediately to the right of the focus.

Add delete_focus(self) -> Option<Self> that removes the current focus and moves right (or left if at the end).

Implement goto_start(self) -> Self that moves the focus to the leftmost position by repeatedly going left.

Extend the zipper to a TreeZipper<T> for binary trees, with go_down_left, go_down_right, and go_up operations.

In OCaml, implement a zipper for strings (treating the string as a list of characters) and use it to implement a simple text editor with insert/delete at cursor.

Open Source Repos

functional-rust

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

Rust