892-partition-iterator — Partition Iterator
Functional Programming
Tutorial
The Problem
Splitting a collection into groups based on a predicate is a fundamental data classification operation. Database query engines partition rows into matching and non-matching sets. Compilers partition tokens into valid and invalid. Trading systems partition orders into buy and sell. The naive approach uses two separate filter passes, scanning the data twice. Iterator::partition does this in one pass, returning two collections simultaneously. OCaml has List.partition. Python's itertools requires two passes. This single-pass property is critical for large data sets or when the source can only be consumed once.
🎯 Learning Outcomes
Iterator::partition(pred) to split into two collections in one pass.fold() for multi-class classificationEither<L, R> to route elements with transformation during partitioning.filter() callsList.partition and three-way classification idiomsCode Example
pub fn split_even_odd(data: &[i32]) -> (Vec<i32>, Vec<i32>) {
data.iter().partition(|&&x| x % 2 == 0)
}Key Differences
partition preserves input order; OCaml List.partition using cons-prepend requires List.rev to restore order.partition_map with Either can partition into two collections of different types; OCaml partition_map similarly supports this.partition on iter() produces Vec<&T>; using into_iter() produces Vec<T> with ownership transfer.OCaml Approach
List.partition: ('a -> bool) -> 'a list -> 'a list * 'a list is the direct equivalent. OCaml also has List.partition_map: ('a -> ('b, 'c) Either.t) -> 'a list -> 'b list * 'c list (since 4.14). Three-way partition: List.fold_left (fun (a, b, c) x -> if p1 x then (x::a, b, c) else if p2 x then (a, x::b, c) else (a, b, x::c)) ([], [], []) xs. OCaml's lists are singly-linked, so partition is O(n) but the cons-append order reverses the output (requires List.rev).
Full Source
#![allow(clippy::all)]
//! Example 892: Partition Iterator
//! Split a collection into two groups by a predicate — single pass, two outputs.
// === Approach 1: Basic partition using Iterator::partition ===
/// Split integers into even and odd — idiomatic Rust, one pass.
pub fn split_even_odd(data: &[i32]) -> (Vec<i32>, Vec<i32>) {
data.iter().partition(|&&x| x % 2 == 0)
}
/// Split integers into positive and non-positive.
pub fn split_positive(data: &[i32]) -> (Vec<i32>, Vec<i32>) {
data.iter().partition(|&&x| x > 0)
}
// === Approach 2: Multi-way partition (fold-based, mirrors OCaml's fold_right) ===
/// Partition into three groups by two predicates.
/// Elements matching `p1` go to `a`, those matching `p2` (but not `p1`) to `b`,
/// and the rest to `c`.
pub fn partition3<T: Clone>(
data: &[T],
p1: impl Fn(&T) -> bool,
p2: impl Fn(&T) -> bool,
) -> (Vec<T>, Vec<T>, Vec<T>) {
data.iter().cloned().fold(
(Vec::new(), Vec::new(), Vec::new()),
|(mut a, mut b, mut c), x| {
if p1(&x) {
a.push(x);
} else if p2(&x) {
b.push(x);
} else {
c.push(x);
}
(a, b, c)
},
)
}
/// Classify integers into negatives, zeros, and positives.
pub fn classify_numbers(data: &[i32]) -> (Vec<i32>, Vec<i32>, Vec<i32>) {
partition3(data, |&x| x < 0, |&x| x == 0)
}
// === Approach 3: partition_map — route elements to Left or Right with transformation ===
pub enum Either<L, R> {
Left(L),
Right(R),
}
/// Partition with simultaneous transformation.
/// Each element is mapped to `Either::Left` or `Either::Right`; results are collected
/// into two separate `Vec`s — mirrors OCaml's `Either`-based `partition_map`.
pub fn partition_map<T, L, R>(data: &[T], f: impl Fn(&T) -> Either<L, R>) -> (Vec<L>, Vec<R>) {
data.iter()
.fold((Vec::new(), Vec::new()), |(mut lefts, mut rights), x| {
match f(x) {
Either::Left(l) => lefts.push(l),
Either::Right(r) => rights.push(r),
}
(lefts, rights)
})
}
/// Parse strings into successes (i32) and failures (original string).
pub fn parse_numbers<'a>(data: &[&'a str]) -> (Vec<i32>, Vec<&'a str>) {
partition_map(data, |s| match s.parse::<i32>() {
Ok(n) => Either::Left(n),
Err(_) => Either::Right(*s),
})
}
#[cfg(test)]
mod tests {
use super::*;
// --- split_even_odd ---
#[test]
fn test_split_even_odd_empty() {
let (evens, odds) = split_even_odd(&[]);
assert_eq!(evens, Vec::<i32>::new());
assert_eq!(odds, Vec::<i32>::new());
}
#[test]
fn test_split_even_odd_mixed() {
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_split_even_odd_all_even() {
let (evens, odds) = split_even_odd(&[2, 4, 8]);
assert_eq!(evens, vec![2, 4, 8]);
assert!(odds.is_empty());
}
#[test]
fn test_split_even_odd_negatives() {
let (evens, odds) = split_even_odd(&[-4, -3, 0, 1]);
assert_eq!(evens, vec![-4, 0]);
assert_eq!(odds, vec![-3, 1]);
}
// --- split_positive ---
#[test]
fn test_split_positive_mixed() {
let (pos, non_pos) = split_positive(&[-2, -1, 0, 1, 2]);
assert_eq!(pos, vec![1, 2]);
assert_eq!(non_pos, vec![-2, -1, 0]);
}
// --- classify_numbers ---
#[test]
fn test_classify_numbers() {
let (neg, zero, pos) = classify_numbers(&[-3, -1, 0, 0, 2, 5]);
assert_eq!(neg, vec![-3, -1]);
assert_eq!(zero, vec![0, 0]);
assert_eq!(pos, vec![2, 5]);
}
#[test]
fn test_classify_numbers_empty() {
let (neg, zero, pos) = classify_numbers(&[]);
assert!(neg.is_empty());
assert!(zero.is_empty());
assert!(pos.is_empty());
}
// --- parse_numbers (partition_map) ---
#[test]
fn test_parse_numbers_mixed() {
let (parsed, failed) = parse_numbers(&["1", "two", "3", "four", "5"]);
assert_eq!(parsed, vec![1, 3, 5]);
assert_eq!(failed, vec!["two", "four"]);
}
#[test]
fn test_parse_numbers_all_valid() {
let (parsed, failed) = parse_numbers(&["10", "20", "30"]);
assert_eq!(parsed, vec![10, 20, 30]);
assert!(failed.is_empty());
}
#[test]
fn test_parse_numbers_all_invalid() {
let (parsed, failed) = parse_numbers(&["a", "b", "c"]);
assert!(parsed.is_empty());
assert_eq!(failed, vec!["a", "b", "c"]);
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
// --- split_even_odd ---
#[test]
fn test_split_even_odd_empty() {
let (evens, odds) = split_even_odd(&[]);
assert_eq!(evens, Vec::<i32>::new());
assert_eq!(odds, Vec::<i32>::new());
}
#[test]
fn test_split_even_odd_mixed() {
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_split_even_odd_all_even() {
let (evens, odds) = split_even_odd(&[2, 4, 8]);
assert_eq!(evens, vec![2, 4, 8]);
assert!(odds.is_empty());
}
#[test]
fn test_split_even_odd_negatives() {
let (evens, odds) = split_even_odd(&[-4, -3, 0, 1]);
assert_eq!(evens, vec![-4, 0]);
assert_eq!(odds, vec![-3, 1]);
}
// --- split_positive ---
#[test]
fn test_split_positive_mixed() {
let (pos, non_pos) = split_positive(&[-2, -1, 0, 1, 2]);
assert_eq!(pos, vec![1, 2]);
assert_eq!(non_pos, vec![-2, -1, 0]);
}
// --- classify_numbers ---
#[test]
fn test_classify_numbers() {
let (neg, zero, pos) = classify_numbers(&[-3, -1, 0, 0, 2, 5]);
assert_eq!(neg, vec![-3, -1]);
assert_eq!(zero, vec![0, 0]);
assert_eq!(pos, vec![2, 5]);
}
#[test]
fn test_classify_numbers_empty() {
let (neg, zero, pos) = classify_numbers(&[]);
assert!(neg.is_empty());
assert!(zero.is_empty());
assert!(pos.is_empty());
}
// --- parse_numbers (partition_map) ---
#[test]
fn test_parse_numbers_mixed() {
let (parsed, failed) = parse_numbers(&["1", "two", "3", "four", "5"]);
assert_eq!(parsed, vec![1, 3, 5]);
assert_eq!(failed, vec!["two", "four"]);
}
#[test]
fn test_parse_numbers_all_valid() {
let (parsed, failed) = parse_numbers(&["10", "20", "30"]);
assert_eq!(parsed, vec![10, 20, 30]);
assert!(failed.is_empty());
}
#[test]
fn test_parse_numbers_all_invalid() {
let (parsed, failed) = parse_numbers(&["a", "b", "c"]);
assert!(parsed.is_empty());
assert_eq!(failed, vec!["a", "b", "c"]);
}
}Deep Comparison
OCaml vs Rust: Partition Iterator
Side-by-Side Code
OCaml
(* Binary partition: evens vs odds *)
let split_even_odd lst =
List.partition (fun x -> x mod 2 = 0) lst
(* Multi-way partition via fold_right *)
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 ([], [], [])
(* Partition with transformation using Either *)
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 ([], [])
Rust (idiomatic — Iterator::partition)
pub fn split_even_odd(data: &[i32]) -> (Vec<i32>, Vec<i32>) {
data.iter().partition(|&&x| x % 2 == 0)
}
Rust (functional/recursive — fold-based multi-way)
pub fn partition3<T: Clone>(
data: &[T],
p1: impl Fn(&T) -> bool,
p2: impl Fn(&T) -> bool,
) -> (Vec<T>, Vec<T>, Vec<T>) {
data.iter().cloned().fold(
(Vec::new(), Vec::new(), Vec::new()),
|(mut a, mut b, mut c), x| {
if p1(&x) { a.push(x); }
else if p2(&x) { b.push(x); }
else { c.push(x); }
(a, b, c)
},
)
}
Rust (partition_map with user-defined Either)
pub fn partition_map<T, L, R>(
data: &[T],
f: impl Fn(&T) -> Either<L, R>,
) -> (Vec<L>, Vec<R>) {
data.iter().fold((Vec::new(), Vec::new()), |(mut lefts, mut rights), x| {
match f(x) {
Either::Left(l) => lefts.push(l),
Either::Right(r) => rights.push(r),
}
(lefts, rights)
})
}
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| Binary partition | val partition : ('a -> bool) -> 'a list -> 'a list * 'a list | fn partition(self, f: impl Fn(&T) -> bool) -> (B, B) |
| Input collection | 'a list | &[T] (borrowed slice) |
| Output collection | 'a list * 'a list | (Vec<T>, Vec<T>) |
| Multi-way | tuple of 3 lists | (Vec<T>, Vec<T>, Vec<T>) |
| Either type | Either.Left \| Either.Right (stdlib) | user-defined enum Either<L, R> |
Key Insights
List.partition and Rust's Iterator::partition traverse the input exactly once, routing each element to one of two output collections simultaneously — unlike two separate filter calls.T: Clone) or collect references (Vec<&T>). Cloning here is semantically correct since both output Vecs own their elements independently.Either availability**: OCaml 4.12+ ships Either in the standard library. Rust's standard library does not expose Either, so partition_map requires a user-defined enum — a common pattern also addressed by the either crate.fold_right mirrors Rust's .fold(). Both accumulate a tuple of collections in a single left-to-right (or right-to-left in OCaml) scan, making the pattern directly translatable across the two languages.Iterator::partition is constrained to B: Default + Extend<Self::Item>, which Vec<T> satisfies out of the box. This genericity means partition works on any collection implementing those traits, not just Vec.When to Use Each Style
**Use Iterator::partition when:** splitting into exactly two groups with a simple boolean predicate and no transformation needed — it is the most concise and idiomatic choice.
**Use fold-based multi-way partition when:** you need three or more output buckets, or when the routing logic is complex enough that match branches are clearer than nested if/else.
**Use partition_map when:** each element must be transformed as it is routed — for example, parsing results where successes become i32 and failures keep the original &str.
Exercises
partition_at_index<T: Clone>(data: &[T], n: usize) -> (Vec<T>, Vec<T>) that splits at position n.classify_words(words: &[&str]) -> (Vec<&str>, Vec<&str>, Vec<&str>) that separates short (<5), medium (5-8), and long (>8) words.stable_partition<T: Clone>(data: &[T], pred: impl Fn(&T) -> bool) -> Vec<T> that moves all matching elements to the front while preserving relative order.