List.partition — Split by Predicate
Functional Programming
Tutorial
The Problem
Split a collection into two parts in a single traversal: elements that satisfy a predicate go into one group, and those that do not go into another. The function returns both groups simultaneously as a tuple, making it more efficient and expressive than two separate filter operations. This example implements a generic partition function and derives concrete domain helpers — splitting integers by a numeric threshold and strings by length — to show how the abstraction applies in practice.
🎯 Learning Outcomes
List.partition pred xs maps to Rust's Iterator::partition, and why both return a two-element tuple rather than requiring two passesfilter twice is also O(n) but doubles the work and requires the predicate to be called twice per elementClone bound needed to go from &[T] to owned Vec<T> outputFn(&T) -> bool predicate bound and OCaml's structurally-typed anonymous functions — and why Rust requires the bound to be spelled outCode Example
pub fn partition<T: Clone, F>(items: &[T], pred: F) -> (Vec<T>, Vec<T>)
where
F: Fn(&T) -> bool,
{
items.iter().cloned().partition(|x| pred(x))
}Key Differences
List.partition and Iterator::partition traverse the collection once; two separate filter calls would traverse it twice and call the predicate on every element twice — important when the predicate is expensive or the collection is large.let (small, big) = List.partition ...; Rust: let (small, big) = partition(...) — the syntax is identical, which is a pleasant surprise when coming from OCaml.'a -> bool through structural typing; Rust requires the generic bound F: Fn(&T) -> bool, which must be declared explicitly in the function signature and is enforced by the compiler.T: Clone to move values from a borrowed slice into two owned Vecs, making the allocation cost visible in the type signature.OCaml Approach
OCaml's List.partition accepts a predicate and a list, and returns a pair (matches, non_matches) where both lists maintain the original relative order of elements. Internally it is implemented as a single List.fold_left, accumulating into two separate accumulators. The result is destructured with let (small, big) = List.partition (fun x -> x <= 5) numbers — pattern matching on the pair directly in the let binding. The predicate is an ordinary first-class function; no special syntax or trait is needed to pass it.
Full Source
#![allow(clippy::all)]
//! List.partition — Split by Predicate
//! See example.ml for OCaml reference
//!
//! OCaml's `List.partition pred xs` returns `(matches, non_matches)` in a single pass.
//! Rust's `Iterator::partition` does the same, collecting into two separate `Vec`s.
/// Split a slice into two vecs: elements satisfying `pred` and those that don't.
/// Mirrors OCaml: `List.partition (fun x -> x <= 5) numbers`
pub fn partition<T: Clone, F>(items: &[T], pred: F) -> (Vec<T>, Vec<T>)
where
F: Fn(&T) -> bool,
{
items.iter().cloned().partition(|x| pred(x))
}
/// Partition integers into (small, big) where small means `<= threshold`.
pub fn partition_threshold(numbers: &[i32], threshold: i32) -> (Vec<i32>, Vec<i32>) {
partition(numbers, |&x| x <= threshold)
}
/// Partition strings by length: (short, long) where short means `len <= max_len`.
pub fn partition_by_length<'a>(words: &[&'a str], max_len: usize) -> (Vec<&'a str>, Vec<&'a str>) {
partition(words, |s| s.len() <= max_len)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_partition_numbers() {
let numbers: Vec<i32> = (1..=10).collect();
let (small, big) = partition_threshold(&numbers, 5);
assert_eq!(small, vec![1, 2, 3, 4, 5]);
assert_eq!(big, vec![6, 7, 8, 9, 10]);
}
#[test]
fn test_partition_empty() {
let (small, big) = partition_threshold(&[], 5);
assert!(small.is_empty());
assert!(big.is_empty());
}
#[test]
fn test_partition_all_match() {
let nums = vec![1i32, 2, 3];
let (small, big) = partition_threshold(&nums, 10);
assert_eq!(small, vec![1, 2, 3]);
assert!(big.is_empty());
}
#[test]
fn test_partition_none_match() {
let nums = vec![6i32, 7, 8];
let (small, big) = partition_threshold(&nums, 5);
assert!(small.is_empty());
assert_eq!(big, vec![6, 7, 8]);
}
#[test]
fn test_partition_by_length() {
let words = vec!["hi", "hello", "ok", "world", "rust"];
let (short, long) = partition_by_length(&words, 3);
assert_eq!(short, vec!["hi", "ok"]);
assert_eq!(long, vec!["hello", "world", "rust"]);
}
#[test]
fn test_partition_evens_odds() {
let nums: Vec<i32> = (1..=6).collect();
let (evens, odds) = partition(&nums, |&x| x % 2 == 0);
assert_eq!(evens, vec![2, 4, 6]);
assert_eq!(odds, vec![1, 3, 5]);
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_partition_numbers() {
let numbers: Vec<i32> = (1..=10).collect();
let (small, big) = partition_threshold(&numbers, 5);
assert_eq!(small, vec![1, 2, 3, 4, 5]);
assert_eq!(big, vec![6, 7, 8, 9, 10]);
}
#[test]
fn test_partition_empty() {
let (small, big) = partition_threshold(&[], 5);
assert!(small.is_empty());
assert!(big.is_empty());
}
#[test]
fn test_partition_all_match() {
let nums = vec![1i32, 2, 3];
let (small, big) = partition_threshold(&nums, 10);
assert_eq!(small, vec![1, 2, 3]);
assert!(big.is_empty());
}
#[test]
fn test_partition_none_match() {
let nums = vec![6i32, 7, 8];
let (small, big) = partition_threshold(&nums, 5);
assert!(small.is_empty());
assert_eq!(big, vec![6, 7, 8]);
}
#[test]
fn test_partition_by_length() {
let words = vec!["hi", "hello", "ok", "world", "rust"];
let (short, long) = partition_by_length(&words, 3);
assert_eq!(short, vec!["hi", "ok"]);
assert_eq!(long, vec!["hello", "world", "rust"]);
}
#[test]
fn test_partition_evens_odds() {
let nums: Vec<i32> = (1..=6).collect();
let (evens, odds) = partition(&nums, |&x| x % 2 == 0);
assert_eq!(evens, vec![2, 4, 6]);
assert_eq!(odds, vec![1, 3, 5]);
}
}Deep Comparison
OCaml vs Rust: List.partition — Split by Predicate
Side-by-Side Code
OCaml
let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
let (small, big) = List.partition (fun x -> x <= 5) numbers
Rust (idiomatic)
pub fn partition<T: Clone, F>(items: &[T], pred: F) -> (Vec<T>, Vec<T>)
where
F: Fn(&T) -> bool,
{
items.iter().cloned().partition(|x| pred(x))
}
Rust (functional fold)
// Mirrors OCaml's accumulator-based implementation explicitly.
pub fn partition_fold<T: Clone, F>(items: &[T], pred: F) -> (Vec<T>, Vec<T>)
where
F: Fn(&T) -> bool,
{
items.iter().fold((vec![], vec![]), |(mut yes, mut no), x| {
if pred(x) { yes.push(x.clone()); } else { no.push(x.clone()); }
(yes, no)
})
}
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| partition | ('a -> bool) -> 'a list -> 'a list * 'a list | fn partition<T: Clone, F>(&[T], F) -> (Vec<T>, Vec<T>) |
| result type | 'a list * 'a list (tuple) | (Vec<T>, Vec<T>) (tuple) |
| predicate | 'a -> bool | F: Fn(&T) -> bool |
| destructuring | let (small, big) = ... | let (small, big) = ... |
Key Insights
partition traverse the list once and split into two output collections, which is more efficient than calling filter twice.Iterator::partition is a built-in method that collects into a pair of collections — exactly matching OCaml's List.partition semantics.let (a, b) = partition(...) for destructuring the result tuple — the syntax is nearly identical.clone() each element since ownership prevents moving items into two separate Vecs simultaneously. OCaml's GC shares list nodes freely.'a; Rust's receives a reference &T (since the iterator yields &T from a &[T] slice). The cloned() adapter materializes the T after filtering.When to Use Each Style
**Use Iterator::partition when:** you need to split a slice into two groups in a single pass — it's the most idiomatic and readable approach.
Use the fold-based partition when: you want to accumulate into more complex structures than a pair of Vecs (e.g., a HashMap of groups), or when teaching the fold-based derivation of partition.
Exercises
partition_map that applies a function returning Result<A, B> to each element and collects Ok(a) values into one Vec<A> and Err(b) values into another Vec<B>, in a single pass. This mirrors the OCaml List.partition_map added in OCaml 4.12.low and high, return (below, middle, above) in a single traversal. Verify that the union of all three groups contains exactly the elements of the input with no duplicates or omissions.partition and two separate filter calls always produce the same result, and that the concatenation of both output Vecs is a permutation of the input slice.