ExamplesBy LevelBy TopicLearning Paths
1001 Intermediate
← 10011002 →

1001 — List Filter

Functional Programming

Tutorial

The Problem

Keep only elements of a list that satisfy a predicate. Implement three approaches: iterator-based filter_iter (idiomatic), filter_in_place using Vec::retain, and filter_recursive (functional style). Compare with OCaml's List.filter and a recursive implementation.

🎯 Learning Outcomes

  • • Use items.iter().filter(pred).cloned().collect() for filter-into-new-collection
  • • Use items.retain(pred) for in-place filtering without allocation
  • • Implement recursive filter with slice patterns and T: Clone
  • • Understand that .filter(pred) passes &&T when called on iter() — predicate receives &T
  • • Map Rust's retain to OCaml's List.filter (both O(n))
  • • Distinguish immutable filter (returns new vec) from mutable retain (modifies in place)

    • Code Example

    let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
let evens: Vec<_> = numbers.iter().filter(|x| x % 2 == 0).cloned().collect();

    Key Differences

    AspectRustOCaml
    Idiomatic.filter(pred).collect()List.filter pred lst
    In-placeVec::retain(pred)Not possible (immutable lists)
    Predicate arg&T (double ref from iter)T (value)
    Allocationcollect allocates; retain does notAlways allocates
    Lazinessfilter is lazyList.filter is eager
    filter_map.filter_map(f)List.filter_map f

    Vec::retain is a unique Rust capability — filtering in place with O(n) time and O(1) auxiliary space. It is the correct choice when you own the Vec and don't need to preserve the original.

    OCaml Approach

    List.filter (fun x -> x mod 2 = 0) numbers is the standard call. The custom recursive let rec filter_recursive pred lst = match lst with | [] -> [] | head :: tail -> if pred head then head :: filter_recursive pred tail else filter_recursive pred tail mirrors the logic exactly. OCaml lists are immutable, so all filtering creates a new list — no in-place equivalent exists.

    Full Source

    #![allow(clippy::all)]
//! List filtering: keep only elements satisfying a condition.
//!
//! This module demonstrates two approaches to filtering lists in Rust:
//! 1. **Idiomatic Rust** using iterators (lazy, composable, zero-copy)
//! 2. **Recursive** functional style (mimics OCaml's List.filter)

/// Filter a vector using iterators (idiomatic Rust).
///
/// Returns a new Vec containing only elements where the predicate returns true.
/// Uses the built-in `filter()` method for efficiency.
///
/// # Example
/// ```
/// use list_filter::filter_iter;
/// let numbers = vec![1, 2, 3, 4, 5];
/// let evens = filter_iter(&numbers, |x| x % 2 == 0);
/// assert_eq!(evens, vec![2, 4]);
/// ```
pub fn filter_iter<T: Clone>(items: &[T], predicate: impl Fn(&T) -> bool) -> Vec<T> {
    items.iter().filter(|x| predicate(x)).cloned().collect()
}

/// Filter a slice in-place using iterators.
///
/// Retains only elements where the predicate returns true.
/// Modifies the original vector.
///
/// # Example
/// ```
/// use list_filter::filter_in_place;
/// let mut numbers = vec![1, 2, 3, 4, 5];
/// filter_in_place(&mut numbers, |x| x % 2 == 0);
/// assert_eq!(numbers, vec![2, 4]);
/// ```
pub fn filter_in_place<T>(items: &mut Vec<T>, predicate: impl Fn(&T) -> bool) {
    items.retain(|x| predicate(x));
}

/// Filter a vector using recursion (functional, OCaml-style).
///
/// Returns a new Vec by recursively filtering the input.
/// Demonstrates functional programming idioms in Rust.
///
/// # Example
/// ```
/// use list_filter::filter_recursive;
/// let numbers = vec![1, 2, 3, 4, 5];
/// let odds = filter_recursive(&numbers, |x| x % 2 != 0);
/// assert_eq!(odds, vec![1, 3, 5]);
/// ```
pub fn filter_recursive<T: Clone>(items: &[T], predicate: impl Fn(&T) -> bool + Copy) -> Vec<T> {
    match items {
        [] => Vec::new(),
        [head, tail @ ..] => {
            let mut rest = filter_recursive(tail, predicate);
            if predicate(head) {
                let mut result = vec![head.clone()];
                result.append(&mut rest);
                result
            } else {
                rest
            }
        }
    }
}

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

    #[test]
    fn test_filter_iter_multiple_elements() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        let evens = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(evens, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_iter_odds() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        let odds = filter_iter(&numbers, |x| x % 2 != 0);
        assert_eq!(odds, vec![1, 3, 5, 7]);
    }

    #[test]
    fn test_filter_iter_empty() {
        let numbers: Vec<i32> = Vec::new();
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_iter_single_element_matches() {
        let numbers = vec![4];
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, vec![4]);
    }

    #[test]
    fn test_filter_iter_single_element_no_match() {
        let numbers = vec![3];
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_iter_all_match() {
        let numbers = vec![2, 4, 6, 8];
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_iter_none_match() {
        let numbers = vec![1, 3, 5, 7];
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_in_place_multiple_elements() {
        let mut numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        filter_in_place(&mut numbers, |x| x % 2 == 0);
        assert_eq!(numbers, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_in_place_empty() {
        let mut numbers: Vec<i32> = Vec::new();
        filter_in_place(&mut numbers, |x| x % 2 == 0);
        assert_eq!(numbers, Vec::new());
    }

    #[test]
    fn test_filter_in_place_single_match() {
        let mut numbers = vec![4];
        filter_in_place(&mut numbers, |x| x % 2 == 0);
        assert_eq!(numbers, vec![4]);
    }

    #[test]
    fn test_filter_in_place_single_no_match() {
        let mut numbers = vec![3];
        filter_in_place(&mut numbers, |x| x % 2 == 0);
        assert_eq!(numbers, Vec::new());
    }

    #[test]
    fn test_filter_recursive_multiple_elements() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        let evens = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(evens, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_recursive_odds() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        let odds = filter_recursive(&numbers, |x| x % 2 != 0);
        assert_eq!(odds, vec![1, 3, 5, 7]);
    }

    #[test]
    fn test_filter_recursive_empty() {
        let numbers: Vec<i32> = Vec::new();
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_recursive_single_element_matches() {
        let numbers = vec![4];
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, vec![4]);
    }

    #[test]
    fn test_filter_recursive_single_element_no_match() {
        let numbers = vec![3];
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_recursive_all_match() {
        let numbers = vec![2, 4, 6, 8];
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_recursive_none_match() {
        let numbers = vec![1, 3, 5, 7];
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_iter_with_strings() {
        let words = vec!["hello", "world", "a", "rust"];
        let long_words = filter_iter(&words, |w| w.len() > 1);
        assert_eq!(long_words, vec!["hello", "world", "rust"]);
    }

    #[test]
    fn test_filter_recursive_with_strings() {
        let words = vec!["hello", "world", "a", "rust"];
        let long_words = filter_recursive(&words, |w| w.len() > 1);
        assert_eq!(long_words, vec!["hello", "world", "rust"]);
    }

    #[test]
    fn test_filter_iter_and_recursive_equivalent() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        let evens_iter = filter_iter(&numbers, |x| x % 2 == 0);
        let evens_recursive = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(evens_iter, evens_recursive);
    }

    #[test]
    fn test_filter_with_complex_predicate() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        let result = filter_iter(&numbers, |x| x > &3 && x < &8);
        assert_eq!(result, vec![4, 5, 6, 7]);
    }
}
    ✓ Tests Rust test suite 
    #[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_filter_iter_multiple_elements() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        let evens = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(evens, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_iter_odds() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        let odds = filter_iter(&numbers, |x| x % 2 != 0);
        assert_eq!(odds, vec![1, 3, 5, 7]);
    }

    #[test]
    fn test_filter_iter_empty() {
        let numbers: Vec<i32> = Vec::new();
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_iter_single_element_matches() {
        let numbers = vec![4];
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, vec![4]);
    }

    #[test]
    fn test_filter_iter_single_element_no_match() {
        let numbers = vec![3];
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_iter_all_match() {
        let numbers = vec![2, 4, 6, 8];
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_iter_none_match() {
        let numbers = vec![1, 3, 5, 7];
        let result = filter_iter(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_in_place_multiple_elements() {
        let mut numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        filter_in_place(&mut numbers, |x| x % 2 == 0);
        assert_eq!(numbers, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_in_place_empty() {
        let mut numbers: Vec<i32> = Vec::new();
        filter_in_place(&mut numbers, |x| x % 2 == 0);
        assert_eq!(numbers, Vec::new());
    }

    #[test]
    fn test_filter_in_place_single_match() {
        let mut numbers = vec![4];
        filter_in_place(&mut numbers, |x| x % 2 == 0);
        assert_eq!(numbers, vec![4]);
    }

    #[test]
    fn test_filter_in_place_single_no_match() {
        let mut numbers = vec![3];
        filter_in_place(&mut numbers, |x| x % 2 == 0);
        assert_eq!(numbers, Vec::new());
    }

    #[test]
    fn test_filter_recursive_multiple_elements() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        let evens = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(evens, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_recursive_odds() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
        let odds = filter_recursive(&numbers, |x| x % 2 != 0);
        assert_eq!(odds, vec![1, 3, 5, 7]);
    }

    #[test]
    fn test_filter_recursive_empty() {
        let numbers: Vec<i32> = Vec::new();
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_recursive_single_element_matches() {
        let numbers = vec![4];
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, vec![4]);
    }

    #[test]
    fn test_filter_recursive_single_element_no_match() {
        let numbers = vec![3];
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_recursive_all_match() {
        let numbers = vec![2, 4, 6, 8];
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, vec![2, 4, 6, 8]);
    }

    #[test]
    fn test_filter_recursive_none_match() {
        let numbers = vec![1, 3, 5, 7];
        let result = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(result, Vec::new());
    }

    #[test]
    fn test_filter_iter_with_strings() {
        let words = vec!["hello", "world", "a", "rust"];
        let long_words = filter_iter(&words, |w| w.len() > 1);
        assert_eq!(long_words, vec!["hello", "world", "rust"]);
    }

    #[test]
    fn test_filter_recursive_with_strings() {
        let words = vec!["hello", "world", "a", "rust"];
        let long_words = filter_recursive(&words, |w| w.len() > 1);
        assert_eq!(long_words, vec!["hello", "world", "rust"]);
    }

    #[test]
    fn test_filter_iter_and_recursive_equivalent() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        let evens_iter = filter_iter(&numbers, |x| x % 2 == 0);
        let evens_recursive = filter_recursive(&numbers, |x| x % 2 == 0);
        assert_eq!(evens_iter, evens_recursive);
    }

    #[test]
    fn test_filter_with_complex_predicate() {
        let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
        let result = filter_iter(&numbers, |x| x > &3 && x < &8);
        assert_eq!(result, vec![4, 5, 6, 7]);
    }
}

    Deep Comparison

    Detailed Comparison: OCaml vs Rust List Filtering

    This document provides a side-by-side analysis of list filtering in OCaml and Rust, including code, type signatures, and key insights.

    Side-by-Side Code Comparison

    The Simplest Case: Built-in Filter

    **OCaml (using List.filter):**

    let numbers = [1; 2; 3; 4; 5; 6; 7; 8]
let evens = List.filter (fun x -> x mod 2 = 0) numbers

    **Rust (using .filter().collect()):**

    let numbers = vec![1, 2, 3, 4, 5, 6, 7, 8];
let evens: Vec<_> = numbers.iter().filter(|x| x % 2 == 0).cloned().collect();

    Observations:

  • • OCaml: One line, built-in function
  • • Rust: More explicit (iterator chain), but lazy until .collect()
  • • OCaml works with immutable linked lists; Rust works with contiguous arrays

    • Recursive Implementation

    OCaml:

    let rec filter_recursive pred lst =
  match lst with
  | [] -> []
  | head :: tail ->
      if pred head then
        head :: filter_recursive pred tail
      else
        filter_recursive pred tail

    Rust:

    pub fn filter_recursive<T: Clone>(items: &[T], pred: impl Fn(&T) -> bool + Copy) -> Vec<T> {
    match items {
        [] => Vec::new(),
        [head, tail @ ..] => {
            let mut rest = filter_recursive(tail, pred);
            if pred(head) {
                let mut result = vec![head.clone()];
                result.append(&mut rest);
                result
            } else {
                rest
            }
        }
    }
}

    Key Differences:

  • Pattern matching syntax:

    • - OCaml: [head :: tail] for cons pattern - Rust: [head, tail @ ..] for slice pattern (more explicit about reference)

  • List construction:

    • - OCaml: head :: rest (cheap, constant time cons) - Rust: Manual vec![head.clone()] then .append(&mut rest) (involves allocation)

  • Generic bounds:

    • - OCaml: Type inference handles 'a; closure type implicit - Rust: Explicit <T: Clone>, impl Fn(&T) -> bool + Copy

    Type Signatures Table

    AspectOCamlRust
    Filter function('a -> bool) -> 'a list -> 'a list<T: Clone>(pred: impl Fn(&T) -> bool) -> Vec<T>
    Closure type'a -> bool (implicit)Fn(&T) -> bool (trait bound)
    Input list'a list (linked)&[T] (slice/array)
    Output'a list (linked)Vec<T> (owned heap array)
    Predicate applicationpred x (value)pred(x) (reference)
    Cons operationh :: t (O(1))vec![h].append(&mut t) (O(n))
    Type inferenceFull polymorphism 'aGeneric bounds <T>

    Execution Model Differences

    OCaml: Evaluation Strategy

    List.filter pred [1; 2; 3]
→ matches 2 with pred?
→ if yes: 2 :: List.filter pred [3]
→ constructs linked-list node at each step
→ returns full list (eager)

    Characteristics:

  • • Eager evaluation (entire list constructed before return)
  • • Cheap cons (::) at each step
  • • Garbage collector cleans up intermediate nodes
  • • Natural recursion (list structure drives control flow)

    • Rust: Iterator Chain

    numbers.iter()          // Iterator<&T>
  .filter(|x| ...)      // FilterIter wrapper
  .cloned()             // ClonedIter wrapper
  .collect()            // consumes iterator, allocates Vec

    Characteristics:

  • • Lazy evaluation (iterator wrappers created, not evaluated until .collect())
  • • Zero intermediate allocations during chaining
  • • Borrowing prevents mutation during iteration
  • • Composable (.filter().map().take() = one pass)

    • Closure Semantics

    OCaml

    let x = 5
let pred = fun y -> y > x  (* x captured by closure *)
List.filter pred [1; 2; 3; 4; 5; 6]  (* [6] *)

    Closure rules:

  • • Captures variables from enclosing scope (immutable by default)
  • • No explicit capture syntax; implicit via free variables

    • Rust

    let x = 5;
let pred = |y: &i32| y > &x;  // x captured by shared borrow
vec![1, 2, 3, 4, 5, 6]
    .iter()
    .filter(pred)
    .cloned()
    .collect::<Vec<_>>()  // [6]

    Closure rules:

  • • Captures by reference (shared borrow by default)
  • • Move semantics available with move keyword
  • • Borrow checker ensures closure doesn't outlive captured variables

    • Performance Characteristics

    OperationOCamlRust
    Filter 1000 ints~0.1ms (GC overhead)~0.01ms (zero-copy)
    Chain filter+map2 passes (eager)1 pass (lazy)
    MemoryLinked list pointers (8 bytes per node)Contiguous Vec (8 bytes per int, dense)
    Cache localityPoor (pointer chasing)Excellent (contiguous)
    Cons operationO(1) allocationO(1)–O(n) depending on strategy

    Winner: Rust for large datasets due to cache locality and lazy iterator composition.

    5 Key Insights

    1. Lists vs Vectors: Data Structure Dictates Idiom

    OCaml's singly-linked list makes recursion feel natural:

    [1; 2; 3] ≡ 1 :: 2 :: 3 :: []

    Rust's Vec makes iterators natural:

    vec![1, 2, 3] ≡ [1, 2, 3] in contiguous memory

    Lesson: The data structure shapes how you think about problems. Rust's iterators are an API layer over contiguous arrays; OCaml's recursion is the structural reality of linked lists.

    2. Lazy vs Eager: Trade Compile Efficiency for Runtime Efficiency

    OCaml's List.filter is eager—it builds the entire result immediately.

    Rust's .filter() is lazy—it's a zero-cost wrapper that defers work until .collect().

    let iter = numbers.iter().filter(|x| x % 2 == 0);  // No filtering yet
let result = iter.collect::<Vec<_>>();  // Now it filters

    Lesson: Laziness allows composition without intermediate allocations. Rust's type system makes this free.

    3. Ownership Eliminates One Dimension of Confusion

    In OCaml, garbage collection handles cleanup implicitly. You never ask, "Who owns this list?"

    In Rust, ownership is explicit:

    let numbers = vec![1, 2, 3];  // I own this
let evens = filter_iter(&numbers, |x| x % 2 == 0);  // I borrow it
println!("{:?}", numbers);  // Still usable (borrow is over)

    Lesson: Explicit ownership prevents use-after-free bugs at compile time. It feels verbose initially but becomes a powerful invariant.

    4. Monomorphism vs Polymorphism: Specialization vs Generality

    OCaml is fully polymorphic. A function like List.filter works on any type:

    List.filter (fun x -> x > 0) [1; 2; 3]         (* ints *)
List.filter (fun x -> x > 0.0) [1.0; 2.0]      (* floats *)

    Rust uses monomorphization: each instantiation of a generic function gets a specialized version:

    filter_iter(&[1, 2, 3], |x| x > &0)      // Generates code for Vec<i32>
filter_iter(&[1.0, 2.0], |x| x > &0.0)  // Generates code for Vec<f64>

    Lesson: Monomorphization means no runtime dispatch overhead (the generic is as fast as hand-written code). The trade-off is compile time and binary size.

    5. Borrow Checker Prevents Entire Classes of Bugs

    OCaml doesn't prevent this:

    let lst = [1; 2; 3]
let iter = List.iter (fun x -> ...) lst
(* Somewhere else, if you mutate lst, the iter may break *)

    Rust prevents it:

    let mut numbers = vec![1, 2, 3];
let evens: Vec<_> = numbers.iter().filter(|x| x % 2 == 0).collect();
// numbers.push(4);  // ERROR: can't mutate while borrowed

    Lesson: The borrow checker is a feature, not a limitation. It catches data race bugs, use-after-free, and iterator invalidation at compile time.

    Summary Table: When to Use Each

    Use CaseOCamlRustWhy
    List processing (small)✅ Natural recursion⚠️ Iterators verboseLinked structure natural for OCaml
    Performance-critical filtering❌ GC overhead✅ Zero-copy iteratorsCache locality + laziness
    Polymorphic code✅ Implicit 'a⚠️ Explicit genericsOCaml's inference simpler
    Preventing mutations❌ Immutable by default, but no guarantee✅ Borrow checker enforcesRust's compile-time guarantee
    Teaching recursion✅ Clear, idiomatic⚠️ Slice patterns less obviousList structure matches algorithm

    Conclusion: OCaml and Rust solve the same problem with different idioms rooted in their data structures and memory models. Understanding why each language chooses its idiom teaches you more than the idiom itself.

    Exercises

  • Use filter_map to simultaneously filter and transform: keep only positive numbers and double them.
  • Implement partition_iter<T: Clone>(xs: &[T], pred: impl Fn(&T)->bool) -> (Vec<T>, Vec<T>) using filter + collect twice. Then compare with .partition(pred) for efficiency.
  • Write remove_duplicates<T: Eq + Hash>(xs: &[T]) -> Vec<&T> using a HashSet for membership tracking.
  • Chain filter + map + take(5) on an infinite range to find the first 5 primes.
  • In OCaml, implement filter_seq : ('a -> bool) -> 'a Seq.t -> 'a Seq.t for lazy filtering.

    • Open Source Repos

    functional-rust

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

    Rust