Traverse with Option
Functional Programming
Tutorial
The Problem
Given a list and a function that might fail for each element, how do you apply the function to all elements and either get all results or fail at the first problem? map produces Vec<Option<U>> — a list of maybes. traverse flips this to Option<Vec<U>> — either all succeeded or the whole thing failed. This is the "all or nothing" pattern: validate a batch of inputs, parse a list of strings, look up a list of keys — succeed if all succeed, fail on first problem. Rust achieves this via Iterator::collect::<Option<Vec<T>>>(), which is traverse for Option built into the language.
🎯 Learning Outcomes
[T] -> (T -> Option<U>) -> Option<[U]]xs.iter().map(f).collect::<Option<Vec<U>>>() is traverse in RustVec<Option<U>> → Option<Vec<U>>Code Example
fn traverse_option<T, U, F: Fn(&T) -> Option<U>>(xs: &[T], f: F) -> Option<Vec<U>> {
xs.iter().map(f).collect() // That's it!
}Key Differences
| Aspect | Rust | OCaml |
|---|---|---|
| Idiomatic traverse | .collect::<Option<Vec<_>>>() | List.fold_right or filter_map |
| Short-circuit | Automatic via collect | Manual with None arm |
| Manual version | try_fold with ? | List.fold_right |
| Order | Left-to-right (iter) | Right-fold builds correct order |
| Drop failures | filter_map | List.filter_map |
| Type signature | Option<Vec<U>> | 'u list option |
OCaml Approach
OCaml's traverse for option: let traverse f xs = List.fold_right (fun x acc -> match f x, acc with Some y, Some ys -> Some (y :: ys) | _ -> None) xs (Some []). The right fold ensures left-to-right evaluation order with a right-to-left accumulation — produces the correct order. List.filter_map is traverse that drops failures rather than short-circuiting. OCaml's Option.bind inside a fold naturally implements the early-exit behavior.
Full Source
#![allow(clippy::all)]
// Example 064: Traverse with Option
// Apply a function returning Option to each element, collecting all or nothing
// Approach 1: Using Iterator::collect (Rust's built-in traverse!)
fn traverse_option<T, U, F: Fn(&T) -> Option<U>>(xs: &[T], f: F) -> Option<Vec<U>> {
xs.iter().map(f).collect()
// collect::<Option<Vec<U>>>() is Rust's traverse!
}
// Approach 2: Manual fold implementation
fn traverse_option_fold<T, U, F: Fn(&T) -> Option<U>>(xs: &[T], f: F) -> Option<Vec<U>> {
xs.iter().try_fold(Vec::new(), |mut acc, x| {
let y = f(x)?;
acc.push(y);
Some(acc)
})
}
// Approach 3: Sequence — traverse with identity
fn sequence_option<T: Clone>(xs: &[Option<T>]) -> Option<Vec<T>> {
xs.iter().cloned().collect()
}
fn safe_div10(x: &i32) -> Option<i32> {
if *x == 0 {
None
} else {
Some(10 / x)
}
}
fn parse_int(s: &&str) -> Option<i32> {
s.parse().ok()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_traverse_all_succeed() {
assert_eq!(
traverse_option(&[2, 5, 1], safe_div10),
Some(vec![5, 2, 10])
);
}
#[test]
fn test_traverse_one_fails() {
assert_eq!(traverse_option(&[2, 0, 1], safe_div10), None);
}
#[test]
fn test_traverse_empty() {
assert_eq!(traverse_option(&[], safe_div10), Some(vec![]));
}
#[test]
fn test_fold_version() {
assert_eq!(
traverse_option_fold(&[2, 5, 1], safe_div10),
Some(vec![5, 2, 10])
);
assert_eq!(traverse_option_fold(&[2, 0, 1], safe_div10), None);
}
#[test]
fn test_parse_strings() {
let strs = ["1", "2", "3"];
assert_eq!(traverse_option(&strs, parse_int), Some(vec![1, 2, 3]));
let strs2 = ["1", "bad", "3"];
assert_eq!(traverse_option(&strs2, parse_int), None);
}
#[test]
fn test_sequence() {
assert_eq!(
sequence_option(&[Some(1), Some(2), Some(3)]),
Some(vec![1, 2, 3])
);
assert_eq!(sequence_option(&[Some(1), None, Some(3)]), None);
}
#[test]
fn test_collect_is_traverse() {
// Rust's collect() on Iterator<Item=Option<T>> IS traverse!
let result: Option<Vec<i32>> = vec![Some(1), Some(2), Some(3)].into_iter().collect();
assert_eq!(result, Some(vec![1, 2, 3]));
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_traverse_all_succeed() {
assert_eq!(
traverse_option(&[2, 5, 1], safe_div10),
Some(vec![5, 2, 10])
);
}
#[test]
fn test_traverse_one_fails() {
assert_eq!(traverse_option(&[2, 0, 1], safe_div10), None);
}
#[test]
fn test_traverse_empty() {
assert_eq!(traverse_option(&[], safe_div10), Some(vec![]));
}
#[test]
fn test_fold_version() {
assert_eq!(
traverse_option_fold(&[2, 5, 1], safe_div10),
Some(vec![5, 2, 10])
);
assert_eq!(traverse_option_fold(&[2, 0, 1], safe_div10), None);
}
#[test]
fn test_parse_strings() {
let strs = ["1", "2", "3"];
assert_eq!(traverse_option(&strs, parse_int), Some(vec![1, 2, 3]));
let strs2 = ["1", "bad", "3"];
assert_eq!(traverse_option(&strs2, parse_int), None);
}
#[test]
fn test_sequence() {
assert_eq!(
sequence_option(&[Some(1), Some(2), Some(3)]),
Some(vec![1, 2, 3])
);
assert_eq!(sequence_option(&[Some(1), None, Some(3)]), None);
}
#[test]
fn test_collect_is_traverse() {
// Rust's collect() on Iterator<Item=Option<T>> IS traverse!
let result: Option<Vec<i32>> = vec![Some(1), Some(2), Some(3)].into_iter().collect();
assert_eq!(result, Some(vec![1, 2, 3]));
}
}Deep Comparison
Comparison: Traverse with Option
Traverse
OCaml:
let rec traverse_option f = function
| [] -> Some []
| x :: xs ->
match f x with
| None -> None
| Some y ->
match traverse_option f xs with
| None -> None
| Some ys -> Some (y :: ys)
Rust (built-in via collect!):
fn traverse_option<T, U, F: Fn(&T) -> Option<U>>(xs: &[T], f: F) -> Option<Vec<U>> {
xs.iter().map(f).collect() // That's it!
}
Sequence
OCaml:
let sequence_option xs = traverse_option Fun.id xs
(* [Some 1; Some 2; Some 3] → Some [1; 2; 3] *)
Rust:
fn sequence_option<T: Clone>(xs: &[Option<T>]) -> Option<Vec<T>> {
xs.iter().cloned().collect()
}
Fold-Based Traverse
OCaml:
let traverse_option_fold f xs =
List.fold_right (fun x acc ->
match f x, acc with
| Some y, Some ys -> Some (y :: ys)
| _ -> None
) xs (Some [])
Rust:
fn traverse_option_fold<T, U, F: Fn(&T) -> Option<U>>(xs: &[T], f: F) -> Option<Vec<U>> {
xs.iter().try_fold(Vec::new(), |mut acc, x| {
acc.push(f(x)?);
Some(acc)
})
}
Exercises
traverse_option to parse a Vec<&str> of integers, returning None if any string fails to parse.traverse_option using explicit and_then chains and verify it matches collect.traverse_option that reports the first failing element along with its index.filter_map: show that traverse fails on None while filter_map skips None.