006 Intermediate

006 — Function Composition

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "006 — Function Composition" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Function composition is the mathematical operation of combining two functions `f` and `g` into `f ∘ g`, where `(f ∘ g)(x) = f(g(x))`. Key difference from OCaml: 1. **Built

Tutorial

The Problem

Function composition is the mathematical operation of combining two functions f and g into f ∘ g, where (f ∘ g)(x) = f(g(x)). It is the fundamental mechanism by which complex transformations are built from simple, reusable parts. Unix pipes (ls | grep foo | sort) are function composition in a shell. Promise chaining in JavaScript, method chaining in jQuery, and Spark's transformation DAGs are all manifestations of the same idea.

In purely functional languages like Haskell, (.) is a built-in operator: (f . g) x = f (g x). This enables point-free style where you define functions by composition without naming intermediate values. While Rust does not have a built-in composition operator, closures and iterator method chaining achieve the same expressive power.

🎯 Learning Outcomes

• Implement compose(f, g) that returns a new function applying g then f

• Implement pipe(f, g) that applies f then g (left-to-right reading order)

• Use Rust's iterator method chaining as idiomatic composition

• Build a pipeline function that applies a list of transformations in sequence

• Understand the mathematical definition: (f ∘ g)(x) = f(g(x))

• Implement a pipeline function that applies a slice of &dyn Fn(i64) -> i64 transformations sequentially using fold

Code Example

let result: i64 = data.iter()
    .map(|x| x * 2)
    .filter(|x| x > &5)
    .sum();

let result = data
  |> List.map (fun x -> x * 2)
  |> List.filter (fun x -> x > 5)
  |> List.fold_left ( + ) 0

Key Differences

Built-in operator: Haskell has (.), OCaml does not by default, Rust does not. All three require explicit definition or use of method chaining.

**Box<dyn Fn> overhead**: Rust needs a Box (heap allocation + vtable) to return composed closures because each closure is a different type. OCaml closures are heap-allocated by the GC with no explicit boxing.

Lifetime: Rust's composed function requires 'static bounds on the input functions if stored. OCaml closures capture environment via GC references with no lifetime constraints.

Method chaining vs composition: Rust's idiomatic style is iterator method chaining (.map().filter()), which reads left-to-right like OCaml's |>. Mathematical composition (f ∘ g) is less common in idiomatic Rust code.

Built-in operator: Haskell has (.), OCaml has no built-in compose (though |> serves as pipe). Rust has neither — both must be built from closures.

**Box<dyn Fn>:** Rust's composed closure has an unnameable type, requiring Box<dyn Fn(A) -> C> for storage and return. OCaml closures always have a uniform runtime representation.

**'static bound:** Rust's compose requires 'static because the closure may outlive its enclosing scope. OCaml closures capture environment automatically.

Method chaining as composition: Rust's .map().filter().sum() is function composition without naming intermediate values — the most idiomatic form.

Argument order: Mathematical f ∘ g applies g first, then f. OCaml's |> applies left-to-right. Rust's pipe also applies left-to-right — check which order your compose function uses.

OCaml Approach

OCaml does not have a built-in (.) composition operator in the standard library (unlike Haskell), but it is trivially defined: let (%) f g = fun x -> f (g x). The |> pipe operator serves as left-to-right composition for single values. Composing transformations on lists is done by piping: list |> List.map f |> List.filter g. Function composition is pervasive in OCaml because functions are naturally curried — List.map (fun x -> x + 1) |> List.filter (fun x -> x > 0) partially applies to create reusable pipeline stages.

Full Source

#![allow(clippy::all)]
/// Function Composition: building complex transformations from simple parts.
///
/// OCaml doesn't have a built-in composition operator (though `|>` serves similarly).
/// Rust also lacks one, but closures and method chaining achieve the same goal.

// ── Compose two functions ───────────────────────────────────────────────────

/// Compose f and g: returns a new function that applies g first, then f.
/// Equivalent to mathematical (f ∘ g)(x) = f(g(x))
pub fn compose<A, B, C>(
    f: impl Fn(B) -> C + 'static,
    g: impl Fn(A) -> B + 'static,
) -> Box<dyn Fn(A) -> C> {
    Box::new(move |x| f(g(x)))
}

/// Pipe-style compose: applies f first, then g. More natural reading order.
/// Equivalent to OCaml's `x |> f |> g`
pub fn pipe<A, B, C>(
    f: impl Fn(A) -> B + 'static,
    g: impl Fn(B) -> C + 'static,
) -> Box<dyn Fn(A) -> C> {
    Box::new(move |x| g(f(x)))
}

// ── Idiomatic Rust: method chaining via iterators ───────────────────────────

/// Process a list: double, keep evens, sum. Demonstrates iterator composition.
pub fn process(data: &[i64]) -> i64 {
    data.iter().map(|x| x * 2).filter(|x| x % 2 == 0).sum()
}

/// Build a transformation pipeline using fold over functions
pub fn pipeline(value: i64, steps: &[&dyn Fn(i64) -> i64]) -> i64 {
    steps.iter().fold(value, |acc, f| f(acc))
}

// ── Compose multiple functions ──────────────────────────────────────────────

/// Compose a vector of functions into a single function (right-to-left)
pub fn compose_all(funcs: Vec<Box<dyn Fn(i64) -> i64>>) -> Box<dyn Fn(i64) -> i64> {
    Box::new(move |x| funcs.iter().rev().fold(x, |acc, f| f(acc)))
}

/// Pipe a vector of functions (left-to-right)
pub fn pipe_all(funcs: Vec<Box<dyn Fn(i64) -> i64>>) -> Box<dyn Fn(i64) -> i64> {
    Box::new(move |x| funcs.iter().fold(x, |acc, f| f(acc)))
}

// ── Practical: string processing pipeline ───────────────────────────────────

/// Compose string transformations
pub fn process_string(s: &str) -> String {
    // Rust's method chaining IS composition
    s.trim()
        .to_lowercase()
        .replace("  ", " ")
        .chars()
        .filter(|c| c.is_alphanumeric() || *c == ' ')
        .collect()
}

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

    #[test]
    fn test_compose() {
        let double = |x: i64| x * 2;
        let inc = |x: i64| x + 1;
        let double_then_inc = compose(inc, double); // inc(double(x))
        assert_eq!(double_then_inc(5), 11); // 5*2=10, +1=11
    }

    #[test]
    fn test_pipe() {
        let double = |x: i64| x * 2;
        let inc = |x: i64| x + 1;
        let inc_then_double = pipe(inc, double); // double(inc(x))
        assert_eq!(inc_then_double(5), 12); // 5+1=6, *2=12
    }

    #[test]
    fn test_process_iterator_chain() {
        assert_eq!(process(&[1, 2, 3, 4, 5]), 30); // all doubled are even
        assert_eq!(process(&[]), 0);
        assert_eq!(process(&[7]), 14);
    }

    #[test]
    fn test_pipeline() {
        let add1: &dyn Fn(i64) -> i64 = &|x| x + 1;
        let mul2: &dyn Fn(i64) -> i64 = &|x| x * 2;
        let sub3: &dyn Fn(i64) -> i64 = &|x| x - 3;
        assert_eq!(pipeline(5, &[add1, mul2, sub3]), 9); // (5+1)*2-3=9
    }

    #[test]
    fn test_compose_all() {
        let funcs: Vec<Box<dyn Fn(i64) -> i64>> = vec![
            Box::new(|x| x + 1),
            Box::new(|x| x * 2),
            Box::new(|x| x - 3),
        ];
        // Right-to-left: (x-3)*2+1; for x=10: 7*2+1=15
        let f = compose_all(funcs);
        assert_eq!(f(10), 15);
    }

    #[test]
    fn test_pipe_all() {
        let funcs: Vec<Box<dyn Fn(i64) -> i64>> = vec![
            Box::new(|x| x + 1),
            Box::new(|x| x * 2),
            Box::new(|x| x - 3),
        ];
        // Left-to-right: ((x+1)*2)-3; for x=10: 11*2-3=19
        let f = pipe_all(funcs);
        assert_eq!(f(10), 19);
    }

    #[test]
    fn test_process_string() {
        assert_eq!(process_string("  Hello  WORLD!  "), "hello world");
        assert_eq!(process_string(""), "");
        assert_eq!(process_string("Rust 2024"), "rust 2024");
    }
}

(* Function Composition: building pipelines from simple functions *)

(* ── Composition operator (not built-in, but commonly defined) *)

let compose f g x = f (g x)   (* (f ∘ g)(x) = f(g(x)) *)
let ( >> ) f g x = g (f x)    (* pipe/forward composition *)

(* ── Basic examples ──────────────────────────────────────── *)

let double x = x * 2
let inc x = x + 1
let square x = x * x

let double_then_inc = compose inc double   (* inc(double(x)) *)
let inc_then_double = inc >> double        (* double(inc(x)) *)

(* ── Pipeline with |> (OCaml's most-used composition) ──── *)

let process data =
  data
  |> List.map (fun x -> x * 2)
  |> List.filter (fun x -> x mod 2 = 0)
  |> List.fold_left ( + ) 0

(* ── Compose a list of functions ─────────────────────────── *)

let compose_all funcs x =
  List.fold_right (fun f acc -> f acc) funcs x

let pipe_all funcs x =
  List.fold_left (fun acc f -> f acc) x funcs

(* ── Pipeline helper ─────────────────────────────────────── *)

let pipeline value steps =
  List.fold_left (fun acc f -> f acc) value steps

(* ── String processing ───────────────────────────────────── *)

let process_string s =
  s
  |> String.trim
  |> String.lowercase_ascii

(* ── Tests ────────────────────────────────────────────────── *)
let () =
  assert (double_then_inc 5 = 11);
  assert (inc_then_double 5 = 12);
  assert (process [1;2;3;4;5] = 30);
  assert (process [] = 0);
  assert (pipeline 5 [inc; double; (fun x -> x - 3)] = 9);
  assert (compose_all [inc; double; (fun x -> x - 3)] 10 = 15);
  assert (pipe_all [inc; double; (fun x -> x - 3)] 10 = 19);
  assert (process_string "  Hello  " = "hello");
  print_endline "✓ All composition tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_compose() {
        let double = |x: i64| x * 2;
        let inc = |x: i64| x + 1;
        let double_then_inc = compose(inc, double); // inc(double(x))
        assert_eq!(double_then_inc(5), 11); // 5*2=10, +1=11
    }

    #[test]
    fn test_pipe() {
        let double = |x: i64| x * 2;
        let inc = |x: i64| x + 1;
        let inc_then_double = pipe(inc, double); // double(inc(x))
        assert_eq!(inc_then_double(5), 12); // 5+1=6, *2=12
    }

    #[test]
    fn test_process_iterator_chain() {
        assert_eq!(process(&[1, 2, 3, 4, 5]), 30); // all doubled are even
        assert_eq!(process(&[]), 0);
        assert_eq!(process(&[7]), 14);
    }

    #[test]
    fn test_pipeline() {
        let add1: &dyn Fn(i64) -> i64 = &|x| x + 1;
        let mul2: &dyn Fn(i64) -> i64 = &|x| x * 2;
        let sub3: &dyn Fn(i64) -> i64 = &|x| x - 3;
        assert_eq!(pipeline(5, &[add1, mul2, sub3]), 9); // (5+1)*2-3=9
    }

    #[test]
    fn test_compose_all() {
        let funcs: Vec<Box<dyn Fn(i64) -> i64>> = vec![
            Box::new(|x| x + 1),
            Box::new(|x| x * 2),
            Box::new(|x| x - 3),
        ];
        // Right-to-left: (x-3)*2+1; for x=10: 7*2+1=15
        let f = compose_all(funcs);
        assert_eq!(f(10), 15);
    }

    #[test]
    fn test_pipe_all() {
        let funcs: Vec<Box<dyn Fn(i64) -> i64>> = vec![
            Box::new(|x| x + 1),
            Box::new(|x| x * 2),
            Box::new(|x| x - 3),
        ];
        // Left-to-right: ((x+1)*2)-3; for x=10: 11*2-3=19
        let f = pipe_all(funcs);
        assert_eq!(f(10), 19);
    }

    #[test]
    fn test_process_string() {
        assert_eq!(process_string("  Hello  WORLD!  "), "hello world");
        assert_eq!(process_string(""), "");
        assert_eq!(process_string("Rust 2024"), "rust 2024");
    }
}

Deep Comparison

Function Composition: OCaml vs Rust

The Core Insight

Composition is the essence of functional programming: build complex behavior by snapping together simple functions. OCaml expresses this through the pipe operator |> and custom composition operators. Rust achieves it through iterator method chaining, which is arguably even more natural for data processing pipelines.

OCaml Approach

OCaml's pipe operator |> is the workhorse for composition:

let result = data
  |> List.map (fun x -> x * 2)
  |> List.filter (fun x -> x > 5)
  |> List.fold_left ( + ) 0

Custom composition operators are easy to define:

let compose f g x = f (g x)
let ( >> ) f g x = g (f x)

Functions compose naturally because of automatic currying — List.map f returns a function ready to accept a list.

Rust Approach

Rust's iterator adapters ARE composition — each method returns a new iterator:

let result: i64 = data.iter()
    .map(|x| x * 2)
    .filter(|x| x > &5)
    .sum();

For explicit function composition, closures do the job:

fn compose<A,B,C>(f: impl Fn(B)->C, g: impl Fn(A)->B) -> impl Fn(A)->C {
    move |x| f(g(x))
}

Rust's zero-cost abstractions mean iterator chains compile to the same code as hand-written loops.

Key Differences

Aspect	OCaml	Rust
Pipe operator	`\\|>` (built-in)	No equivalent (method chaining instead)
Composition	Custom `compose` / `>>`	Closures or method chains
Iterator chains	`List.map f \\|> List.filter g`	`.map(f).filter(g)`
Lazy evaluation	Lists are eager	Iterators are lazy
Type inference	Full	Usually needs return type hints
Performance	Intermediate lists allocated	Zero-cost (fused into single pass)

What Rust Learners Should Notice

• **Method chaining replaces |>**: Rust's .map().filter().collect() is the idiomatic equivalent of OCaml's pipe chains. It reads left-to-right and composes naturally.

• Iterators are lazy: Unlike OCaml's List.map which creates a new list, Rust iterators don't allocate until .collect(). This is a major performance advantage.

• Explicit composition is rare in Rust: While you can build compose(f, g), idiomatic Rust prefers method chains or closures that call both functions inline.

• **Box<dyn Fn> vs impl Fn**: Composing functions dynamically requires Box<dyn Fn> (heap allocation). Static composition with impl Fn is zero-cost but can't be stored in collections.

Exercises

Compose three: Write compose3(f, g, h) that produces a function equivalent to f(g(h(x))). Then generalize to compose_all(fns: Vec<Box<dyn Fn(i64) -> i64>>) -> Box<dyn Fn(i64) -> i64> using fold.

Memoize: Write a memoize(f: impl Fn(i32) -> i32) -> impl FnMut(i32) -> i32 wrapper that caches results in a HashMap. How does this interact with composition?

Point-free pipeline: Define three small functions double, increment, square and compose them into a single transform: Box<dyn Fn(i64) -> i64> without calling any of them directly.

Memoize: Implement memoize<A: Hash + Eq + Clone, B: Clone>(f: impl Fn(A) -> B) -> impl Fn(A) -> B using a HashMap cache to avoid recomputing results for inputs already seen.

Retry combinator: Write retry<T, E>(f: impl Fn() -> Result<T, E>, n: usize) -> Result<T, E> that calls f up to n times, returning the first Ok or the last Err.

Open Source Repos

functional-rust

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

Rust

Tutorial Video

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Function Composition: OCaml vs Rust

The Core Insight

OCaml Approach

Rust Approach

Key Differences

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos