🎬 How Rust Iterators Work Lazy evaluation, chaining, collect(), and zero-cost abstractions.

📝 Text version (for readers / accessibility)

• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed

• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection

• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops

• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably

• Chaining replaces nested loops with a readable, composable pipeline

098: Partition Iterator

Difficulty: 3 Level: Intermediate Split a collection into two groups by a predicate — evens/odds, valid/invalid, successes/failures.

The Problem This Solves

You have a mixed collection and need to separate it into two groups without traversing it twice. Classic examples: split a list of parse results into successes and errors, separate positive from negative numbers, classify events into handled and unhandled. Writing two separate `.filter()` calls is intuitive but wasteful — two full passes, two allocations. `.partition()` does both in a single pass, building both output collections simultaneously. For multi-way classification (more than two groups), `.partition()` isn't enough. But the same single-pass pattern extends naturally to `match` branches or a manual fold.

The Intuition

Think of `.partition()` as two `.filter()` calls fused into one. The predicate routes each element: `true` → first collection, `false` → second collection. Both collections are built in one pass, in original order. Python's equivalent is a comprehension pattern: `trues = [x for x in data if pred(x)]` + `falses = [x for x in data if not pred(x)]` — two passes. Rust's `.partition()` is one. The return type is generic: `(B, B) where B: Default + Extend<Item>`. In practice this almost always means `(Vec<T>, Vec<T>)`.

How It Works in Rust

// Binary partition: even vs odd
fn split_even_odd(data: &[i32]) -> (Vec<i32>, Vec<i32>) {
 data.iter().partition(|&&x| x % 2 == 0)
 // → (evens, odds)
}

// Multi-way classification: use a loop for 3+ categories
fn classify_numbers(data: &[i32]) -> (Vec<i32>, Vec<i32>, Vec<i32>) {
 let mut negative = Vec::new();
 let mut zero = Vec::new();
 let mut positive = Vec::new();
 for &x in data {
     match x.cmp(&0) {
         std::cmp::Ordering::Less    => negative.push(x),
         std::cmp::Ordering::Equal   => zero.push(x),
         std::cmp::Ordering::Greater => positive.push(x),
     }
 }
 (negative, zero, positive)
}

// Partition Results: separate Ok and Err in one pass
fn partition_results(data: &[&str]) -> (Vec<i32>, Vec<String>) {
 let mut oks = Vec::new();
 let mut errs = Vec::new();
 for &s in data {
     match s.parse::<i32>() {
         Ok(n)  => oks.push(n),
         Err(e) => errs.push(format!("{}: {}", s, e)),
     }
 }
 (oks, errs)
}

// Split at first match: keep before + after the split point
fn split_at_first(data: &[i32], pred: impl Fn(&i32) -> bool) -> (&[i32], &[i32]) {
 match data.iter().position(|x| pred(x)) {
     Some(i) => (&data[..i], &data[i..]),
     None    => (data, &[]),
 }
}

What This Unlocks

Error handling pipelines: collect all parse errors to display, proceed with valid values.
Routing: partition incoming events by type, process each group with specialized logic.
Data cleaning: separate well-formed records from malformed ones in a single scan.

Key Differences

Concept	OCaml	Rust
Binary split	`List.partition pred`	`.partition(pred)`
Return type	`('a list * 'a list)`	`(B, B) where B: Default + Extend`
Multi-way	`fold_left` with accumulator	Manual `match` loop
With transformation	`partition_map` (external)	Manual `match` loop
Split at position	Manual recursion	`.position()` + slice indexing

// Example 098: Partition Iterator
// Split into two collections by predicate

// === Approach 1: Basic partition ===
fn split_even_odd(data: &[i32]) -> (Vec<i32>, Vec<i32>) {
    data.iter().partition(|&&x| x % 2 == 0)
}

fn split_positive(data: &[i32]) -> (Vec<&i32>, Vec<&i32>) {
    data.iter().partition(|&&x| x > 0)
}

// === Approach 2: Multi-way partition ===
fn partition3<T>(data: &[T], p1: impl Fn(&T) -> bool, p2: impl Fn(&T) -> bool) -> (Vec<&T>, Vec<&T>, Vec<&T>) {
    let mut a = Vec::new();
    let mut b = Vec::new();
    let mut c = Vec::new();
    for item in data {
        if p1(item) { a.push(item); }
        else if p2(item) { b.push(item); }
        else { c.push(item); }
    }
    (a, b, c)
}

fn classify_numbers(data: &[i32]) -> (Vec<&i32>, Vec<&i32>, Vec<&i32>) {
    partition3(data, |&&x| x < 0, |&&x| x == 0)
}

// === Approach 3: Partition with transformation ===
fn partition_results(data: &[&str]) -> (Vec<i32>, Vec<String>) {
    let mut oks = Vec::new();
    let mut errs = Vec::new();
    for &s in data {
        match s.parse::<i32>() {
            Ok(n) => oks.push(n),
            Err(e) => errs.push(format!("{}: {}", s, e)),
        }
    }
    (oks, errs)
}

fn validate_ages(ages: &[i32]) -> (Vec<i32>, Vec<i32>) {
    ages.iter().partition(|&&a| (0..=150).contains(&a))
}

// split_at equivalent
fn split_at_first<T>(data: &[T], pred: impl Fn(&T) -> bool) -> (&[T], &[T]) {
    match data.iter().position(|x| pred(x)) {
        Some(pos) => (&data[..pos], &data[pos..]),
        None => (data, &[]),
    }
}

// Partition into HashMap buckets
use std::collections::HashMap;

fn bucket_by<T, K: std::hash::Hash + Eq>(data: &[T], key: impl Fn(&T) -> K) -> HashMap<K, Vec<&T>> {
    let mut map: HashMap<K, Vec<&T>> = HashMap::new();
    for item in data {
        map.entry(key(item)).or_default().push(item);
    }
    map
}

fn main() {
    let (evens, odds) = split_even_odd(&[1,2,3,4,5,6]);
    println!("Evens: {:?}, Odds: {:?}", evens, odds);

    let (neg, zero, pos) = classify_numbers(&[-2, 0, 3, -1, 0, 5]);
    println!("Neg: {:?}, Zero: {:?}, Pos: {:?}", neg, zero, pos);

    let (oks, errs) = partition_results(&["1", "abc", "3", "xyz"]);
    println!("Parsed: {:?}, Errors: {:?}", oks, errs);

    let (before, after) = split_at_first(&[1,2,3,4,5], |x| *x > 3);
    println!("Before: {:?}, After: {:?}", before, after);

    let buckets = bucket_by(&[1,2,3,4,5,6,7,8,9], |x| *x % 3);
    println!("Buckets: {:?}", buckets);
}

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

    #[test]
    fn test_split_even_odd() {
        let (evens, odds) = split_even_odd(&[1,2,3,4,5,6]);
        assert_eq!(evens, vec![2,4,6]);
        assert_eq!(odds, vec![1,3,5]);
    }

    #[test]
    fn test_classify_numbers() {
        let (neg, zero, pos) = classify_numbers(&[-2, 0, 3, -1, 0, 5]);
        assert_eq!(neg, vec![&-2, &-1]);
        assert_eq!(zero, vec![&0, &0]);
        assert_eq!(pos, vec![&3, &5]);
    }

    #[test]
    fn test_partition_results() {
        let (oks, errs) = partition_results(&["1", "abc", "3"]);
        assert_eq!(oks, vec![1, 3]);
        assert_eq!(errs.len(), 1);
    }

    #[test]
    fn test_validate_ages() {
        let (valid, invalid) = validate_ages(&[25, -5, 200, 30, 0]);
        assert_eq!(valid, vec![25, 30, 0]);
        assert_eq!(invalid, vec![-5, 200]);
    }

    #[test]
    fn test_split_at_first() {
        let (before, after) = split_at_first(&[1,2,3,4,5], |x| *x > 3);
        assert_eq!(before, &[1,2,3]);
        assert_eq!(after, &[4,5]);
    }

    #[test]
    fn test_split_at_none() {
        let (before, after) = split_at_first(&[1,2,3], |x| *x > 10);
        assert_eq!(before, &[1,2,3]);
        assert!(after.is_empty());
    }

    #[test]
    fn test_bucket_by() {
        let buckets = bucket_by(&["hello", "hi", "world", "wow"], |s| s.chars().next().unwrap());
        assert_eq!(buckets[&'h'].len(), 2);
        assert_eq!(buckets[&'w'].len(), 2);
    }
}

(* Example 098: Partition Iterator *)
(* Split into two collections by predicate *)

(* Approach 1: List.partition *)
let split_even_odd lst =
  List.partition (fun x -> x mod 2 = 0) lst

let split_positive lst =
  List.partition (fun x -> x > 0) lst

(* Approach 2: Multi-way partition *)
let partition3 p1 p2 lst =
  List.fold_right (fun x (a, b, c) ->
    if p1 x then (x :: a, b, c)
    else if p2 x then (a, x :: b, c)
    else (a, b, x :: c)
  ) lst ([], [], [])

let classify_numbers lst =
  partition3 (fun x -> x < 0) (fun x -> x = 0) lst

(* Approach 3: Partition with transformation *)
let partition_map f lst =
  List.fold_right (fun x (lefts, rights) ->
    match f x with
    | Either.Left l -> (l :: lefts, rights)
    | Either.Right r -> (lefts, r :: rights)
  ) lst ([], [])

let validate_ages ages =
  let valid, invalid = List.partition (fun a -> a >= 0 && a <= 150) ages in
  (valid, invalid)

let split_at_first pred lst =
  let rec aux acc = function
    | [] -> (List.rev acc, [])
    | x :: rest when pred x -> (List.rev acc, x :: rest)
    | x :: rest -> aux (x :: acc) rest
  in
  aux [] lst

(* Tests *)
let () =
  let (evens, odds) = split_even_odd [1;2;3;4;5;6] in
  assert (evens = [2;4;6]);
  assert (odds = [1;3;5]);

  let (pos, neg) = split_positive [3; -1; 4; -5; 0] in
  assert (pos = [3; 4]);
  assert (neg = [-1; -5; 0]);

  let (neg, zero, pos) = classify_numbers [-2; 0; 3; -1; 0; 5] in
  assert (neg = [-2; -1]);
  assert (zero = [0; 0]);
  assert (pos = [3; 5]);

  let (valid, invalid) = validate_ages [25; -5; 200; 30; 0] in
  assert (valid = [25; 30; 0]);
  assert (invalid = [-5; 200]);

  let (before, after) = split_at_first (fun x -> x > 3) [1;2;3;4;5] in
  assert (before = [1;2;3]);
  assert (after = [4;5]);

  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Comparison: Partition Iterator

Binary Partition

OCaml:

🐪 Show OCaml equivalent

let (evens, odds) = List.partition (fun x -> x mod 2 = 0) [1;2;3;4;5;6]
(* evens = [2;4;6], odds = [1;3;5] *)

Rust:

let (evens, odds): (Vec<i32>, Vec<i32>) = [1,2,3,4,5,6].iter().partition(|&&x| x % 2 == 0);

Three-Way Partition

OCaml:

🐪 Show OCaml equivalent

let partition3 p1 p2 lst =
List.fold_right (fun x (a, b, c) ->
 if p1 x then (x :: a, b, c)
 else if p2 x then (a, x :: b, c)
 else (a, b, x :: c)
) lst ([], [], [])

Rust:

fn partition3<T>(data: &[T], p1: impl Fn(&T) -> bool, p2: impl Fn(&T) -> bool)
 -> (Vec<&T>, Vec<&T>, Vec<&T>)
{
 let mut a = Vec::new(); let mut b = Vec::new(); let mut c = Vec::new();
 for item in data {
     if p1(item) { a.push(item); }
     else if p2(item) { b.push(item); }
     else { c.push(item); }
 }
 (a, b, c)
}

Split At

OCaml:

🐪 Show OCaml equivalent

let rec split_at_first pred = function
| [] -> ([], [])
| x :: rest when pred x -> ([], x :: rest)
| x :: rest -> let (a, b) = split_at_first pred rest in (x :: a, b)

Rust:

let pos = data.iter().position(|x| pred(x)).unwrap_or(data.len());
let (before, after) = data.split_at(pos);

098: Partition Iterator

The Problem This Solves

The Intuition

How It Works in Rust

What This Unlocks

Key Differences

📊 Detailed Comparison

Comparison: Partition Iterator

Binary Partition

Three-Way Partition

Split At

Related Examples