List Filter — Select Elements by Predicate
ListsHOF
Tutorial
The Problem
Select elements from a list that satisfy a boolean predicate, equivalent to OCaml's List.filter. Demonstrated by splitting a list of integers into even and odd subsets.
🎯 Learning Outcomes
List.filter maps to Rust's .iter().filter().collect()Iterator::partition computes both halves in one pass — more efficient than filtering twice[head, tail @ ..]) enables recursive list processing&[T]) and owning (Vec<T>) in filter operations🦀 The Rust Way
Rust's iterator chain list.iter().filter(|x| pred(x)).cloned().collect() mirrors List.filter directly. For computing both halves, Iterator::partition is more efficient than two filter passes. Recursive slice pattern matching ([head, tail @ ..]) makes the OCaml structural recursion explicit in Rust.
Code Example
pub fn filter_idiomatic<T, F>(list: &[T], predicate: F) -> Vec<T>
where
T: Clone,
F: Fn(&T) -> bool,
{
list.iter().filter(|x| predicate(x)).cloned().collect()
}
// Two halves in a single pass — more efficient than filtering twice
pub fn partition_by<T, F>(list: &[T], predicate: F) -> (Vec<T>, Vec<T>)
where
T: Clone,
F: Fn(&T) -> bool,
{
let (yes, no): (Vec<&T>, Vec<&T>) = list.iter().partition(|x| predicate(x));
(
yes.into_iter().cloned().collect(),
no.into_iter().cloned().collect(),
)
}Key Differences
'a list; Rust uses contiguous &[T] slices — no allocation for the input.&T to avoid cloning the input during filtering.evens and odds with two separate List.filter calls (two passes); Rust's partition does it in one pass..clone() elements when going from borrowed &T to owned Vec<T>.OCaml Approach
OCaml's List.filter pred lst traverses the list and builds a new list of elements satisfying pred. It is defined recursively in terms of cons (::) and is a classic higher-order function. OCaml also has List.partition for splitting into two lists at once.
Full Source
#![allow(clippy::all)]
/// Filter elements from a slice that satisfy the predicate.
///
/// Solution 1: Idiomatic Rust — iterator `.filter()` chain.
/// Mirrors OCaml's `List.filter` directly.
pub fn filter_idiomatic<T, F>(list: &[T], predicate: F) -> Vec<T>
where
T: Clone,
F: Fn(&T) -> bool,
{
list.iter().filter(|x| predicate(x)).cloned().collect()
}
/// Split a slice into matching and non-matching elements in one pass.
///
/// Solution 2: Partition — more efficient than filtering twice when you need
/// both halves, as in the OCaml example that computes both evens and odds.
pub fn partition_by<T, F>(list: &[T], predicate: F) -> (Vec<T>, Vec<T>)
where
T: Clone,
F: Fn(&T) -> bool,
{
// iter() yields &T; partition collects into (Vec<&T>, Vec<&T>)
let (yes, no): (Vec<&T>, Vec<&T>) = list.iter().partition(|x| predicate(x));
(
yes.into_iter().cloned().collect(),
no.into_iter().cloned().collect(),
)
}
/// Filter elements recursively — mirrors OCaml's explicit pattern matching.
///
/// Solution 3: Recursive, closest to OCaml's structural recursion on lists.
pub fn filter_recursive<T, F>(list: &[T], predicate: F) -> Vec<T>
where
T: Clone,
F: Fn(&T) -> bool,
{
fn go<T, F>(list: &[T], pred: &F) -> Vec<T>
where
T: Clone,
F: Fn(&T) -> bool,
{
match list {
[] => vec![],
[head, tail @ ..] => {
let mut rest = go(tail, pred);
if pred(head) {
// Prepend: mirrors OCaml's `x :: filter pred rest`
rest.insert(0, head.clone());
}
rest
}
}
}
go(list, &predicate)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_filter_empty() {
let empty: &[i32] = &[];
assert_eq!(filter_idiomatic(empty, |x| x % 2 == 0), Vec::<i32>::new());
}
#[test]
fn test_filter_evens() {
let numbers = [1, 2, 3, 4, 5, 6, 7, 8];
assert_eq!(filter_idiomatic(&numbers, |x| x % 2 == 0), vec![2, 4, 6, 8]);
}
#[test]
fn test_filter_odds() {
let numbers = [1, 2, 3, 4, 5, 6, 7, 8];
assert_eq!(filter_idiomatic(&numbers, |x| x % 2 != 0), vec![1, 3, 5, 7]);
}
#[test]
fn test_filter_none_match() {
let numbers = [1, 3, 5];
assert_eq!(
filter_idiomatic(&numbers, |x| x % 2 == 0),
Vec::<i32>::new()
);
}
#[test]
fn test_filter_all_match() {
let numbers = [2, 4, 6];
assert_eq!(filter_idiomatic(&numbers, |x| x % 2 == 0), vec![2, 4, 6]);
}
#[test]
fn test_filter_by_threshold() {
let numbers = [1, 5, 10, 15, 20];
assert_eq!(filter_idiomatic(&numbers, |x| *x > 10), vec![15, 20]);
}
#[test]
fn test_partition_evens_and_odds() {
let numbers = [1, 2, 3, 4, 5, 6, 7, 8];
let (evens, odds) = partition_by(&numbers, |x| x % 2 == 0);
assert_eq!(evens, vec![2, 4, 6, 8]);
assert_eq!(odds, vec![1, 3, 5, 7]);
}
#[test]
fn test_recursive_matches_idiomatic() {
let numbers = [1, 2, 3, 4, 5, 6, 7, 8];
assert_eq!(
filter_recursive(&numbers, |x| x % 2 == 0),
filter_idiomatic(&numbers, |x| x % 2 == 0)
);
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_filter_empty() {
let empty: &[i32] = &[];
assert_eq!(filter_idiomatic(empty, |x| x % 2 == 0), Vec::<i32>::new());
}
#[test]
fn test_filter_evens() {
let numbers = [1, 2, 3, 4, 5, 6, 7, 8];
assert_eq!(filter_idiomatic(&numbers, |x| x % 2 == 0), vec![2, 4, 6, 8]);
}
#[test]
fn test_filter_odds() {
let numbers = [1, 2, 3, 4, 5, 6, 7, 8];
assert_eq!(filter_idiomatic(&numbers, |x| x % 2 != 0), vec![1, 3, 5, 7]);
}
#[test]
fn test_filter_none_match() {
let numbers = [1, 3, 5];
assert_eq!(
filter_idiomatic(&numbers, |x| x % 2 == 0),
Vec::<i32>::new()
);
}
#[test]
fn test_filter_all_match() {
let numbers = [2, 4, 6];
assert_eq!(filter_idiomatic(&numbers, |x| x % 2 == 0), vec![2, 4, 6]);
}
#[test]
fn test_filter_by_threshold() {
let numbers = [1, 5, 10, 15, 20];
assert_eq!(filter_idiomatic(&numbers, |x| *x > 10), vec![15, 20]);
}
#[test]
fn test_partition_evens_and_odds() {
let numbers = [1, 2, 3, 4, 5, 6, 7, 8];
let (evens, odds) = partition_by(&numbers, |x| x % 2 == 0);
assert_eq!(evens, vec![2, 4, 6, 8]);
assert_eq!(odds, vec![1, 3, 5, 7]);
}
#[test]
fn test_recursive_matches_idiomatic() {
let numbers = [1, 2, 3, 4, 5, 6, 7, 8];
assert_eq!(
filter_recursive(&numbers, |x| x % 2 == 0),
filter_idiomatic(&numbers, |x| x % 2 == 0)
);
}
}Deep Comparison
OCaml vs Rust: List Filter — Select Elements by Predicate
Side-by-Side Code
OCaml
(* Idiomatic: List.filter is built-in *)
let numbers = [1; 2; 3; 4; 5; 6; 7; 8]
let evens = List.filter (fun x -> x mod 2 = 0) numbers
let odds = List.filter (fun x -> x mod 2 <> 0) numbers
(* Recursive: explicit structural recursion *)
let rec filter_rec pred = function
| [] -> []
| x :: rest ->
if pred x then x :: filter_rec pred rest
else filter_rec pred rest
Rust (idiomatic)
pub fn filter_idiomatic<T, F>(list: &[T], predicate: F) -> Vec<T>
where
T: Clone,
F: Fn(&T) -> bool,
{
list.iter().filter(|x| predicate(x)).cloned().collect()
}
// Two halves in a single pass — more efficient than filtering twice
pub fn partition_by<T, F>(list: &[T], predicate: F) -> (Vec<T>, Vec<T>)
where
T: Clone,
F: Fn(&T) -> bool,
{
let (yes, no): (Vec<&T>, Vec<&T>) = list.iter().partition(|x| predicate(x));
(
yes.into_iter().cloned().collect(),
no.into_iter().cloned().collect(),
)
}
Rust (functional/recursive)
pub fn filter_recursive<T, F>(list: &[T], predicate: F) -> Vec<T>
where
T: Clone,
F: Fn(&T) -> bool,
{
fn go<T, F>(list: &[T], pred: &F) -> Vec<T>
where
T: Clone,
F: Fn(&T) -> bool,
{
match list {
[] => vec![],
[head, tail @ ..] => {
let mut rest = go(tail, pred);
if pred(head) {
rest.insert(0, head.clone()); // prepend: mirrors `x :: filter_rec pred rest`
}
rest
}
}
}
go(list, &predicate)
}
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| Filter function | val filter : ('a -> bool) -> 'a list -> 'a list | fn filter_idiomatic<T, F>(list: &[T], predicate: F) -> Vec<T> |
| Predicate type | 'a -> bool | F: Fn(&T) -> bool |
| List type (input) | 'a list | &[T] (borrowed slice) |
| List type (output) | 'a list | Vec<T> (owned) |
| Partition | val partition : ('a -> bool) -> 'a list -> 'a list * 'a list | fn partition_by<T, F>(list: &[T], predicate: F) -> (Vec<T>, Vec<T>) |
Key Insights
List.filter → .filter().collect():** The iterator chain is a direct translation — the predicate is passed as a closure and items satisfying it are collected into a new Vec.&T (references) to avoid cloning the input elements before the final .cloned().collect() at the output.List.filter twice (once for evens, once for odds), making two passes over the list. Rust's partition does both in a single pass — a meaningful optimization for large lists.[head, tail @ ..] in Rust is a close match to OCaml's x :: rest — both destructure the head from the tail, enabling the same recursive structure.&T to an owned Vec<T> requires .clone() — the cost is explicit and visible.When to Use Each Style
**Use idiomatic Rust (.filter().collect()) when:** you need a subset of a slice and want clear, concise code that mirrors List.filter.
**Use partition_by when:** you need both the matching and non-matching elements — it avoids a second traversal and is the Rust equivalent to OCaml's List.partition.
Use recursive Rust when: you are learning the OCaml→Rust translation or need to implement a custom traversal that processes elements in pairs or accumulates state beyond what filter supports.
Exercises
filter with map in a single pass: implement filter_map that applies a T -> Option<U> function and collects only Some results.take_while from scratch: return elements from the front of the list as long as the predicate holds, stopping at the first failure.filter_with_context that passes both the current element and the previously accepted element (as an Option) to the predicate, enabling stateful filtering like keeping only elements greater than the last accepted one.