005 Intermediate

List Filter From Scratch

Higher-Order FunctionsListsPredicates

Tutorial Video

Text description (accessibility)

This video demonstrates the "List Filter From Scratch" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Higher-Order Functions, Lists, Predicates. Implement a filter function that removes elements from a list that don't satisfy a given predicate (boolean test function). Key difference from OCaml: 1. **List representation:** OCaml uses cons lists (`h :: t`); Rust uses slices (`&[T]`)

Tutorial

The Problem

Implement a filter function that removes elements from a list that don't satisfy a given predicate (boolean test function). This is the fundamental operation for selecting a subset of elements while preserving order.

filter is the second pillar of list processing after map. It answers the question: "which elements satisfy this property?" Every SQL WHERE clause, every grep command, and every search feature in a UI implements filter. Building it from scratch — recursive pattern matching, then fold, then iterator — makes the abstraction concrete and shows the three levels of abstraction available in functional programming.

🎯 Learning Outcomes

• How to work with predicate functions (fn(&T) -> bool) in Rust

• Three approaches to filtering: idiomatic iterators, recursive pattern matching, and fold

• The role of .clone() when working with owned collections vs borrowed slices

• How Rust handles higher-order functions (functions that take functions as parameters)

• The trade-off between idiomatic Rust (iterators) and functional style (recursion)

🦀 The Rust Way

Rust provides three idiomatic paths:

Iterator chain (most idiomatic): items.iter().filter(...).cloned().collect() — leverages Rust's lazy iterators and standard library

Recursive pattern matching (closest to OCaml): matches on [h, rest @ ..] and recursively calls itself

Fold/accumulate (functional alternative): uses fold to build the result bottom-up

All three preserve order and handle empty lists correctly. The iterator version is preferred in production Rust because it avoids allocations during traversal.

Code Example

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

pub fn is_even(x: &i32) -> bool {
    x % 2 == 0
}

fn main() {
    let nums = vec![-2, -1, 0, 1, 2, 3, 4];
    let evens = filter(is_even, &nums);
    for n in evens {
        print!("{} ", n);
    }
    println!();
}

let rec filter p = function
  | []     -> []
  | h :: t ->
    let t' = filter p t in
    if p h then h :: t' else t'

let is_even x = x mod 2 = 0

let () =
  let nums = [-2; -1; 0; 1; 2; 3; 4] in
  List.iter (Printf.printf "%d ") (filter is_even nums); print_newline ()

Key Differences

List representation: OCaml uses cons lists (h :: t); Rust uses slices (&[T])

Recursion safety: OCaml's immutable recursion is safe by default; Rust requires fn(&T) to avoid mutable predicates

Cloning: Rust must .clone() elements when moving them into the result vector; OCaml lists share structure via references

Laziness: Rust iterators are lazy (elements processed on-demand); fold is eager (processes all elements immediately)

Function type: OCaml uses 'a -> bool for predicates; Rust uses fn(&T) -> bool (function pointer) or impl Fn(&T) -> bool (closure). Function pointers are faster than closures for inline predicates.

**Clone requirement:** Rust requires T: Clone to extract values from &[T] into a new owned Vec<T>. OCaml's GC handles sharing automatically.

Order: Both recursive implementations process elements front-to-back and preserve order. The fold-based version accumulates in order via push (not prepend), so no reversal is needed.

Predicate takes reference: filter(pred, items) in Rust passes &T to the predicate. In OCaml, List.filter passes the value directly.

OCaml Approach

OCaml's filter is recursive: it pattern-matches on the head and tail of the list, recursively filters the tail, and then conditionally prepends the head. This naturally preserves list order because the predicate is tested as each element is deconstructed.

Full Source

#![allow(clippy::all)]
/// Filter removes elements that don't satisfy the predicate.
/// Idiomatic Rust: uses iterator chains like the Rust standard library
pub fn filter<T: Clone>(predicate: fn(&T) -> bool, items: &[T]) -> Vec<T> {
    items.iter().filter(|x| predicate(x)).cloned().collect()
}

/// Filter using immutable recursion — closer to OCaml style.
/// Shows the explicit pattern matching on the list structure.
pub fn filter_recursive<T: Clone>(predicate: fn(&T) -> bool, items: &[T]) -> Vec<T> {
    match items {
        [] => vec![],
        [h, rest @ ..] => {
            let mut tail = filter_recursive(predicate, rest);
            if predicate(h) {
                let mut result = vec![h.clone()];
                result.append(&mut tail);
                result
            } else {
                tail
            }
        }
    }
}

/// Filter using fold/reduce pattern — functional accumulation.
/// Demonstrates left fold over the slice.
pub fn filter_fold<T: Clone>(predicate: fn(&T) -> bool, items: &[T]) -> Vec<T> {
    items.iter().fold(vec![], |mut acc, x| {
        if predicate(x) {
            acc.push(x.clone());
        }
        acc
    })
}

// Predicates
pub fn is_even(x: &i32) -> bool {
    x % 2 == 0
}

pub fn is_odd(x: &i32) -> bool {
    x % 2 != 0
}

pub fn is_positive(x: &i32) -> bool {
    *x > 0
}

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

    #[test]
    fn test_filter_empty() {
        let nums: Vec<i32> = vec![];
        assert_eq!(filter(is_even, &nums), vec![]);
    }

    #[test]
    fn test_filter_single() {
        assert_eq!(filter(is_even, &[2]), vec![2]);
        assert_eq!(filter(is_even, &[3]), vec![]);
    }

    #[test]
    fn test_filter_multiple() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        let evens = filter(is_even, &nums);
        assert_eq!(evens, vec![-2, 0, 2, 4]);
    }

    #[test]
    fn test_filter_all_pass() {
        let nums = vec![2, 4, 6];
        assert_eq!(filter(is_even, &nums), vec![2, 4, 6]);
    }

    #[test]
    fn test_filter_none_pass() {
        let nums = vec![1, 3, 5];
        let evens: Vec<i32> = filter(is_even, &nums);
        assert_eq!(evens, vec![]);
    }

    #[test]
    fn test_filter_positive() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        assert_eq!(filter(is_positive, &nums), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_filter_odd() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        assert_eq!(filter(is_odd, &nums), vec![-1, 1, 3]);
    }

    #[test]
    fn test_filter_recursive_multiple() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        let evens = filter_recursive(is_even, &nums);
        assert_eq!(evens, vec![-2, 0, 2, 4]);
    }

    #[test]
    fn test_filter_recursive_positive() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        assert_eq!(filter_recursive(is_positive, &nums), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_filter_fold_multiple() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        let evens = filter_fold(is_even, &nums);
        assert_eq!(evens, vec![-2, 0, 2, 4]);
    }

    #[test]
    fn test_filter_fold_positive() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        assert_eq!(filter_fold(is_positive, &nums), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_all_implementations_same() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        let idiomatic = filter(is_even, &nums);
        let recursive = filter_recursive(is_even, &nums);
        let fold = filter_fold(is_even, &nums);
        assert_eq!(idiomatic, recursive);
        assert_eq!(recursive, fold);
    }
}

(* Filter removes elements that don't satisfy the predicate *)
let rec filter p = function
  | []     -> []
  | h :: t ->
    let t' = filter p t in
    if p h then h :: t' else t'

(* Specialised predicates *)
let is_even x = x mod 2 = 0
let is_odd x = x mod 2 <> 0
let is_positive x = x > 0

let () =
  let nums = [-2; -1; 0; 1; 2; 3; 4] in
  List.iter (Printf.printf "%d ") (filter is_even nums); print_newline ();
  List.iter (Printf.printf "%d ") (filter is_positive nums); print_newline ()

✓ Tests Rust test suite

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

    #[test]
    fn test_filter_empty() {
        let nums: Vec<i32> = vec![];
        assert_eq!(filter(is_even, &nums), vec![]);
    }

    #[test]
    fn test_filter_single() {
        assert_eq!(filter(is_even, &[2]), vec![2]);
        assert_eq!(filter(is_even, &[3]), vec![]);
    }

    #[test]
    fn test_filter_multiple() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        let evens = filter(is_even, &nums);
        assert_eq!(evens, vec![-2, 0, 2, 4]);
    }

    #[test]
    fn test_filter_all_pass() {
        let nums = vec![2, 4, 6];
        assert_eq!(filter(is_even, &nums), vec![2, 4, 6]);
    }

    #[test]
    fn test_filter_none_pass() {
        let nums = vec![1, 3, 5];
        let evens: Vec<i32> = filter(is_even, &nums);
        assert_eq!(evens, vec![]);
    }

    #[test]
    fn test_filter_positive() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        assert_eq!(filter(is_positive, &nums), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_filter_odd() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        assert_eq!(filter(is_odd, &nums), vec![-1, 1, 3]);
    }

    #[test]
    fn test_filter_recursive_multiple() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        let evens = filter_recursive(is_even, &nums);
        assert_eq!(evens, vec![-2, 0, 2, 4]);
    }

    #[test]
    fn test_filter_recursive_positive() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        assert_eq!(filter_recursive(is_positive, &nums), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_filter_fold_multiple() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        let evens = filter_fold(is_even, &nums);
        assert_eq!(evens, vec![-2, 0, 2, 4]);
    }

    #[test]
    fn test_filter_fold_positive() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        assert_eq!(filter_fold(is_positive, &nums), vec![1, 2, 3, 4]);
    }

    #[test]
    fn test_all_implementations_same() {
        let nums = vec![-2, -1, 0, 1, 2, 3, 4];
        let idiomatic = filter(is_even, &nums);
        let recursive = filter_recursive(is_even, &nums);
        let fold = filter_fold(is_even, &nums);
        assert_eq!(idiomatic, recursive);
        assert_eq!(recursive, fold);
    }
}

Deep Comparison

OCaml vs Rust: List Filter

Side-by-Side Code

OCaml

let rec filter p = function
  | []     -> []
  | h :: t ->
    let t' = filter p t in
    if p h then h :: t' else t'

let is_even x = x mod 2 = 0

let () =
  let nums = [-2; -1; 0; 1; 2; 3; 4] in
  List.iter (Printf.printf "%d ") (filter is_even nums); print_newline ()

Rust (idiomatic)

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

pub fn is_even(x: &i32) -> bool {
    x % 2 == 0
}

fn main() {
    let nums = vec![-2, -1, 0, 1, 2, 3, 4];
    let evens = filter(is_even, &nums);
    for n in evens {
        print!("{} ", n);
    }
    println!();
}

Rust (recursive)

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

Type Signatures

Concept	OCaml	Rust
Filter function	`('a -> bool) -> 'a list -> 'a list`	`fn(fn(&T) -> bool, &[T]) -> Vec<T>`
Predicate	`'a -> bool`	`fn(&T) -> bool`
List type	`'a list`	`Vec<T>` or `&[T]`
Empty list	`[]`	`vec![]` or `[]` (pattern)
Cons	`h :: t`	`[h, rest @ ..]` (pattern)

Key Insights

Pattern matching equivalence: OCaml's h :: t directly maps to Rust's [h, rest @ ..] slice pattern. Both deconstruct lists into head and tail in a single match expression.

Ownership vs. sharing: OCaml lists are immutable and share structure via references; h :: t' reuses memory. Rust vectors must .clone() each element because vectors own their data. This is why the idiomatic Rust version collects into Vec<T> instead of building a linked list.

Function types as parameters: OCaml's 'a -> bool is a universal function type. Rust's fn(&T) -> bool is more restrictive—it requires a function pointer, not a closure. For general higher-order functions, Rust would use impl Fn(&T) -> bool or Box<dyn Fn(&T) -> bool>, but function pointers suffice here.

Idiomatic style divergence: OCaml recursion is the natural, encouraged pattern. Rust's idiomatic style favors iterators—they compose better, avoid stack depth issues, and integrate with the standard library. Recursion in Rust is a valid but secondary choice.

Predicate binding: In OCaml, the predicate p is bound once at the function's start. In Rust, we pass predicate: fn(&T) -> bool explicitly. This makes the dependency clearer and enables partial application via closures (though function pointers don't capture state).

When to Use Each Style

Use idiomatic Rust iterator when:

• You're filtering within a data pipeline (map, filter, fold chains)

• Performance matters (iterators may optimize better and avoid intermediate allocations)

• The predicate is simple or from the standard library (e.g., is_some, is_ok)

Use recursive Rust when:

• Teaching functional programming concepts or comparing directly with OCaml

• The predicate has complex control flow that reads better as pattern matches

• You need to preserve the functional recursion pattern for clarity

OCaml recursion is always natural because:

• Immutable data structures encourage recursion

• No stack depth concerns for typical list sizes

• Pattern matching is the primary control flow mechanism

Exercises

Implement reject — the inverse of filter: keep only elements for which the predicate returns false.

Write filter_map from scratch: apply a function f: T -> Option<U> to each element and collect only the Some results into a new Vec<U>.

Implement partition from scratch that splits a list into a pair (Vec<T>, Vec<T>) — elements satisfying the predicate and those that do not — in a single pass.

Open Source Repos

functional-rust

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

Rust