618: Traversal for Collection Optics

The Problem This Solves

let mut results = Vec::new();
let mut failed = false;
for s in &strs {
 match s.parse::<i32>() {
     Ok(n)  => results.push(n),
     Err(_) => { failed = true; break; }
 }
}
if failed { return None; }
// results is Vec<i32> if we made it here

let parsed: Vec<Option<i32>> = strs.iter().map(|s| s.parse().ok()).collect();
// Now you have Vec<Option<i32>> — you need to flip it to Option<Vec<i32>>
// How? Another pass, more boilerplate
let result: Option<Vec<i32>> = if parsed.iter().all(|x| x.is_some()) {
 Some(parsed.into_iter().map(|x| x.unwrap()).collect())
} else {
 None
};

The Intuition

• `traverse` with `Option`: `Vec<A>` + `fn(A) → Option<B>` → `Option<Vec<B>>`

• `traverse` with `Result`: `Vec<A>` + `fn(A) → Result<B, E>` → `Result<Vec<B>, E>`

Vec<A>  +  fn(A) -> Option<B>
    ↓ traverse
Option<Vec<B>>    ← Some([b1, b2, b3]) or None on first failure

How It Works in Rust

// Step 1: The fundamental traverse operation — Option effect
fn traverse_opt<A, B>(xs: Vec<A>, f: impl Fn(A) -> Option<B>) -> Option<Vec<B>> {
 xs.into_iter()
     .map(f)              // Iterator<Item = Option<B>>
     .collect()           // collect() on Iterator<Item=Option<B>> into Option<Vec<B>>
                          // ← this is the key: collect() knows to short-circuit!
}

// Works because Rust's FromIterator for Option short-circuits on None
traverse_opt(vec!["1", "2", "3"], |s| s.parse::<i32>().ok());  // Some([1, 2, 3])
traverse_opt(vec!["1", "x", "3"], |s| s.parse::<i32>().ok());  // None — "x" fails

// Step 2: Same pattern for Result — get an error message instead of None
fn traverse_result<A, B, E>(xs: Vec<A>, f: impl Fn(A) -> Result<B, E>) -> Result<Vec<B>, E> {
 xs.into_iter().map(f).collect()  // Same trick! collect() short-circuits on Err
}

// Returns first error encountered:
traverse_result(["1.5", "abc"].to_vec(), |s| {
 s.parse::<f64>().map_err(|_| format!("bad float: {}", s))
});  // Err("bad float: abc")

// Step 3: Traverse a nested structure (matrix)
fn traverse_matrix<A: Clone, B>(
 m: Vec<Vec<A>>,
 f: impl Fn(A) -> Option<B> + Clone,
) -> Option<Vec<Vec<B>>> {
 // outer traverse: for each row, inner traverse: for each element
 traverse_opt(m, |row| traverse_opt(row, f.clone()))
 // If any element in any row fails → None for the whole matrix
}

let matrix = vec![vec!["1", "2"], vec!["3", "4"]];
traverse_matrix(matrix, |s| s.parse::<i32>().ok());
// Some([[1, 2], [3, 4]])

// Step 4: Traversal as filter_map — "Prism traversal"
// Collect only the values that match a pattern (like a Prism over a collection)
fn collect_values<A: Clone, B>(xs: &[A], prism: impl Fn(&A) -> Option<B>) -> Vec<B> {
 xs.iter().filter_map(prism).collect()
 // Different from traverse_opt: here None means "skip this element", not "fail"
}

enum Json { Num(f64), Str(String), Null }
let jsons = vec![Json::Num(1.0), Json::Str("hi".into()), Json::Num(2.0), Json::Null];
let nums = collect_values(&jsons, |j| match j { Json::Num(n) => Some(*n), _ => None });
// [1.0, 2.0] — strings and nulls filtered out

// Step 5: Traverse nested Option<Vec<A>>
fn traverse_nested<A, B>(opt: Option<Vec<A>>, f: impl Fn(A) -> Option<B>) -> Option<Vec<B>> {
 opt.and_then(|xs| traverse_opt(xs, f))
 // None input → None output
 // Some(xs) → traverse xs → Option<Vec<B>>
}

What This Unlocks

• Data validation pipelines — parse and validate every field in a batch of records: `traverse_result(records, validate)` gives you either all-valid data or the first error, without manual error-accumulation code.
• API response handling — deserialising a `Vec<RawJson>` into `Vec<ParsedItem>` is exactly traversal: `traverse_opt(raw_items, parse_item)`. One `None` means "malformed response."
• The `Option<Vec<T>>` ↔ `Vec<Option<T>>` flip — knowing that `collect::<Option<Vec<T>>>()` does the flip explains a class of iterator patterns that are otherwise confusing.

Key Differences