1181 Intermediate

List.partition — Divide List by Predicate

Functional Programming

Tutorial

The Problem

Split a list (or slice) into two groups based on a predicate: elements satisfying the predicate go into the first group, the rest into the second.

🎯 Learning Outcomes

• How Rust's Iterator::partition mirrors OCaml's List.partition directly

• How to write the same logic as a fold accumulator (functional Rust style)

• How slice pattern matching enables recursive list processing in Rust

• The difference between Fn(&T) -> bool (idiomatic) and double-deref in iterator closures

🦀 The Rust Way

Rust's Iterator::partition mirrors OCaml's List.partition almost exactly: it consumes the iterator and returns a pair of collections. Working on slices (&[T]) rather than owned lists preserves the data without allocation, while the predicate receives &T (a reference to each element).

Code Example

pub fn partition_idiomatic<T, F>(items: &[T], pred: F) -> (Vec<&T>, Vec<&T>)
where
    F: Fn(&T) -> bool,
{
    items.iter().partition(|x| pred(x))
}

(* Idiomatic — one function call *)
let (small, big) = List.partition (fun x -> x <= 5) [1;2;3;4;5;6;7;8;9;10]

(* Recursive — explicit structural recursion *)
let rec partition_rec pred = function
  | [] -> ([], [])
  | x :: rest ->
    let (yes, no) = partition_rec pred rest in
    if pred x then (x :: yes, no)
    else (yes, x :: no)

Key Differences

Types: OCaml returns 'a list * 'a list (owned copies); Rust returns (Vec<&T>, Vec<&T>) (references into the original slice) — zero copying.

Predicate arity: OCaml predicate takes 'a; Rust predicate takes &T because we iterate over references.

Recursion depth: OCaml's recursive partition_rec is idiomatic; in Rust, deep recursion on slices risks stack overflow — prefer Iterator::partition or fold.

Allocation: OCaml lists are singly-linked and always heap-allocated; Rust slices are contiguous and borrowed, allocation only happens for the result Vecs.

OCaml Approach

OCaml provides List.partition : ('a -> bool) -> 'a list -> 'a list * 'a list in the standard library. The recursive implementation uses structural pattern matching on the cons list, prepending to the matching or non-matching accumulator on each step.

Full Source

/// Partition a slice into two Vecs based on a predicate.
/// Elements for which `pred` returns true go into the first Vec (yes),
/// the rest into the second Vec (no).
///
/// Solution 1: Idiomatic Rust — uses `partition` from Iterator
pub fn partition_idiomatic<T, F>(items: &[T], pred: F) -> (Vec<&T>, Vec<&T>)
where
    F: Fn(&T) -> bool,
{
    // items.iter() yields &T; Iterator::partition's closure receives &&T, so deref once
    items.iter().partition(|x| pred(x))
}

/// Solution 2: Functional fold — mirrors the OCaml accumulator style
pub fn partition_fold<T, 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);
        } else {
            no.push(x);
        }
        (yes, no)
    })
}

/// Solution 3: Recursive — explicit recursion matching OCaml style
pub fn partition_recursive<'a, T, F>(items: &'a [T], pred: &F) -> (Vec<&'a T>, Vec<&'a T>)
where
    F: Fn(&T) -> bool,
{
    match items {
        [] => (vec![], vec![]),
        [head, rest @ ..] => {
            let (mut yes, mut no) = partition_recursive(rest, pred);
            if pred(head) {
                yes.insert(0, head);
            } else {
                no.insert(0, head);
            }
            (yes, no)
        }
    }
}

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

    #[test]
    fn test_empty() {
        let empty: &[i32] = &[];
        let (yes, no) = partition_idiomatic(empty, |_| true);
        assert!(yes.is_empty());
        assert!(no.is_empty());
    }

    #[test]
    fn test_single_matches() {
        let (yes, no) = partition_idiomatic(&[3_i32], |x| *x <= 5);
        assert_eq!(yes, vec![&3]);
        assert!(no.is_empty());
    }

    #[test]
    fn test_single_no_match() {
        let (yes, no) = partition_idiomatic(&[7_i32], |x| *x <= 5);
        assert!(yes.is_empty());
        assert_eq!(no, vec![&7]);
    }

    #[test]
    fn test_numbers_split_at_5() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10_i32];
        let (small, big) = partition_idiomatic(&numbers, |x| *x <= 5);
        assert_eq!(small, vec![&1, &2, &3, &4, &5]);
        assert_eq!(big, vec![&6, &7, &8, &9, &10]);
    }

    #[test]
    fn test_all_match() {
        let data = [1, 2, 3_i32];
        let (yes, no) = partition_idiomatic(&data, |x| *x < 10);
        assert_eq!(yes, vec![&1, &2, &3]);
        assert!(no.is_empty());
    }

    #[test]
    fn test_none_match() {
        let data = [10, 20, 30_i32];
        let (yes, no) = partition_idiomatic(&data, |x| *x < 5);
        assert!(yes.is_empty());
        assert_eq!(no, vec![&10, &20, &30]);
    }

    #[test]
    fn test_fold_matches_idiomatic() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10_i32];
        let (s1, b1) = partition_idiomatic(&numbers, |x| *x <= 5);
        let (s2, b2) = partition_fold(&numbers, |x| *x <= 5);
        assert_eq!(s1, s2);
        assert_eq!(b1, b2);
    }

    #[test]
    fn test_recursive_matches_idiomatic() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10_i32];
        let pred = |x: &i32| *x <= 5;
        let (s1, b1) = partition_idiomatic(&numbers, pred);
        let (s2, b2) = partition_recursive(&numbers, &pred);
        assert_eq!(s1, s2);
        assert_eq!(b1, b2);
    }

    #[test]
    fn test_even_odd_partition() {
        let data = [1, 2, 3, 4, 5, 6_i32];
        let (evens, odds) = partition_idiomatic(&data, |x| *x % 2 == 0);
        assert_eq!(evens, vec![&2, &4, &6]);
        assert_eq!(odds, vec![&1, &3, &5]);
    }
}

(* Idiomatic OCaml — List.partition splits a list by a predicate *)
let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
let (small, big) = List.partition (fun x -> x <= 5) numbers

let () = Printf.printf "Small: %s\n"
  (String.concat " " (List.map string_of_int small))
let () = Printf.printf "Big: %s\n"
  (String.concat " " (List.map string_of_int big))

(* Recursive OCaml — shows the explicit structural recursion *)
let rec partition_rec pred = function
  | [] -> ([], [])
  | x :: rest ->
    let (yes, no) = partition_rec pred rest in
    if pred x then (x :: yes, no)
    else (yes, x :: no)

let () =
  let (s, b) = partition_rec (fun x -> x <= 5) numbers in
  assert (s = [1; 2; 3; 4; 5]);
  assert (b = [6; 7; 8; 9; 10]);
  let (evens, odds) = List.partition (fun x -> x mod 2 = 0) numbers in
  assert (evens = [2; 4; 6; 8; 10]);
  assert (odds = [1; 3; 5; 7; 9]);
  assert (List.partition (fun _ -> true) [] = ([], []));
  print_endline "ok"

✓ Tests Rust test suite

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

    #[test]
    fn test_empty() {
        let empty: &[i32] = &[];
        let (yes, no) = partition_idiomatic(empty, |_| true);
        assert!(yes.is_empty());
        assert!(no.is_empty());
    }

    #[test]
    fn test_single_matches() {
        let (yes, no) = partition_idiomatic(&[3_i32], |x| *x <= 5);
        assert_eq!(yes, vec![&3]);
        assert!(no.is_empty());
    }

    #[test]
    fn test_single_no_match() {
        let (yes, no) = partition_idiomatic(&[7_i32], |x| *x <= 5);
        assert!(yes.is_empty());
        assert_eq!(no, vec![&7]);
    }

    #[test]
    fn test_numbers_split_at_5() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10_i32];
        let (small, big) = partition_idiomatic(&numbers, |x| *x <= 5);
        assert_eq!(small, vec![&1, &2, &3, &4, &5]);
        assert_eq!(big, vec![&6, &7, &8, &9, &10]);
    }

    #[test]
    fn test_all_match() {
        let data = [1, 2, 3_i32];
        let (yes, no) = partition_idiomatic(&data, |x| *x < 10);
        assert_eq!(yes, vec![&1, &2, &3]);
        assert!(no.is_empty());
    }

    #[test]
    fn test_none_match() {
        let data = [10, 20, 30_i32];
        let (yes, no) = partition_idiomatic(&data, |x| *x < 5);
        assert!(yes.is_empty());
        assert_eq!(no, vec![&10, &20, &30]);
    }

    #[test]
    fn test_fold_matches_idiomatic() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10_i32];
        let (s1, b1) = partition_idiomatic(&numbers, |x| *x <= 5);
        let (s2, b2) = partition_fold(&numbers, |x| *x <= 5);
        assert_eq!(s1, s2);
        assert_eq!(b1, b2);
    }

    #[test]
    fn test_recursive_matches_idiomatic() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10_i32];
        let pred = |x: &i32| *x <= 5;
        let (s1, b1) = partition_idiomatic(&numbers, pred);
        let (s2, b2) = partition_recursive(&numbers, &pred);
        assert_eq!(s1, s2);
        assert_eq!(b1, b2);
    }

    #[test]
    fn test_even_odd_partition() {
        let data = [1, 2, 3, 4, 5, 6_i32];
        let (evens, odds) = partition_idiomatic(&data, |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 — Divide List by Predicate

Side-by-Side Code

OCaml

(* Idiomatic — one function call *)
let (small, big) = List.partition (fun x -> x <= 5) [1;2;3;4;5;6;7;8;9;10]

(* Recursive — explicit structural recursion *)
let rec partition_rec pred = function
  | [] -> ([], [])
  | x :: rest ->
    let (yes, no) = partition_rec pred rest in
    if pred x then (x :: yes, no)
    else (yes, x :: no)

Rust (idiomatic)

pub fn partition_idiomatic<T, F>(items: &[T], pred: F) -> (Vec<&T>, Vec<&T>)
where
    F: Fn(&T) -> bool,
{
    items.iter().partition(|x| pred(x))
}

Rust (functional fold)

pub fn partition_fold<T, 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); } else { no.push(x); }
        (yes, no)
    })
}

Rust (recursive)

pub fn partition_recursive<'a, T, F>(items: &'a [T], pred: &F) -> (Vec<&'a T>, Vec<&'a T>)
where
    F: Fn(&T) -> bool,
{
    match items {
        [] => (vec![], vec![]),
        [head, rest @ ..] => {
            let (mut yes, mut no) = partition_recursive(rest, pred);
            if pred(head) { yes.insert(0, head); } else { no.insert(0, head); }
            (yes, no)
        }
    }
}

Type Signatures

Concept	OCaml	Rust
Function signature	`val partition : ('a -> bool) -> 'a list -> 'a list * 'a list`	`fn partition_idiomatic<T, F>(items: &[T], pred: F) -> (Vec<&T>, Vec<&T>)`
List type	`'a list`	`&[T]` (borrowed slice)
Predicate	`'a -> bool`	`Fn(&T) -> bool`
Return type	`'a list * 'a list`	`(Vec<&T>, Vec<&T>)`
Tuple result	`let (small, big) = ...`	`let (small, big) = ...` (identical syntax)

Key Insights

Direct API parity: Iterator::partition and List.partition are conceptually identical — both take a predicate and return a pair of collections. The Rust API feels like a direct port.

Borrowing avoids copying: The Rust implementation returns Vec<&T> — references into the original slice. OCaml always produces new lists (cons cells) because lists are immutable and linked. Rust's borrow checker makes zero-copy partitioning safe and natural.

**Predicate takes &T not T:** In Rust, iterating over &[T] yields &T. The predicate must accept a reference. This is why the closure is |x| *x <= 5 (or |x: &i32| *x <= 5) rather than |x| x <= 5.

Lifetime threading in recursive form: The recursive Rust version requires an explicit lifetime 'a to connect the input slice lifetime to the output references. OCaml's GC handles this automatically — there is no concept of lifetimes.

Fold mirrors accumulator recursion: The fold version closely mirrors how you would manually implement List.partition in OCaml without pattern matching: carry two accumulators and decide which to extend at each step.

When to Use Each Style

**Use idiomatic Rust (Iterator::partition) when:** you have a slice or any iterator and want the simplest, most readable, most performant partition — this is the right default.

Use fold when: you want to be explicit about the accumulator pattern, or you are building a more complex partition (e.g., partitioning into more than two groups by accumulating differently).

Use recursive Rust when: you are teaching the OCaml parallel or need to process the slice head-first with early-termination logic not expressible with partition.

Open Source Repos

functional-rust

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

Rust