098 Intermediate

098 — Partition Iterator

Functional Programming

Tutorial

The Problem

Use Rust's .partition(predicate) to split an iterator into two collections in a single pass: elements satisfying the predicate go into the first collection, the rest into the second. Compare with OCaml's List.partition and partition_map using Either.

🎯 Learning Outcomes

• Use iter.partition(|x| pred(x)) to produce two Vec<T> simultaneously

• Understand that partition consumes the iterator in one pass — no intermediate allocation

• Require a type annotation (Vec<T>, Vec<T>) for the result destructuring

• Handle edge cases: empty input, all-match, no-match

• Map Rust's .partition() to OCaml's List.partition

• Extend to partition_map for element-wise classification into two typed collections

Code Example

#![allow(clippy::all)]
// 098: Partition Iterator

#[cfg(test)]
mod tests {
    #[test]
    fn test_partition() {
        let (evens, odds): (Vec<i32>, Vec<i32>) = (1..=6).partition(|x| x % 2 == 0);
        assert_eq!(evens, vec![2, 4, 6]);
        assert_eq!(odds, vec![1, 3, 5]);
    }

    #[test]
    fn test_partition_empty() {
        let (a, b): (Vec<i32>, Vec<i32>) = std::iter::empty().partition(|_: &i32| true);
        assert!(a.is_empty());
        assert!(b.is_empty());
    }

    #[test]
    fn test_partition_all_match() {
        let (yes, no): (Vec<i32>, Vec<i32>) = (1..=3).partition(|_| true);
        assert_eq!(yes, vec![1, 2, 3]);
        assert!(no.is_empty());
    }
}

(* 098: Partition *)

let partition pred lst = List.partition pred lst

(* Custom partition_map: either left or right *)
let partition_map f lst =
  List.fold_right (fun x (l, r) ->
    match f x with
    | Either.Left v -> (v :: l, r)
    | Either.Right v -> (l, v :: r)
  ) lst ([], [])

(* Tests *)
let () =
  let (evens, odds) = partition (fun x -> x mod 2 = 0) [1;2;3;4;5;6] in
  assert (evens = [2;4;6]);
  assert (odds = [1;3;5]);
  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Built-in	`Iterator::partition(pred)`	`List.partition pred lst`
Return type	`(Vec<T>, Vec<T>)`	`'a list * 'a list`
Type annotation	Required on destructuring	Inferred
`partition_map`	Custom or `itertools`	`List.partition_map` (OCaml 4.12+)
Single pass	Yes	Yes
Empty input	Returns two empty vecs	Returns `([], [])`

partition is cleaner than filter + filter for two complementary predicates — it avoids traversing the input twice. Use it whenever you need both sides of a classification simultaneously.

OCaml Approach

List.partition pred lst is built into the standard library and returns a tuple (list, list). partition_map f lst uses Either.Left/Either.Right to route elements to different typed collections via fold_right. OCaml's partition is lazy-safe only via Seq.partition in newer versions.

Full Source

#![allow(clippy::all)]
// 098: Partition Iterator

#[cfg(test)]
mod tests {
    #[test]
    fn test_partition() {
        let (evens, odds): (Vec<i32>, Vec<i32>) = (1..=6).partition(|x| x % 2 == 0);
        assert_eq!(evens, vec![2, 4, 6]);
        assert_eq!(odds, vec![1, 3, 5]);
    }

    #[test]
    fn test_partition_empty() {
        let (a, b): (Vec<i32>, Vec<i32>) = std::iter::empty().partition(|_: &i32| true);
        assert!(a.is_empty());
        assert!(b.is_empty());
    }

    #[test]
    fn test_partition_all_match() {
        let (yes, no): (Vec<i32>, Vec<i32>) = (1..=3).partition(|_| true);
        assert_eq!(yes, vec![1, 2, 3]);
        assert!(no.is_empty());
    }
}

(* 098: Partition *)

let partition pred lst = List.partition pred lst

(* Custom partition_map: either left or right *)
let partition_map f lst =
  List.fold_right (fun x (l, r) ->
    match f x with
    | Either.Left v -> (v :: l, r)
    | Either.Right v -> (l, v :: r)
  ) lst ([], [])

(* Tests *)
let () =
  let (evens, odds) = partition (fun x -> x mod 2 = 0) [1;2;3;4;5;6] in
  assert (evens = [2;4;6]);
  assert (odds = [1;3;5]);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    #[test]
    fn test_partition() {
        let (evens, odds): (Vec<i32>, Vec<i32>) = (1..=6).partition(|x| x % 2 == 0);
        assert_eq!(evens, vec![2, 4, 6]);
        assert_eq!(odds, vec![1, 3, 5]);
    }

    #[test]
    fn test_partition_empty() {
        let (a, b): (Vec<i32>, Vec<i32>) = std::iter::empty().partition(|_: &i32| true);
        assert!(a.is_empty());
        assert!(b.is_empty());
    }

    #[test]
    fn test_partition_all_match() {
        let (yes, no): (Vec<i32>, Vec<i32>) = (1..=3).partition(|_| true);
        assert_eq!(yes, vec![1, 2, 3]);
        assert!(no.is_empty());
    }
}

Deep Comparison

Core Insight

Partition separates elements into two collections based on a predicate — like filter but keeps both sides

OCaml Approach

• See example.ml for implementation

Rust Approach

• See example.rs for implementation

Comparison Table

Feature	OCaml	Rust
See	example.ml	example.rs

Exercises

Implement partition_map<T, A, B>(iter: impl Iterator<Item=T>, f: impl Fn(T) -> Result<A, B>) -> (Vec<A>, Vec<B>) using fold.

Use partition to split a Vec<Result<T, E>> into (Vec<T>, Vec<E>).

Implement three_way_partition<T>(v: Vec<T>, pred1: impl Fn(&T)->bool, pred2: impl Fn(&T)->bool) -> (Vec<T>, Vec<T>, Vec<T>).

Show that partition(pred) is equivalent to (filter(pred).collect(), filter(|x| !pred(x)).collect()) and explain the trade-off.

In OCaml, implement partition_fold that groups list elements into n buckets based on f: 'a -> int using Array of lists.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust