001 Intermediate

001 — Higher-Order Functions

Functional Programming

Tutorial

The Problem

Higher-order functions (HOFs) are the foundational abstraction of functional programming, rooted in lambda calculus from the 1930s. The core insight is that functions are values: they can be passed as arguments, returned from other functions, and stored in data structures. This eliminates entire categories of boilerplate loops.

The three pillars — map, filter, and fold — capture the three fundamental patterns of list processing: transforming every element, selecting some elements, and reducing a collection to a single value. Every non-trivial data pipeline in any language is a composition of these three operations. They appear in NumPy, Spark, SQL (SELECT, WHERE, GROUP BY), Hadoop MapReduce, and every stream-processing library.

HOFs eliminate the need for hand-written loops for 90% of data-processing tasks. When you see a Python for loop building a result list, it almost always hides a map or filter. Making this abstraction explicit enables parallel execution (data parallelism in Rayon uses the same map/filter/fold API), lazy evaluation, and composable pipelines that are impossible with raw loops.

🎯 Learning Outcomes

• Understand why functions-as-values eliminate boilerplate iteration

• Use map, filter, and fold/reduce on slices and iterators

• Implement recursive versions to understand the underlying mechanics

• Chain multiple higher-order functions into a single expressive pipeline

• Recognize when to use closures (|x| ...) vs named functions

• Distinguish between fold_left (left-to-right, tail-recursive in OCaml) and fold_right (right-to-left, not safe for large lists)

• Understand that Rust's Iterator::fold is always left-to-right and implemented as a loop

• Recognize that Rust's Iterator methods are zero-cost abstractions — the compiler inlines and optimizes them as efficiently as hand-written loops

Code Example

#![allow(clippy::all)]
// 001: Higher-Order Functions
// map, filter, fold — the three pillars of functional programming

// Approach 1: Using iterator methods
fn double_all(nums: &[i32]) -> Vec<i32> {
    nums.iter().map(|&x| x * 2).collect()
}

fn evens(nums: &[i32]) -> Vec<i32> {
    nums.iter().filter(|&&x| x % 2 == 0).copied().collect()
}

fn sum(nums: &[i32]) -> i32 {
    nums.iter().fold(0, |acc, &x| acc + x)
}

// Approach 2: Manual recursive implementations
fn my_map(f: fn(i32) -> i32, slice: &[i32]) -> Vec<i32> {
    if slice.is_empty() {
        vec![]
    } else {
        let mut result = vec![f(slice[0])];
        result.extend(my_map(f, &slice[1..]));
        result
    }
}

fn my_filter(pred: fn(i32) -> bool, slice: &[i32]) -> Vec<i32> {
    if slice.is_empty() {
        vec![]
    } else {
        let mut result = if pred(slice[0]) {
            vec![slice[0]]
        } else {
            vec![]
        };
        result.extend(my_filter(pred, &slice[1..]));
        result
    }
}

fn my_fold(f: fn(i32, i32) -> i32, acc: i32, slice: &[i32]) -> i32 {
    if slice.is_empty() {
        acc
    } else {
        my_fold(f, f(acc, slice[0]), &slice[1..])
    }
}

// Approach 3: Chained iterators
fn sum_of_doubled_evens(nums: &[i32]) -> i32 {
    nums.iter().filter(|&&x| x % 2 == 0).map(|&x| x * 2).sum()
}

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

    #[test]
    fn test_double_all() {
        assert_eq!(double_all(&[1, 2, 3]), vec![2, 4, 6]);
    }

    #[test]
    fn test_evens() {
        let nums: Vec<i32> = (1..=10).collect();
        assert_eq!(evens(&nums), vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn test_sum() {
        let nums: Vec<i32> = (1..=10).collect();
        assert_eq!(sum(&nums), 55);
    }

    #[test]
    fn test_my_map() {
        assert_eq!(my_map(|x| x + 1, &[1, 2, 3]), vec![2, 3, 4]);
    }

    #[test]
    fn test_my_filter() {
        assert_eq!(my_filter(|x| x > 3, &[1, 2, 3, 4, 5]), vec![4, 5]);
    }

    #[test]
    fn test_my_fold() {
        assert_eq!(my_fold(|a, b| a + b, 0, &[1, 2, 3]), 6);
    }

    #[test]
    fn test_sum_of_doubled_evens() {
        let nums: Vec<i32> = (1..=10).collect();
        assert_eq!(sum_of_doubled_evens(&nums), 60);
    }
}

(* 001: Higher-Order Functions *)
(* map, filter, fold — the three pillars of functional programming *)

(* Approach 1: Using standard library functions *)
let double_all lst = List.map (fun x -> x * 2) lst
let evens lst = List.filter (fun x -> x mod 2 = 0) lst
let sum lst = List.fold_left (fun acc x -> acc + x) 0 lst

(* Approach 2: Manual recursive implementations *)
let rec my_map f = function
  | [] -> []
  | x :: xs -> f x :: my_map f xs

let rec my_filter pred = function
  | [] -> []
  | x :: xs ->
    if pred x then x :: my_filter pred xs
    else my_filter pred xs

let rec my_fold_left f acc = function
  | [] -> acc
  | x :: xs -> my_fold_left f (f acc x) xs

(* Approach 3: Composition — combine HOFs *)
let sum_of_doubled_evens lst =
  lst
  |> List.filter (fun x -> x mod 2 = 0)
  |> List.map (fun x -> x * 2)
  |> List.fold_left ( + ) 0

(* Tests *)
let () =
  let nums = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] in
  assert (double_all [1; 2; 3] = [2; 4; 6]);
  assert (evens nums = [2; 4; 6; 8; 10]);
  assert (sum nums = 55);
  assert (my_map (fun x -> x + 1) [1; 2; 3] = [2; 3; 4]);
  assert (my_filter (fun x -> x > 3) [1; 2; 3; 4; 5] = [4; 5]);
  assert (my_fold_left ( + ) 0 [1; 2; 3] = 6);
  assert (sum_of_doubled_evens nums = 60);
  Printf.printf "✓ All tests passed\n"

Key Differences

Currying: OCaml functions are automatically curried; List.map f returns a new function. Rust requires explicit closures: v.iter().map(|&x| f(x)).

Laziness: Rust iterators are lazy — filter().map() does nothing until consumed by .collect() or .sum(). OCaml's List.map is eager and allocates immediately.

Ownership: Rust's iter() yields references (&T); you must use copied() or cloned() to get owned values. OCaml lists are garbage-collected so this distinction does not exist.

Double-dereference: Iterating a &[i32] yields &&i32 inside closures, requiring &&x patterns. OCaml pattern matching on lists always operates on direct values.

OCaml Approach

OCaml's List.map, List.filter, and List.fold_left/List.fold_right are the direct equivalents. Functions are curried by default, so List.map (fun x -> x * 2) partially applies to produce a new function waiting for its list argument. The |> pipe operator enables list |> List.filter even |> List.map double |> List.fold_left (+) 0 in natural reading order.

The distinction between List.fold_left (tail-recursive, safe) and List.fold_right (not tail-recursive) is a critical OCaml gotcha: always prefer fold_left for large lists. Similarly, Rust's Iterator::fold is always left-to-right and implemented as a loop with no stack risk.

Full Source

#![allow(clippy::all)]
// 001: Higher-Order Functions
// map, filter, fold — the three pillars of functional programming

// Approach 1: Using iterator methods
fn double_all(nums: &[i32]) -> Vec<i32> {
    nums.iter().map(|&x| x * 2).collect()
}

fn evens(nums: &[i32]) -> Vec<i32> {
    nums.iter().filter(|&&x| x % 2 == 0).copied().collect()
}

fn sum(nums: &[i32]) -> i32 {
    nums.iter().fold(0, |acc, &x| acc + x)
}

// Approach 2: Manual recursive implementations
fn my_map(f: fn(i32) -> i32, slice: &[i32]) -> Vec<i32> {
    if slice.is_empty() {
        vec![]
    } else {
        let mut result = vec![f(slice[0])];
        result.extend(my_map(f, &slice[1..]));
        result
    }
}

fn my_filter(pred: fn(i32) -> bool, slice: &[i32]) -> Vec<i32> {
    if slice.is_empty() {
        vec![]
    } else {
        let mut result = if pred(slice[0]) {
            vec![slice[0]]
        } else {
            vec![]
        };
        result.extend(my_filter(pred, &slice[1..]));
        result
    }
}

fn my_fold(f: fn(i32, i32) -> i32, acc: i32, slice: &[i32]) -> i32 {
    if slice.is_empty() {
        acc
    } else {
        my_fold(f, f(acc, slice[0]), &slice[1..])
    }
}

// Approach 3: Chained iterators
fn sum_of_doubled_evens(nums: &[i32]) -> i32 {
    nums.iter().filter(|&&x| x % 2 == 0).map(|&x| x * 2).sum()
}

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

    #[test]
    fn test_double_all() {
        assert_eq!(double_all(&[1, 2, 3]), vec![2, 4, 6]);
    }

    #[test]
    fn test_evens() {
        let nums: Vec<i32> = (1..=10).collect();
        assert_eq!(evens(&nums), vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn test_sum() {
        let nums: Vec<i32> = (1..=10).collect();
        assert_eq!(sum(&nums), 55);
    }

    #[test]
    fn test_my_map() {
        assert_eq!(my_map(|x| x + 1, &[1, 2, 3]), vec![2, 3, 4]);
    }

    #[test]
    fn test_my_filter() {
        assert_eq!(my_filter(|x| x > 3, &[1, 2, 3, 4, 5]), vec![4, 5]);
    }

    #[test]
    fn test_my_fold() {
        assert_eq!(my_fold(|a, b| a + b, 0, &[1, 2, 3]), 6);
    }

    #[test]
    fn test_sum_of_doubled_evens() {
        let nums: Vec<i32> = (1..=10).collect();
        assert_eq!(sum_of_doubled_evens(&nums), 60);
    }
}

(* 001: Higher-Order Functions *)
(* map, filter, fold — the three pillars of functional programming *)

(* Approach 1: Using standard library functions *)
let double_all lst = List.map (fun x -> x * 2) lst
let evens lst = List.filter (fun x -> x mod 2 = 0) lst
let sum lst = List.fold_left (fun acc x -> acc + x) 0 lst

(* Approach 2: Manual recursive implementations *)
let rec my_map f = function
  | [] -> []
  | x :: xs -> f x :: my_map f xs

let rec my_filter pred = function
  | [] -> []
  | x :: xs ->
    if pred x then x :: my_filter pred xs
    else my_filter pred xs

let rec my_fold_left f acc = function
  | [] -> acc
  | x :: xs -> my_fold_left f (f acc x) xs

(* Approach 3: Composition — combine HOFs *)
let sum_of_doubled_evens lst =
  lst
  |> List.filter (fun x -> x mod 2 = 0)
  |> List.map (fun x -> x * 2)
  |> List.fold_left ( + ) 0

(* Tests *)
let () =
  let nums = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] in
  assert (double_all [1; 2; 3] = [2; 4; 6]);
  assert (evens nums = [2; 4; 6; 8; 10]);
  assert (sum nums = 55);
  assert (my_map (fun x -> x + 1) [1; 2; 3] = [2; 3; 4]);
  assert (my_filter (fun x -> x > 3) [1; 2; 3; 4; 5] = [4; 5]);
  assert (my_fold_left ( + ) 0 [1; 2; 3] = 6);
  assert (sum_of_doubled_evens nums = 60);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_double_all() {
        assert_eq!(double_all(&[1, 2, 3]), vec![2, 4, 6]);
    }

    #[test]
    fn test_evens() {
        let nums: Vec<i32> = (1..=10).collect();
        assert_eq!(evens(&nums), vec![2, 4, 6, 8, 10]);
    }

    #[test]
    fn test_sum() {
        let nums: Vec<i32> = (1..=10).collect();
        assert_eq!(sum(&nums), 55);
    }

    #[test]
    fn test_my_map() {
        assert_eq!(my_map(|x| x + 1, &[1, 2, 3]), vec![2, 3, 4]);
    }

    #[test]
    fn test_my_filter() {
        assert_eq!(my_filter(|x| x > 3, &[1, 2, 3, 4, 5]), vec![4, 5]);
    }

    #[test]
    fn test_my_fold() {
        assert_eq!(my_fold(|a, b| a + b, 0, &[1, 2, 3]), 6);
    }

    #[test]
    fn test_sum_of_doubled_evens() {
        let nums: Vec<i32> = (1..=10).collect();
        assert_eq!(sum_of_doubled_evens(&nums), 60);
    }
}

Deep Comparison

Core Insight

Higher-order functions abstract iteration patterns. OCaml uses List.map, List.filter, List.fold_left on linked lists. Rust uses .iter().map(), .filter(), .fold() on iterator chains.

OCaml Approach

• List.map f lst applies f to every element

• List.filter pred lst keeps elements where pred is true

• List.fold_left f acc lst reduces left-to-right

• Functions are curried by default — partial application is free

Rust Approach

• .iter().map(|x| ...) with closures

• .iter().filter(|x| ...) — note double reference &&x

• .iter().fold(init, |acc, x| ...) — accumulator first

• Closures capture environment; Fn, FnMut, FnOnce traits

Comparison Table

Feature	OCaml	Rust
Map	`List.map f lst`	`.iter().map(\\|x\\| f(x))`
Filter	`List.filter p lst`	`.iter().filter(\\|x\\| p(x))`
Fold	`List.fold_left f a lst`	`.iter().fold(a, \\|acc, x\\| ...)`
Currying	Native	Closures returning closures
Evaluation	Eager (list)	Lazy (iterator chain)

Exercises

Compose map and filter: Write positive_doubled(nums: &[i32]) -> Vec<i32> that keeps only positive numbers and doubles them, using a single iterator chain with no intermediate Vec.

Fold-based map: Re-implement my_map using only fold (no recursion or explicit loops) to understand how fold generalizes all list operations.

Running totals: Write running_sum(nums: &[i32]) -> Vec<i32> that returns prefix sums [1, 3, 6, 10, ...] using Rust's .scan() — the stateful fold variant that emits intermediate accumulator values.

Parallel map: Explore how rayon's .par_iter().map(f).collect() has the same interface as sequential .iter().map(f).collect() but executes in parallel. Write a function signature that works with both.

Custom filter combinator: Implement filter_map(f: impl Fn(&T) -> Option<U>, slice: &[T]) -> Vec<U> which combines filtering and mapping in one pass — equivalent to OCaml's List.filter_map.

Open Source Repos

functional-rust

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

Rust