🎬 Traits & Generics Shared behaviour, static vs dynamic dispatch, zero-cost polymorphism.

📝 Text version (for readers / accessibility)

• Traits define shared behaviour — like interfaces but with default implementations

• Generics with trait bounds: fn process(item: T) — monomorphized at compile time

• Static dispatch (impl Trait) = zero cost; dynamic dispatch (dyn Trait) = runtime flexibility via vtable

• Blanket implementations apply traits to all types matching a bound

• Associated types and supertraits enable complex type relationships

208: Traversal

Difficulty: ⭐⭐⭐ Level: Advanced A Lens that focuses on multiple targets at once — apply a function to every element of a `Vec`, every leaf of a tree, or every matching value, collecting all results.

The Problem This Solves

You have a data structure — a list, a tree, a config object with many optional fields — and you want to transform all of a certain kind of value inside it. With a Lens you can reach one field. But what about all elements? What about all the leaf nodes in a tree? What about every even number in a list? The naive approach is to write a custom function for every case:

fn double_all(xs: Vec<i32>) -> Vec<i32> { xs.into_iter().map(|x| x * 2).collect() }
fn double_evens(xs: Vec<i32>) -> Vec<i32> { xs.into_iter().map(|x| if x % 2 == 0 { x * 2 } else { x }).collect() }
fn double_leaves(t: Tree<i32>) -> Tree<i32> { /* recursive case ... */ }

Each of these is bespoke. You can't compose them. You can't write a generic "count the targets" or "collect all targets into a list" without reimplementing it for each structure. You can't make a filtered version that targets only some elements. A Traversal packages the "how to walk and modify this structure" logic into a reusable value, letting you write `over`, `collect`, `length_of`, `sum_of`, `all_of`, `any_of` once and use them with any Traversal. This exists to solve exactly that pain.

The Intuition

A Lens focuses on exactly one value inside a structure (e.g., the `x` field of a `Point`). A Traversal is a Lens that can focus on zero or more values at once. Think of a Traversal as a reusable "visiting pattern." It encodes where to look inside a structure, and gives you two fundamental operations: 1. `over` (modify all) — apply a function to every focused value and rebuild the structure. 2. `collect` (list all) — extract every focused value into a `Vec`. Everything else is derived: count them (`length_of`), sum them (`sum_of`), check all (`all_of`), check any (`any_of`). Analogy: A Traversal is like a CSS selector. The selector `.foo` says "target all elements with class foo." You can then `.map()` over them, `.filter()` them, count them — but the selector itself is reusable and composable, separate from what you do with it.

// A Traversal carries two pieces of logic:
struct Traversal<S, A> {
 over:    Box<dyn Fn(&dyn Fn(&A) -> A, &S) -> S>,  // modify all focused A's in S
 to_list: Box<dyn Fn(&S) -> Vec<A>>,                // collect all focused A's
}
//
// S = the structure (e.g., Vec<i32>, Tree<String>)
// A = the focused element type (e.g., i32, String)

The key insight: `traverse` applies an effectful function to each target and collects results. This is how `Option<Vec<T>>` ↔ `Vec<Option<T>>` flipping works — you traverse a `Vec` with a function that returns `Option`, and the traversal collects into `Option<Vec<T>>`, short-circuiting on the first `None`.

How It Works in Rust

// Step 1: The Traversal type — two operations bundled together
struct Traversal<S, A> {
 over:    Box<dyn Fn(&dyn Fn(&A) -> A, &S) -> S>,
 to_list: Box<dyn Fn(&S) -> Vec<A>>,
}

impl<S: 'static, A: 'static> Traversal<S, A> {
 fn modify(&self, f: &dyn Fn(&A) -> A, s: &S) -> S { (self.over)(f, s) }
 fn collect(&self, s: &S) -> Vec<A>               { (self.to_list)(s) }

 // Derived combinators — built once, work for any Traversal
 fn length_of(&self, s: &S) -> usize { self.collect(s).len() }
}

// Step 2: A simple Traversal — target every element of a Vec
fn each_traversal<T: Clone + 'static>() -> Traversal<Vec<T>, T> {
 Traversal {
     over:    Box::new(|f, xs| xs.iter().map(|x| f(x)).collect()),
     to_list: Box::new(|xs| xs.clone()),
 }
}

let t = each_traversal::<i32>();
let xs = vec![1, 2, 3, 4, 5];
t.collect(&xs);               // [1, 2, 3, 4, 5]
t.modify(&|x| x * 2, &xs);   // [2, 4, 6, 8, 10]
t.length_of(&xs);             // 5

// Step 3: A Traversal over a tree — visits every Leaf
fn each_leaf<T: Clone + 'static>() -> Traversal<Tree<T>, T> {
 fn walk<T: Clone>(f: &dyn Fn(&T) -> T, t: &Tree<T>) -> Tree<T> {
     match t {
         Tree::Leaf(x)       => Tree::Leaf(f(x)),          // apply f at leaves
         Tree::Branch(l, r)  => Tree::Branch(             // recurse into branches
             Box::new(walk(f, l)),
             Box::new(walk(f, r)),
         ),
     }
 }
 // ... (to_list recursively collects leaves)
}

let tree = Tree::Branch(
 Box::new(Tree::Leaf(1)),
 Box::new(Tree::Leaf(2)),
);
each_leaf::<i32>().collect(&tree);             // [1, 2]
each_leaf::<i32>().modify(&|x| x + 10, &tree); // Branch(Leaf(11), Leaf(12))

// Step 4: Filtered Traversal — target only elements matching a predicate
fn filtered<T: Clone + 'static>(
 pred: impl Fn(&T) -> bool + Clone + 'static,
) -> Traversal<Vec<T>, T> {
 let p1 = pred.clone();
 let p2 = pred;
 Traversal {
     // over: apply f only to matching elements, pass others through unchanged
     over: Box::new(move |f, xs| {
         xs.iter().map(|x| if p1(x) { f(x) } else { x.clone() }).collect()
     }),
     // to_list: only include matching elements
     to_list: Box::new(move |xs| xs.iter().filter(|x| p2(x)).cloned().collect()),
 }
}

let evens = filtered(|x: &i32| x % 2 == 0);
evens.collect(&xs);              // [2, 4]
evens.modify(&|x| x * 10, &xs); // [1, 20, 3, 40, 5]  — odds unchanged

// Step 5: Generic combinators that work with any Traversal
fn sum_of(t: &Traversal<Vec<i32>, i32>, s: &Vec<i32>) -> i32 { t.collect(s).iter().sum() }
fn all_of<S, A>(t: &Traversal<S, A>, pred: impl Fn(&A) -> bool, s: &S) -> bool {
 t.collect(s).iter().all(|a| pred(a))
}

What This Unlocks

Optics composition — a Traversal is the "read-write" generalisation of both Lens and Prism. Any Lens or Prism can be treated as a degenerate Traversal. Understanding Traversal is the key to understanding the full optics hierarchy (example 211).
Sequence/traverse for `Option` and `Result` — `traverse_opt(xs, f)` applies `f: A → Option<B>` to every element and either returns `Some(Vec<B>)` or `None` (short-circuits on first failure). This pattern appears in every data validation pipeline.
Tree/graph walks — any recursive structure (AST nodes, directory trees, JSON values) can have a Traversal defined for it, enabling generic "apply transformation to all nodes of type X" without bespoke recursive functions.

Key Differences

Concept	OCaml	Rust
Traversal value	Record `{ over; to_list }` with polymorphic function types	`struct Traversal<S, A>` with `Box<dyn Fn>` trait objects
`over` function type	`('a -> 'a) -> 's -> 's` (polymorphic, curried)	`&dyn Fn(&A) -> A` — reference to trait object
Vec mapping	`List.map f xs`	`xs.iter().map(f).collect()`
Tree recursion	Pattern match, no boxing needed	Same pattern, but recursive types need `Box<Tree<T>>`
Filtered traversal	Predicate closure, no clone needed (GC)	Predicate must be `Clone` — stored in both `over` and `to_list` closures

// Example 208: Traversal — Focus on Zero or More Targets

// A traversal focuses on 0-to-many values inside a structure
struct Traversal<S, A> {
    over: Box<dyn Fn(&dyn Fn(&A) -> A, &S) -> S>,
    to_list: Box<dyn Fn(&S) -> Vec<A>>,
}

impl<S: 'static, A: 'static> Traversal<S, A> {
    fn new(
        over: impl Fn(&dyn Fn(&A) -> A, &S) -> S + 'static,
        to_list: impl Fn(&S) -> Vec<A> + 'static,
    ) -> Self {
        Traversal { over: Box::new(over), to_list: Box::new(to_list) }
    }

    fn modify(&self, f: &dyn Fn(&A) -> A, s: &S) -> S { (self.over)(f, s) }
    fn collect(&self, s: &S) -> Vec<A> { (self.to_list)(s) }
    fn length_of(&self, s: &S) -> usize { self.collect(s).len() }
}

// Approach 1: Traversal over Vec elements
fn each_traversal<T: Clone + 'static>() -> Traversal<Vec<T>, T> {
    Traversal::new(
        |f, xs| xs.iter().map(|x| f(x)).collect(),
        |xs| xs.clone(),
    )
}

// Approach 2: Traversal into a tree
#[derive(Debug, Clone, PartialEq)]
enum Tree<T> {
    Leaf(T),
    Branch(Box<Tree<T>>, Box<Tree<T>>),
}

fn each_leaf<T: Clone + 'static>() -> Traversal<Tree<T>, T> {
    fn over_tree<T: Clone>(f: &dyn Fn(&T) -> T, t: &Tree<T>) -> Tree<T> {
        match t {
            Tree::Leaf(x) => Tree::Leaf(f(x)),
            Tree::Branch(l, r) => Tree::Branch(
                Box::new(over_tree(f, l)),
                Box::new(over_tree(f, r)),
            ),
        }
    }
    fn to_list_tree<T: Clone>(t: &Tree<T>) -> Vec<T> {
        match t {
            Tree::Leaf(x) => vec![x.clone()],
            Tree::Branch(l, r) => {
                let mut v = to_list_tree(l);
                v.extend(to_list_tree(r));
                v
            }
        }
    }
    Traversal::new(over_tree, to_list_tree)
}

// Approach 3: Combinators
fn sum_of(t: &Traversal<Vec<i32>, i32>, s: &Vec<i32>) -> i32 {
    t.collect(s).iter().sum()
}

fn all_of<S, A>(t: &Traversal<S, A>, pred: impl Fn(&A) -> bool, s: &S) -> bool {
    t.collect(s).iter().all(|a| pred(a))
}

fn any_of<S, A>(t: &Traversal<S, A>, pred: impl Fn(&A) -> bool, s: &S) -> bool {
    t.collect(s).iter().any(|a| pred(a))
}

// Filtered traversal
fn filtered<T: Clone + 'static>(
    pred: impl Fn(&T) -> bool + Clone + 'static,
) -> Traversal<Vec<T>, T> {
    let p = pred.clone();
    let p2 = pred;
    Traversal::new(
        move |f, xs: &Vec<T>| xs.iter().map(|x| if p(x) { f(x) } else { x.clone() }).collect(),
        move |xs: &Vec<T>| xs.iter().filter(|x| p2(x)).cloned().collect(),
    )
}

fn main() {
    // List traversal
    let xs = vec![1, 2, 3, 4, 5];
    let t = each_traversal::<i32>();
    assert_eq!(t.collect(&xs), vec![1, 2, 3, 4, 5]);
    assert_eq!(t.modify(&|x| x * 2, &xs), vec![2, 4, 6, 8, 10]);
    assert_eq!(t.length_of(&xs), 5);
    assert_eq!(sum_of(&t, &xs), 15);

    // Tree traversal
    let tree = Tree::Branch(
        Box::new(Tree::Branch(Box::new(Tree::Leaf(1)), Box::new(Tree::Leaf(2)))),
        Box::new(Tree::Leaf(3)),
    );
    let tl = each_leaf::<i32>();
    assert_eq!(tl.collect(&tree), vec![1, 2, 3]);
    let tree2 = tl.modify(&|x| x + 10, &tree);
    assert_eq!(each_leaf::<i32>().collect(&tree2), vec![11, 12, 13]);

    // Filtered
    let evens = filtered(|x: &i32| x % 2 == 0);
    assert_eq!(evens.collect(&xs), vec![2, 4]);
    assert_eq!(evens.modify(&|x| x * 10, &xs), vec![1, 20, 3, 40, 5]);

    // Combinators
    assert!(all_of(&t, |x| *x > 0, &xs));
    assert!(any_of(&t, |x| *x == 3, &xs));

    println!("✓ All tests passed");
}

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

    #[test]
    fn test_vec_traversal() {
        let t = each_traversal::<i32>();
        let xs = vec![10, 20, 30];
        assert_eq!(t.modify(&|x| x + 1, &xs), vec![11, 21, 31]);
    }

    #[test]
    fn test_tree_traversal() {
        let t = each_leaf::<String>();
        let tree = Tree::Leaf("hello".to_string());
        assert_eq!(t.collect(&tree), vec!["hello".to_string()]);
    }

    #[test]
    fn test_filtered() {
        let f = filtered(|x: &i32| *x > 3);
        let xs = vec![1, 2, 3, 4, 5];
        assert_eq!(f.collect(&xs), vec![4, 5]);
    }

    #[test]
    fn test_length_of() {
        let t = each_traversal::<i32>();
        assert_eq!(t.length_of(&vec![1, 2, 3]), 3);
        assert_eq!(t.length_of(&vec![]), 0);
    }
}

(* Example 208: Traversal — Focus on Zero or More Targets *)

(* A traversal focuses on 0-to-many values inside a structure *)
type ('s, 'a) traversal = {
  over   : ('a -> 'a) -> 's -> 's;    (* modify all focused values *)
  to_list : 's -> 'a list;             (* collect all focused values *)
}

(* Approach 1: Traversal over list elements *)
let each_traversal : ('a list, 'a) traversal = {
  over = List.map;
  to_list = Fun.id;
}

(* Approach 2: Traversal into a tree structure *)
type 'a tree = Leaf of 'a | Branch of 'a tree * 'a tree

let rec tree_over f = function
  | Leaf x -> Leaf (f x)
  | Branch (l, r) -> Branch (tree_over f l, tree_over f r)

let rec tree_to_list = function
  | Leaf x -> [x]
  | Branch (l, r) -> tree_to_list l @ tree_to_list r

let each_leaf : ('a tree, 'a) traversal = {
  over = tree_over;
  to_list = tree_to_list;
}

(* Approach 3: Traversal combinators *)
let length_of t s = List.length (t.to_list s)
let sum_of t s = List.fold_left ( + ) 0 (t.to_list s)
let all_of t pred s = List.for_all pred (t.to_list s)
let any_of t pred s = List.exists pred (t.to_list s)
let find_of t pred s = List.find_opt pred (t.to_list s)

(* Filtered traversal *)
let filtered pred (t : ('s, 'a) traversal) : ('s, 'a) traversal = {
  over = (fun f s -> t.over (fun a -> if pred a then f a else a) s);
  to_list = (fun s -> List.filter pred (t.to_list s));
}

(* === Tests === *)
let () =
  (* List traversal *)
  let xs = [1; 2; 3; 4; 5] in
  assert (each_traversal.to_list xs = [1; 2; 3; 4; 5]);
  assert (each_traversal.over (fun x -> x * 2) xs = [2; 4; 6; 8; 10]);
  assert (length_of each_traversal xs = 5);
  assert (sum_of each_traversal xs = 15);

  (* Tree traversal *)
  let tree = Branch (Branch (Leaf 1, Leaf 2), Leaf 3) in
  assert (each_leaf.to_list tree = [1; 2; 3]);
  let tree2 = each_leaf.over (fun x -> x + 10) tree in
  assert (each_leaf.to_list tree2 = [11; 12; 13]);
  assert (sum_of each_leaf tree = 6);

  (* Filtered traversal *)
  let evens = filtered (fun x -> x mod 2 = 0) each_traversal in
  assert (evens.to_list xs = [2; 4]);
  let xs2 = evens.over (fun x -> x * 10) xs in
  assert (xs2 = [1; 20; 3; 40; 5]);

  (* Combinators *)
  assert (all_of each_traversal (fun x -> x > 0) xs);
  assert (not (all_of each_traversal (fun x -> x > 3) xs));
  assert (any_of each_traversal (fun x -> x = 3) xs);
  assert (find_of each_traversal (fun x -> x > 3) xs = Some 4);

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 208 — Traversal

Traversal Type

OCaml

🐪 Show OCaml equivalent

type ('s, 'a) traversal = {
over    : ('a -> 'a) -> 's -> 's;
to_list : 's -> 'a list;
}

Rust

struct Traversal<S, A> {
 over: Box<dyn Fn(&dyn Fn(&A) -> A, &S) -> S>,
 to_list: Box<dyn Fn(&S) -> Vec<A>>,
}

List Traversal

OCaml

🐪 Show OCaml equivalent

let each_traversal = {
over = List.map;
to_list = Fun.id;
}

Rust

fn each_traversal<T: Clone + 'static>() -> Traversal<Vec<T>, T> {
 Traversal::new(
     |f, xs| xs.iter().map(|x| f(x)).collect(),
     |xs| xs.clone(),
 )
}

Filtered Traversal

OCaml

🐪 Show OCaml equivalent

let filtered pred t = {
over = (fun f s -> t.over (fun a -> if pred a then f a else a) s);
to_list = (fun s -> List.filter pred (t.to_list s));
}

Rust

fn filtered<T: Clone + 'static>(pred: impl Fn(&T) -> bool + Clone + 'static) -> Traversal<Vec<T>, T> {
 let p = pred.clone();
 Traversal::new(
     move |f, xs| xs.iter().map(|x| if p(x) { f(x) } else { x.clone() }).collect(),
     move |xs| xs.iter().filter(|x| pred(x)).cloned().collect(),
 )
}

208: Traversal

The Problem This Solves

The Intuition

How It Works in Rust

What This Unlocks

Key Differences

📊 Detailed Comparison

Comparison: Example 208 — Traversal

Traversal Type

OCaml

Rust

List Traversal

OCaml

Rust

Filtered Traversal

OCaml

Rust

Related Examples