208 Advanced

Traversal — Focus on Zero or More Targets

Functional Programming

Tutorial

The Problem

A lens focuses on exactly one field; a prism focuses on at most one. A traversal focuses on zero or more values simultaneously. over_all(traversal, f, structure) applies f to every focused element and returns the updated structure. collect_all(traversal, structure) gathers all focused elements into a Vec. Traversals generalize map and fold to any structure: the same traversal that maps over Vec elements can map over tree nodes or nested struct fields.

🎯 Learning Outcomes

• Understand traversals as optics that focus on multiple values at once

• Implement over and collect as the two primitive traversal operations

• Derive higher-level operations (length_of, sum_of, all_of) from primitives

• See how traversals compose with lenses to focus deep inside complex structures

Code Example

type OverFn<S, A>    = Box<dyn Fn(&dyn Fn(&A) -> A, &S) -> S>;
type ToListFn<S, A>  = Box<dyn Fn(&S) -> Vec<A>>;

pub struct Traversal<S, A> {
    over_fn:    OverFn<S, A>,
    to_list_fn: ToListFn<S, A>,
}

impl<S: 'static, A: 'static> Traversal<S, A> {
    pub fn over(&self, f: impl Fn(&A) -> A, s: &S) -> S {
        (self.over_fn)(&f, s)
    }
    pub fn collect_all(&self, s: &S) -> Vec<A> { (self.to_list_fn)(s) }
    pub fn length_of(&self, s: &S) -> usize    { self.collect_all(s).len() }
    pub fn all_of(&self, s: &S, pred: impl Fn(&A) -> bool) -> bool {
        self.collect_all(s).iter().all(pred)
    }
}

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

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

(* Vec equivalent: traverse every list element *)
let each_traversal : ('a list, 'a) traversal = {
  over    = List.map;
  to_list = Fun.id;
}

(* Tree leaf traversal *)
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;
}

(* Derived operations — work with any traversal *)
let length_of trav s = List.length (trav.to_list s)
let sum_of    trav s = List.fold_left (+) 0 (trav.to_list s)
let all_of    trav s pred = List.for_all pred (trav.to_list s)

Key Differences

Over and collect: Both fundamental operations (over and to_list/collect) are identical in structure across languages.

Composition: Composing a lens with a traversal gives a traversal focused on the lens's target, then traversed; both languages handle this via function composition.

Applicative vs. explicit: Haskell/OCaml traversals use the Applicative functor for general traverse; Rust's version uses explicit over and collect — less general but clearer.

Derived operations: All aggregate operations (sum, count, any, all) are derived from collect — the traversal is a "lens for many targets."

OCaml Approach

OCaml's traversals use the Haskell-inspired Traversable typeclass:

module type TRAVERSAL = sig
  type s
  type a
  val over : (a -> a) -> s -> s
  val to_list : s -> a list
end

OCaml's List.map, Tree.map, and custom map implementations are all traversals. Haskell's traverse : Applicative f => (a -> f b) -> t a -> f (t b) is the general version — OCaml simulates this with functors.

Full Source

#![allow(clippy::all)]
// Example 208: Traversal — Focus on Zero or More Targets
//
// A Traversal generalises a Lens: instead of focusing on exactly one value
// inside `S`, it focuses on *zero or more* values of type `A`.
//
// Two primitive operations characterise a Traversal:
//   - `over`:    apply a function to every focused value, return updated `S`
//   - `collect`: gather every focused value into a `Vec<A>`
//
// Everything else — `length_of`, `all_of`, `any_of`, `sum_of` — is derived
// from those two primitives and works uniformly for *any* Traversal.

// ---------------------------------------------------------------------------
// Approach 1: Struct-based Traversal (mirrors the OCaml record directly)
// ---------------------------------------------------------------------------

type OverFn<S, A> = Box<dyn Fn(&dyn Fn(&A) -> A, &S) -> S>;
type ToListFn<S, A> = Box<dyn Fn(&S) -> Vec<A>>;

/// A Traversal that focuses on zero or more values of type `A` inside `S`.
pub struct Traversal<S, A> {
    over_fn: OverFn<S, A>,
    to_list_fn: ToListFn<S, A>,
}

impl<S: 'static, A: 'static> Traversal<S, A> {
    /// Build a Traversal from two functions.
    pub fn new(
        over: impl Fn(&dyn Fn(&A) -> A, &S) -> S + 'static,
        to_list: impl Fn(&S) -> Vec<A> + 'static,
    ) -> Self {
        Traversal {
            over_fn: Box::new(over),
            to_list_fn: Box::new(to_list),
        }
    }

    /// Apply `f` to every focused value, returning the updated structure.
    pub fn over(&self, f: impl Fn(&A) -> A, s: &S) -> S {
        (self.over_fn)(&f, s)
    }

    /// Collect all focused values into a `Vec`.
    pub fn collect_all(&self, s: &S) -> Vec<A> {
        (self.to_list_fn)(s)
    }

    /// Count how many values are focused.
    pub fn length_of(&self, s: &S) -> usize {
        self.collect_all(s).len()
    }

    /// `true` iff every focused value satisfies `pred`.
    pub fn all_of(&self, s: &S, pred: impl Fn(&A) -> bool) -> bool {
        self.collect_all(s).iter().all(pred)
    }

    /// `true` iff at least one focused value satisfies `pred`.
    pub fn any_of(&self, s: &S, pred: impl Fn(&A) -> bool) -> bool {
        self.collect_all(s).iter().any(pred)
    }
}

// ---------------------------------------------------------------------------
// Traversal over every element of a Vec
// ---------------------------------------------------------------------------

/// Traversal that focuses on every element of a `Vec<T>`.
///
/// OCaml equivalent:
/// ```ocaml
/// let each_traversal = { over = List.map; to_list = Fun.id }
/// ```
pub fn each_traversal<T: Clone + 'static>() -> Traversal<Vec<T>, T> {
    Traversal::new(
        |f, v: &Vec<T>| v.iter().map(f).collect(),
        |v: &Vec<T>| v.clone(),
    )
}

// ---------------------------------------------------------------------------
// Binary tree + leaf traversal
// ---------------------------------------------------------------------------

/// A simple binary tree whose leaves hold values of type `A`.
#[derive(Debug, Clone, PartialEq)]
pub enum Tree<A> {
    Leaf(A),
    Branch(Box<Tree<A>>, Box<Tree<A>>),
}

fn tree_map<T>(f: &dyn Fn(&T) -> T, tree: &Tree<T>) -> Tree<T> {
    match tree {
        Tree::Leaf(x) => Tree::Leaf(f(x)),
        Tree::Branch(l, r) => Tree::Branch(Box::new(tree_map(f, l)), Box::new(tree_map(f, r))),
    }
}

fn tree_to_list<T: Clone>(tree: &Tree<T>) -> Vec<T> {
    match tree {
        Tree::Leaf(x) => vec![x.clone()],
        Tree::Branch(l, r) => tree_to_list(l).into_iter().chain(tree_to_list(r)).collect(),
    }
}

/// Traversal that focuses on every leaf of a `Tree<T>`.
///
/// OCaml equivalent:
/// ```ocaml
/// let each_leaf = { over = tree_over; to_list = tree_to_list }
/// ```
pub fn each_leaf_traversal<T: Clone + 'static>() -> Traversal<Tree<T>, T> {
    Traversal::new(tree_map, tree_to_list)
}

// ---------------------------------------------------------------------------
// Approach 2: Trait-based Traversal (compile-time dispatch, no allocations)
// ---------------------------------------------------------------------------

/// Implement this trait on any container to get traversal operations for free.
pub trait TraversableExt<A> {
    /// Apply `f` to every focused value, consuming and returning the structure.
    fn over_all(self, f: &impl Fn(A) -> A) -> Self;

    /// Collect all focused values by clone.
    fn collect_targets(&self) -> Vec<A>
    where
        A: Clone;
}

impl<A> TraversableExt<A> for Vec<A> {
    fn over_all(self, f: &impl Fn(A) -> A) -> Self {
        self.into_iter().map(f).collect()
    }

    fn collect_targets(&self) -> Vec<A>
    where
        A: Clone,
    {
        self.clone()
    }
}

fn tree_over_owned<A>(tree: Tree<A>, f: &impl Fn(A) -> A) -> Tree<A> {
    match tree {
        Tree::Leaf(x) => Tree::Leaf(f(x)),
        Tree::Branch(l, r) => Tree::Branch(
            Box::new(tree_over_owned(*l, f)),
            Box::new(tree_over_owned(*r, f)),
        ),
    }
}

impl<A: Clone> TraversableExt<A> for Tree<A> {
    fn over_all(self, f: &impl Fn(A) -> A) -> Self {
        tree_over_owned(self, f)
    }

    fn collect_targets(&self) -> Vec<A> {
        tree_to_list(self)
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

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

    // ── Vec traversal (struct-based) ──────────────────────────────────────

    #[test]
    fn test_each_over_doubles_all_elements() {
        let trav = each_traversal::<i32>();
        let result = trav.over(|x| x * 2, &vec![1, 2, 3, 4]);
        assert_eq!(result, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_each_over_empty_vec_is_empty() {
        let trav = each_traversal::<i32>();
        let result = trav.over(|x| x * 2, &vec![]);
        assert_eq!(result, vec![]);
    }

    #[test]
    fn test_each_collect_all_returns_elements() {
        let trav = each_traversal::<i32>();
        assert_eq!(trav.collect_all(&vec![10, 20, 30]), vec![10, 20, 30]);
    }

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

    #[test]
    fn test_each_all_of_even_numbers() {
        let trav = each_traversal::<i32>();
        assert!(trav.all_of(&vec![2, 4, 6], |x| x % 2 == 0));
        assert!(!trav.all_of(&vec![2, 3, 6], |x| x % 2 == 0));
    }

    #[test]
    fn test_each_any_of_finds_even() {
        let trav = each_traversal::<i32>();
        assert!(trav.any_of(&vec![1, 3, 4], |x| x % 2 == 0));
        assert!(!trav.any_of(&vec![1, 3, 5], |x| x % 2 == 0));
    }

    // ── Tree leaf traversal (struct-based) ───────────────────────────────

    /// Builds: Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
    fn sample_tree() -> Tree<i32> {
        Tree::Branch(
            Box::new(Tree::Leaf(1)),
            Box::new(Tree::Branch(
                Box::new(Tree::Leaf(2)),
                Box::new(Tree::Leaf(3)),
            )),
        )
    }

    #[test]
    fn test_tree_over_doubles_all_leaves() {
        let trav = each_leaf_traversal::<i32>();
        let result = trav.over(|x| x * 2, &sample_tree());
        assert_eq!(
            result,
            Tree::Branch(
                Box::new(Tree::Leaf(2)),
                Box::new(Tree::Branch(
                    Box::new(Tree::Leaf(4)),
                    Box::new(Tree::Leaf(6)),
                )),
            )
        );
    }

    #[test]
    fn test_tree_collect_all_leaves_in_order() {
        let trav = each_leaf_traversal::<i32>();
        assert_eq!(trav.collect_all(&sample_tree()), vec![1, 2, 3]);
    }

    #[test]
    fn test_tree_length_of_counts_leaves() {
        let trav = each_leaf_traversal::<i32>();
        assert_eq!(trav.length_of(&sample_tree()), 3);
        assert_eq!(trav.length_of(&Tree::Leaf(42)), 1);
    }

    #[test]
    fn test_tree_single_leaf_over_and_collect() {
        let trav = each_leaf_traversal::<i32>();
        let t = Tree::Leaf(5);
        assert_eq!(trav.over(|x| x + 10, &t), Tree::Leaf(15));
        assert_eq!(trav.collect_all(&t), vec![5]);
    }

    // ── Trait-based traversal ─────────────────────────────────────────────

    #[test]
    fn test_trait_vec_over_all_triples() {
        let result = vec![1, 2, 3].over_all(&|x| x * 3);
        assert_eq!(result, vec![3, 6, 9]);
    }

    #[test]
    fn test_trait_vec_collect_targets_clones() {
        let v = vec![7, 8, 9];
        assert_eq!(v.collect_targets(), vec![7, 8, 9]);
    }

    #[test]
    fn test_trait_tree_over_all_adds_ten() {
        let t = Tree::Branch(Box::new(Tree::Leaf(1)), Box::new(Tree::Leaf(2)));
        let result = t.over_all(&|x| x + 10);
        assert_eq!(
            result,
            Tree::Branch(Box::new(Tree::Leaf(11)), Box::new(Tree::Leaf(12)))
        );
    }

    #[test]
    fn test_trait_tree_collect_targets_matches_leaves() {
        assert_eq!(sample_tree().collect_targets(), vec![1, 2, 3]);
    }
}

(* 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"

✓ Tests Rust test suite

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

    // ── Vec traversal (struct-based) ──────────────────────────────────────

    #[test]
    fn test_each_over_doubles_all_elements() {
        let trav = each_traversal::<i32>();
        let result = trav.over(|x| x * 2, &vec![1, 2, 3, 4]);
        assert_eq!(result, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_each_over_empty_vec_is_empty() {
        let trav = each_traversal::<i32>();
        let result = trav.over(|x| x * 2, &vec![]);
        assert_eq!(result, vec![]);
    }

    #[test]
    fn test_each_collect_all_returns_elements() {
        let trav = each_traversal::<i32>();
        assert_eq!(trav.collect_all(&vec![10, 20, 30]), vec![10, 20, 30]);
    }

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

    #[test]
    fn test_each_all_of_even_numbers() {
        let trav = each_traversal::<i32>();
        assert!(trav.all_of(&vec![2, 4, 6], |x| x % 2 == 0));
        assert!(!trav.all_of(&vec![2, 3, 6], |x| x % 2 == 0));
    }

    #[test]
    fn test_each_any_of_finds_even() {
        let trav = each_traversal::<i32>();
        assert!(trav.any_of(&vec![1, 3, 4], |x| x % 2 == 0));
        assert!(!trav.any_of(&vec![1, 3, 5], |x| x % 2 == 0));
    }

    // ── Tree leaf traversal (struct-based) ───────────────────────────────

    /// Builds: Branch(Leaf(1), Branch(Leaf(2), Leaf(3)))
    fn sample_tree() -> Tree<i32> {
        Tree::Branch(
            Box::new(Tree::Leaf(1)),
            Box::new(Tree::Branch(
                Box::new(Tree::Leaf(2)),
                Box::new(Tree::Leaf(3)),
            )),
        )
    }

    #[test]
    fn test_tree_over_doubles_all_leaves() {
        let trav = each_leaf_traversal::<i32>();
        let result = trav.over(|x| x * 2, &sample_tree());
        assert_eq!(
            result,
            Tree::Branch(
                Box::new(Tree::Leaf(2)),
                Box::new(Tree::Branch(
                    Box::new(Tree::Leaf(4)),
                    Box::new(Tree::Leaf(6)),
                )),
            )
        );
    }

    #[test]
    fn test_tree_collect_all_leaves_in_order() {
        let trav = each_leaf_traversal::<i32>();
        assert_eq!(trav.collect_all(&sample_tree()), vec![1, 2, 3]);
    }

    #[test]
    fn test_tree_length_of_counts_leaves() {
        let trav = each_leaf_traversal::<i32>();
        assert_eq!(trav.length_of(&sample_tree()), 3);
        assert_eq!(trav.length_of(&Tree::Leaf(42)), 1);
    }

    #[test]
    fn test_tree_single_leaf_over_and_collect() {
        let trav = each_leaf_traversal::<i32>();
        let t = Tree::Leaf(5);
        assert_eq!(trav.over(|x| x + 10, &t), Tree::Leaf(15));
        assert_eq!(trav.collect_all(&t), vec![5]);
    }

    // ── Trait-based traversal ─────────────────────────────────────────────

    #[test]
    fn test_trait_vec_over_all_triples() {
        let result = vec![1, 2, 3].over_all(&|x| x * 3);
        assert_eq!(result, vec![3, 6, 9]);
    }

    #[test]
    fn test_trait_vec_collect_targets_clones() {
        let v = vec![7, 8, 9];
        assert_eq!(v.collect_targets(), vec![7, 8, 9]);
    }

    #[test]
    fn test_trait_tree_over_all_adds_ten() {
        let t = Tree::Branch(Box::new(Tree::Leaf(1)), Box::new(Tree::Leaf(2)));
        let result = t.over_all(&|x| x + 10);
        assert_eq!(
            result,
            Tree::Branch(Box::new(Tree::Leaf(11)), Box::new(Tree::Leaf(12)))
        );
    }

    #[test]
    fn test_trait_tree_collect_targets_matches_leaves() {
        assert_eq!(sample_tree().collect_targets(), vec![1, 2, 3]);
    }
}

Deep Comparison

OCaml vs Rust: Traversal

Side-by-Side Code

OCaml

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

(* Vec equivalent: traverse every list element *)
let each_traversal : ('a list, 'a) traversal = {
  over    = List.map;
  to_list = Fun.id;
}

(* Tree leaf traversal *)
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;
}

(* Derived operations — work with any traversal *)
let length_of trav s = List.length (trav.to_list s)
let sum_of    trav s = List.fold_left (+) 0 (trav.to_list s)
let all_of    trav s pred = List.for_all pred (trav.to_list s)

Rust (idiomatic — struct with boxed closures)

type OverFn<S, A>    = Box<dyn Fn(&dyn Fn(&A) -> A, &S) -> S>;
type ToListFn<S, A>  = Box<dyn Fn(&S) -> Vec<A>>;

pub struct Traversal<S, A> {
    over_fn:    OverFn<S, A>,
    to_list_fn: ToListFn<S, A>,
}

impl<S: 'static, A: 'static> Traversal<S, A> {
    pub fn over(&self, f: impl Fn(&A) -> A, s: &S) -> S {
        (self.over_fn)(&f, s)
    }
    pub fn collect_all(&self, s: &S) -> Vec<A> { (self.to_list_fn)(s) }
    pub fn length_of(&self, s: &S) -> usize    { self.collect_all(s).len() }
    pub fn all_of(&self, s: &S, pred: impl Fn(&A) -> bool) -> bool {
        self.collect_all(s).iter().all(pred)
    }
}

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

Rust (functional/recursive — trait-based, zero allocation)

pub trait TraversableExt<A> {
    fn over_all(self, f: &impl Fn(A) -> A) -> Self;
    fn collect_targets(&self) -> Vec<A> where A: Clone;
}

impl<A> TraversableExt<A> for Vec<A> {
    fn over_all(self, f: &impl Fn(A) -> A) -> Self {
        self.into_iter().map(f).collect()
    }
    fn collect_targets(&self) -> Vec<A> where A: Clone { self.clone() }
}

fn tree_over_owned<A>(tree: Tree<A>, f: &impl Fn(A) -> A) -> Tree<A> {
    match tree {
        Tree::Leaf(x)        => Tree::Leaf(f(x)),
        Tree::Branch(l, r)   => Tree::Branch(
            Box::new(tree_over_owned(*l, f)),
            Box::new(tree_over_owned(*r, f)),
        ),
    }
}

impl<A: Clone> TraversableExt<A> for Tree<A> {
    fn over_all(self, f: &impl Fn(A) -> A) -> Self { tree_over_owned(self, f) }
    fn collect_targets(&self) -> Vec<A>             { tree_to_list(self) }
}

Type Signatures

Concept	OCaml	Rust
Traversal type	`('s, 'a) traversal` (record)	`Traversal<S, A>` (struct)
`over`	`('a -> 'a) -> 's -> 's`	`Fn(&A) -> A, &S) -> S`
`to_list`	`'s -> 'a list`	`Fn(&S) -> Vec<A>`
Polymorphic traversal	Type variable `'a`	Generic `<T>` with `'static` bound
Recursive tree walk	Pattern-matching `function`	`match` with `Box::new` for heap nodes
Trait-based approach	N/A (module functors)	`TraversableExt<A>` trait

Key Insights

Records vs structs: OCaml's record { over; to_list } maps naturally to a Rust struct. Rust needs boxed closures (Box<dyn Fn(...)>) where OCaml uses higher-order functions directly, because Rust's closures are unnameable types.

**Lifetime and 'static bounds**: Rust requires S: 'static and A: 'static when storing closures in a Box<dyn Fn(...)>, since the trait object must outlive the references it captures. OCaml's GC handles object lifetimes transparently.

Two dispatch strategies: The struct-based approach uses runtime dispatch (dyn Fn) — flexible, heap-allocated. The trait-based approach (TraversableExt) uses compile-time dispatch — zero overhead, but each container type must implement the trait manually. OCaml's functor system offers a third alternative unavailable in Rust.

Recursive trees and ownership: OCaml's Branch of 'a tree * 'a tree stores sub-trees inline. Rust must use Box<Tree<A>> to give recursive types a known size. Modifying an owned tree recursively requires consuming it (the tree_over_owned helper takes Tree<A> by value and returns a new one), matching the immutable-update style of OCaml exactly.

Derived operations are universal: length_of, all_of, any_of are defined once in terms of collect_all and work for any Traversal<S, A> or any TraversableExt instance — the same composability that makes OCaml's traversal abstraction powerful applies equally in Rust.

When to Use Each Style

**Use struct-based Traversal<S, A> when:** you want to pass traversals as first-class values, store them in collections, or build combinators (e.g., compose, filtered) at runtime — matching the OCaml idiom most closely.

**Use trait-based TraversableExt<A> when:** performance matters, the set of traversable types is known at compile time, and you want zero-cost abstraction without heap allocation or runtime dispatch.

Exercises

Implement a traversal for tree leaves and verify sum_of and length_of work correctly.

Write modify_at(traversal, index, f, s) that applies f only to the element at a specific index.

Compose a lens and a traversal: a lens that focuses on a Vec<i32> field, composed with a traversal for the vec's elements.

Open Source Repos

functional-rust

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

Rust