1124 Intermediate

1124-listfilter-select-elements-by-predicate — List.filter: Select Elements by Predicate

Functional Programming

Tutorial

The Problem

filter selects elements from a collection that satisfy a predicate, discarding the rest. It is the second pillar of functional data processing (alongside map and fold), appearing in every query language, data pipeline, and UI list filtering operation.

OCaml's List.filter and Rust's Iterator::filter both express this operation, but with different evaluation models and memory characteristics.

🎯 Learning Outcomes

• Use Iterator::filter with a predicate closure to select elements

• Implement recursive filter mirroring OCaml's List.filter structure

• Combine filter with map in a pipeline

• Understand the difference between filter (returns references) and filter_map (transforms while filtering)

• Apply filter to real data: removing None values, filtering by field value

Code Example

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

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

let rec filter_rec pred = function
  | [] -> []
  | x :: rest ->
    if pred x then x :: filter_rec pred rest
    else filter_rec pred rest

Key Differences

Double reference: Rust's iter().filter(|&&x| ...) requires double dereference due to the reference layer added by iter; using iter().copied().filter(|&x| ...) or iter().filter(|x| **x % 2 == 0) are alternatives.

Laziness: Rust's filter is lazy — it does not evaluate until consumed; OCaml's List.filter traverses the list immediately.

**filter_map**: Rust provides filter_map(|x| ...) for combined filter+transform; OCaml has List.filter_map in Base (not stdlib).

Memory: Rust's filter produces a new Vec after .collect(); OCaml's List.filter builds a new linked list.

OCaml Approach

let rec filter f = function
  | [] -> []
  | x :: rest -> if f x then x :: filter f rest else filter f rest

(* Standard library version *)
let filter_evens lst = List.filter (fun x -> x mod 2 = 0) lst

OCaml's List.filter traverses the list once, building a new list with only matching elements.

Full Source

#![allow(dead_code)]
//! List.filter — Select Elements by Predicate
//! See example.ml for OCaml reference
//!
//! OCaml's `List.filter pred xs` keeps only the elements for which `pred` returns true.
//! Rust's `Iterator::filter` is the direct equivalent.

/// Idiomatic Rust: filter a slice using an iterator adapter.
/// Mirrors OCaml: `List.filter pred xs`
pub fn filter<T: Clone, F>(items: &[T], pred: F) -> Vec<T>
where
    F: Fn(&T) -> bool,
{
    items.iter().filter(|x| pred(x)).cloned().collect()
}

/// Functional/recursive: keep elements matching pred by processing head and tail.
/// Mirrors OCaml pattern matching on the list spine.
pub fn filter_recursive<T: Clone, F>(items: &[T], pred: &F) -> Vec<T>
where
    F: Fn(&T) -> bool,
{
    match items {
        [] => vec![],
        [head, rest @ ..] => {
            let mut tail = filter_recursive(rest, pred);
            if pred(head) {
                // Prepend matching element to maintain original order.
                tail.insert(0, head.clone());
            }
            tail
        }
    }
}

/// Keep only even integers from a slice.
pub fn filter_evens(numbers: &[i32]) -> Vec<i32> {
    numbers.iter().filter(|&&x| x % 2 == 0).copied().collect()
}

/// Keep only odd integers from a slice.
pub fn filter_odds(numbers: &[i32]) -> Vec<i32> {
    numbers.iter().filter(|&&x| x % 2 != 0).copied().collect()
}

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

    #[test]
    fn test_filter_empty() {
        let empty: &[i32] = &[];
        assert_eq!(filter(empty, |_| true), vec![]);
        assert_eq!(filter(empty, |_| false), vec![]);
    }

    #[test]
    fn test_filter_single_match() {
        assert_eq!(filter(&[42_i32], |&x| x > 10), vec![42]);
    }

    #[test]
    fn test_filter_single_no_match() {
        assert_eq!(filter(&[3_i32], |&x| x > 10), vec![]);
    }

    #[test]
    fn test_filter_evens_and_odds() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8_i32];
        assert_eq!(filter_evens(&numbers), vec![2, 4, 6, 8]);
        assert_eq!(filter_odds(&numbers), vec![1, 3, 5, 7]);
    }

    #[test]
    fn test_filter_all_match() {
        let data = [1, 2, 3_i32];
        assert_eq!(filter(&data, |&x| x < 100), vec![1, 2, 3]);
    }

    #[test]
    fn test_filter_none_match() {
        let data = [10, 20, 30_i32];
        assert_eq!(filter(&data, |&x| x < 5), vec![]);
    }

    #[test]
    fn test_filter_recursive_matches_idiomatic() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8_i32];
        let pred = |x: &i32| x % 2 == 0;
        assert_eq!(filter(&numbers, pred), filter_recursive(&numbers, &pred));
    }

    #[test]
    fn test_filter_greater_than_threshold() {
        let data = [1, 2, 3, 4, 5_i32];
        assert_eq!(filter(&data, |&x| x > 3), vec![4, 5]);
    }
}

(* Idiomatic OCaml: List.filter keeps elements satisfying a predicate *)
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 OCaml: explicit pattern matching on list spine *)
let rec filter_rec pred = function
  | [] -> []
  | x :: rest ->
    if pred x then x :: filter_rec pred rest
    else filter_rec pred rest

let () =
  assert (evens = [2; 4; 6; 8]);
  assert (odds = [1; 3; 5; 7]);
  assert (List.filter (fun _ -> false) [1;2;3] = []);
  assert (List.filter (fun _ -> true) [1;2;3] = [1;2;3]);
  assert (filter_rec (fun x -> x > 3) [1;2;3;4;5] = [4;5]);
  print_endline "ok"

✓ Tests Rust test suite

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

    #[test]
    fn test_filter_empty() {
        let empty: &[i32] = &[];
        assert_eq!(filter(empty, |_| true), vec![]);
        assert_eq!(filter(empty, |_| false), vec![]);
    }

    #[test]
    fn test_filter_single_match() {
        assert_eq!(filter(&[42_i32], |&x| x > 10), vec![42]);
    }

    #[test]
    fn test_filter_single_no_match() {
        assert_eq!(filter(&[3_i32], |&x| x > 10), vec![]);
    }

    #[test]
    fn test_filter_evens_and_odds() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8_i32];
        assert_eq!(filter_evens(&numbers), vec![2, 4, 6, 8]);
        assert_eq!(filter_odds(&numbers), vec![1, 3, 5, 7]);
    }

    #[test]
    fn test_filter_all_match() {
        let data = [1, 2, 3_i32];
        assert_eq!(filter(&data, |&x| x < 100), vec![1, 2, 3]);
    }

    #[test]
    fn test_filter_none_match() {
        let data = [10, 20, 30_i32];
        assert_eq!(filter(&data, |&x| x < 5), vec![]);
    }

    #[test]
    fn test_filter_recursive_matches_idiomatic() {
        let numbers = [1, 2, 3, 4, 5, 6, 7, 8_i32];
        let pred = |x: &i32| x % 2 == 0;
        assert_eq!(filter(&numbers, pred), filter_recursive(&numbers, &pred));
    }

    #[test]
    fn test_filter_greater_than_threshold() {
        let data = [1, 2, 3, 4, 5_i32];
        assert_eq!(filter(&data, |&x| x > 3), vec![4, 5]);
    }
}

Deep Comparison

OCaml vs Rust: List.filter — Select Elements by Predicate

Side-by-Side Code

OCaml

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

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<T: Clone, F>(items: &[T], pred: F) -> Vec<T>
where
    F: Fn(&T) -> bool,
{
    items.iter().filter(|x| pred(x)).cloned().collect()
}

Rust (functional/recursive)

pub fn filter_recursive<T: Clone, F>(items: &[T], pred: &F) -> Vec<T>
where
    F: Fn(&T) -> bool,
{
    match items {
        [] => vec![],
        [head, rest @ ..] => {
            let mut tail = filter_recursive(rest, pred);
            if pred(head) {
                tail.insert(0, head.clone());
            }
            tail
        }
    }
}

Type Signatures

Concept	OCaml	Rust
filter	`('a -> bool) -> 'a list -> 'a list`	`fn filter<T: Clone, F>(items: &[T], pred: F) -> Vec<T>`
predicate type	`'a -> bool`	`F: Fn(&T) -> bool`
list type	`'a list`	`&[T]` (input slice), `Vec<T>` (output)
closure syntax	`fun x -> x mod 2 = 0`	`\\|x: &i32\\| x % 2 == 0`

Key Insights

Clone requirement: OCaml lists share structure (GC handles memory); Rust must clone() elements when moving them into a new Vec because ownership is explicit.

Borrowed input, owned output: Rust takes &[T] (borrowed slice) and returns Vec<T> (owned collection). OCaml's 'a list -> 'a list uses GC to share nodes.

Iterator chaining: Rust's .filter().cloned().collect() pipeline is lazy until .collect() — no intermediate allocations. OCaml allocates a new list node on every match.

Pattern matching: OCaml's | x :: rest -> is idiomatic list decomposition; Rust mirrors it with [head, rest @ ..] slice patterns (available since Rust 1.42).

Recursive tail position: OCaml's filter_rec is not tail-recursive (it builds the result on the way back up); the same applies to the Rust recursive version, risking stack overflow on very long slices.

When to Use Each Style

Use iterator filter when: working with slices or iterators in production code — it's idiomatic Rust and avoids manual recursion. Use recursive filter when: learning the OCaml↔Rust translation or when processing custom recursive data structures (trees, linked lists) where pattern matching on the structure is natural.

Exercises

Write partition_by<T, F: Fn(&T) -> bool>(list: &[T], pred: F) -> (Vec<T>, Vec<T>) using Iterator::partition.

Implement filter_map_result<T, E, F: Fn(T) -> Result<T, E>>(list: Vec<T>, f: F) -> (Vec<T>, Vec<E>).

Chain filter and map to extract all valid email domains from a list of strings: filter valid emails, map to extract the domain after @.

Open Source Repos

functional-rust

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

Rust