520 Intermediate

Higher-Order Functions

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Higher-Order Functions" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Higher-order functions (HOFs) — functions that take or return other functions — are the backbone of functional programming. Key difference from OCaml: 1. **Iterator vs recursion**: Rust HOFs operate on `Iterator` chains with lazy evaluation and optional collect; OCaml HOFs typically process `list` values recursively, though `Seq` provides laziness.

Tutorial

The Problem

Higher-order functions (HOFs) — functions that take or return other functions — are the backbone of functional programming. They emerged from lambda calculus (Alonzo Church, 1930s) and appeared in practical form in LISP, ML, and Haskell. Rust's iterator API is built entirely on HOFs: map, filter, fold, flat_map, zip. Beyond the standard library, custom HOFs like zip_with, scan_left, and group_by allow expressing complex data transformations as pipelines without intermediate allocations or imperative loops.

🎯 Learning Outcomes

• How to write custom higher-order functions using generic Fn bounds

• The difference between map/filter (element-wise) and fold/scan (accumulating)

• How zip_with generalizes zip + map into a single combining step

• How scan_left produces all intermediate fold values (useful for running totals)

• How to implement partition_by and group_by using closures as classifiers

Code Example

pub fn zip_with<A, B, C, F>(a: &[A], b: &[B], f: F) -> Vec<C>
where F: Fn(&A, &B) -> C {
    a.iter().zip(b.iter()).map(|(x, y)| f(x, y)).collect()
}

vec![1, 2, 3].iter().map(|&x| x * 2).collect::<Vec<_>>()

let zip_with f a b = List.map2 f a b
let scan_left f init = List.fold_left (fun (acc, xs) x ->
  let next = f acc x in (next, xs @ [next])) (init, [init])

List.map (fun x -> x * 2) [1; 2; 3]
List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4]
List.fold_left (+) 0 [1; 2; 3; 4; 5]

Key Differences

Iterator vs recursion: Rust HOFs operate on Iterator chains with lazy evaluation and optional collect; OCaml HOFs typically process list values recursively, though Seq provides laziness.

Zero-copy iteration: Rust &[T] slices avoid allocation in HOFs that don't need ownership; OCaml lists are always heap-allocated linked lists.

Trait bounds: Rust requires explicit Fn, FnMut, or FnOnce bounds on HOF parameters; OCaml infers the function type structurally without named bounds.

Return types: Rust HOFs returning impl Fn cannot name the concrete type; OCaml HOFs return plain function types that are fully transparent to the type checker.

OCaml Approach

OCaml's List module provides map, filter, fold_left, fold_right, and partition as stdlib HOFs. Custom combinators like zip_with and scan_left are straightforward to write and compose. OCaml's structural tail-call optimization makes recursive HOFs efficient without iterators.

let zip_with f xs ys = List.map2 f xs ys
let scan_left f init xs =
  List.fold_left (fun (acc, res) x ->
    let acc' = f acc x in (acc', acc' :: res)
  ) (init, [init]) xs |> snd |> List.rev

Full Source

#![allow(clippy::all)]
//! Higher-Order Functions
//!
//! Rust's iterator HOFs: map, filter, fold, flat_map, zip, and custom ones.

/// Custom HOF: zip two slices with a combining function.
pub fn zip_with<A, B, C, F>(a: &[A], b: &[B], f: F) -> Vec<C>
where
    F: Fn(&A, &B) -> C,
{
    a.iter().zip(b.iter()).map(|(x, y)| f(x, y)).collect()
}

/// Custom HOF: scan (like fold but returns all intermediate values).
pub fn scan_left<T: Clone, U: Clone, F>(items: &[T], init: U, f: F) -> Vec<U>
where
    F: Fn(U, &T) -> U,
{
    let mut acc = init;
    let mut result = vec![acc.clone()];
    for item in items {
        acc = f(acc, item);
        result.push(acc.clone());
    }
    result
}

/// Custom HOF: partition by predicate.
pub fn partition_by<T, P>(items: Vec<T>, pred: P) -> (Vec<T>, Vec<T>)
where
    P: Fn(&T) -> bool,
{
    items.into_iter().partition(pred)
}

/// Custom HOF: take while predicate holds.
pub fn take_while_custom<T, P>(items: &[T], pred: P) -> Vec<T>
where
    T: Clone,
    P: Fn(&T) -> bool,
{
    items.iter().take_while(|x| pred(x)).cloned().collect()
}

/// Custom HOF: group consecutive elements.
pub fn group_by<T: Clone + PartialEq>(items: &[T]) -> Vec<Vec<T>> {
    if items.is_empty() {
        return vec![];
    }
    let mut groups = vec![vec![items[0].clone()]];
    for item in items.iter().skip(1) {
        if groups.last().unwrap().last() == Some(item) {
            groups.last_mut().unwrap().push(item.clone());
        } else {
            groups.push(vec![item.clone()]);
        }
    }
    groups
}

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

    #[test]
    fn test_zip_with_add() {
        let a = [1, 2, 3];
        let b = [10, 20, 30];
        let result = zip_with(&a, &b, |x, y| x + y);
        assert_eq!(result, vec![11, 22, 33]);
    }

    #[test]
    fn test_zip_with_concat() {
        let a = ["a", "b"];
        let b = ["1", "2"];
        let result: Vec<String> = zip_with(&a, &b, |x, y| format!("{}{}", x, y));
        assert_eq!(result, vec!["a1", "b2"]);
    }

    #[test]
    fn test_scan_left_sum() {
        let nums = [1, 2, 3, 4];
        let result = scan_left(&nums, 0, |acc, &x| acc + x);
        assert_eq!(result, vec![0, 1, 3, 6, 10]);
    }

    #[test]
    fn test_partition_by() {
        let (evens, odds) = partition_by(vec![1, 2, 3, 4, 5, 6], |x| x % 2 == 0);
        assert_eq!(evens, vec![2, 4, 6]);
        assert_eq!(odds, vec![1, 3, 5]);
    }

    #[test]
    fn test_take_while_custom() {
        let nums = [1, 2, 3, 10, 4, 5];
        let result = take_while_custom(&nums, |&x| x < 5);
        assert_eq!(result, vec![1, 2, 3]);
    }

    #[test]
    fn test_group_by() {
        let items = [1, 1, 2, 2, 2, 3, 1, 1];
        let groups = group_by(&items);
        assert_eq!(groups, vec![vec![1, 1], vec![2, 2, 2], vec![3], vec![1, 1]]);
    }

    #[test]
    fn test_standard_hofs() {
        let nums = vec![1, 2, 3, 4, 5];

        // map
        let doubled: Vec<i32> = nums.iter().map(|&x| x * 2).collect();
        assert_eq!(doubled, vec![2, 4, 6, 8, 10]);

        // filter
        let evens: Vec<i32> = nums.iter().filter(|&&x| x % 2 == 0).cloned().collect();
        assert_eq!(evens, vec![2, 4]);

        // fold
        let sum: i32 = nums.iter().fold(0, |acc, &x| acc + x);
        assert_eq!(sum, 15);
    }
}

(* Higher-order functions in OCaml *)

(* Custom HOFs *)
let my_map f = List.map f
let my_filter pred = List.filter pred
let my_fold_left f init = List.fold_left f init
let my_for_all pred = List.for_all pred

(* Pipeline operator *)
let ( |> ) x f = f x

let () =
  let nums = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10] in

  (* Map *)
  let squares = List.map (fun x -> x * x) nums in
  Printf.printf "squares: [%s]\n" (String.concat ";" (List.map string_of_int squares));

  (* Filter *)
  let evens = List.filter (fun x -> x mod 2 = 0) nums in
  Printf.printf "evens: [%s]\n" (String.concat ";" (List.map string_of_int evens));

  (* Fold *)
  let sum = List.fold_left (+) 0 nums in
  Printf.printf "sum: %d\n" sum;

  (* Pipeline *)
  let result =
    nums
    |> List.filter (fun x -> x mod 2 = 0)
    |> List.map (fun x -> x * x)
    |> List.fold_left (+) 0
  in
  Printf.printf "sum of even squares: %d\n" result;

  (* any / all *)
  Printf.printf "any >5: %b\n" (List.exists (fun x -> x > 5) nums);
  Printf.printf "all >0: %b\n" (List.for_all (fun x -> x > 0) nums);

  (* flat_map *)
  let expanded = List.concat_map (fun x -> [x; x*10]) [1;2;3] in
  Printf.printf "flat_map: [%s]\n" (String.concat ";" (List.map string_of_int expanded))

✓ Tests Rust test suite

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

    #[test]
    fn test_zip_with_add() {
        let a = [1, 2, 3];
        let b = [10, 20, 30];
        let result = zip_with(&a, &b, |x, y| x + y);
        assert_eq!(result, vec![11, 22, 33]);
    }

    #[test]
    fn test_zip_with_concat() {
        let a = ["a", "b"];
        let b = ["1", "2"];
        let result: Vec<String> = zip_with(&a, &b, |x, y| format!("{}{}", x, y));
        assert_eq!(result, vec!["a1", "b2"]);
    }

    #[test]
    fn test_scan_left_sum() {
        let nums = [1, 2, 3, 4];
        let result = scan_left(&nums, 0, |acc, &x| acc + x);
        assert_eq!(result, vec![0, 1, 3, 6, 10]);
    }

    #[test]
    fn test_partition_by() {
        let (evens, odds) = partition_by(vec![1, 2, 3, 4, 5, 6], |x| x % 2 == 0);
        assert_eq!(evens, vec![2, 4, 6]);
        assert_eq!(odds, vec![1, 3, 5]);
    }

    #[test]
    fn test_take_while_custom() {
        let nums = [1, 2, 3, 10, 4, 5];
        let result = take_while_custom(&nums, |&x| x < 5);
        assert_eq!(result, vec![1, 2, 3]);
    }

    #[test]
    fn test_group_by() {
        let items = [1, 1, 2, 2, 2, 3, 1, 1];
        let groups = group_by(&items);
        assert_eq!(groups, vec![vec![1, 1], vec![2, 2, 2], vec![3], vec![1, 1]]);
    }

    #[test]
    fn test_standard_hofs() {
        let nums = vec![1, 2, 3, 4, 5];

        // map
        let doubled: Vec<i32> = nums.iter().map(|&x| x * 2).collect();
        assert_eq!(doubled, vec![2, 4, 6, 8, 10]);

        // filter
        let evens: Vec<i32> = nums.iter().filter(|&&x| x % 2 == 0).cloned().collect();
        assert_eq!(evens, vec![2, 4]);

        // fold
        let sum: i32 = nums.iter().fold(0, |acc, &x| acc + x);
        assert_eq!(sum, 15);
    }
}

Deep Comparison

OCaml vs Rust: Higher-Order Functions

OCaml

let zip_with f a b = List.map2 f a b
let scan_left f init = List.fold_left (fun (acc, xs) x ->
  let next = f acc x in (next, xs @ [next])) (init, [init])

List.map (fun x -> x * 2) [1; 2; 3]
List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4]
List.fold_left (+) 0 [1; 2; 3; 4; 5]

Rust

pub fn zip_with<A, B, C, F>(a: &[A], b: &[B], f: F) -> Vec<C>
where F: Fn(&A, &B) -> C {
    a.iter().zip(b.iter()).map(|(x, y)| f(x, y)).collect()
}

vec![1, 2, 3].iter().map(|&x| x * 2).collect::<Vec<_>>()

Key Differences

OCaml: List module with List.map, List.filter, etc.

Rust: Iterator trait methods: .map(), .filter(), .fold()

OCaml: Lazy by default in some contexts

Rust: Iterators are lazy, collect() to materialize

Both support chaining multiple HOFs

Exercises

**unfold**: Implement unfold<T, S, F>(seed: S, f: F) -> Vec<T> where F: Fn(S) -> Option<(T, S)> that generates a vector by repeatedly applying f until it returns None.

**chunk_by**: Write a HOF that groups elements into fixed-size chunks, returning a Vec<Vec<T>>, handling the remainder chunk if the length is not divisible.

**find_map**: Implement find_map<T, U, F>(items: &[T], f: F) -> Option<U> where F: Fn(&T) -> Option<U> that returns the first Some result from applying f to each element.

Open Source Repos

functional-rust

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

Rust