052: Function Composition

Difficulty: 1 Level: Beginner Combine two functions into one: `compose(f, g)(x) = f(g(x))`.

The Problem This Solves

You have a `validate` function and a `trim` function. You want a single `clean` function that trims then validates. Without composition, you write `validate(trim(s))` everywhere — three names, nested syntax, reading right-to-left. Function composition solves this by building new functions from existing ones. `compose(validate, trim)` produces a single `clean` function you can store, pass around, and call without seeing the internals. When you add a `normalize` step later, you compose again rather than changing all the call sites. This is the functional programmer's version of a pipeline: instead of threading data through a sequence, you thread functions together first, then run the composed function once.

The Intuition

Mathematical composition: f∘g means "apply g, then f." `compose(f, g)` returns a new function that does exactly that. The argument order might feel backwards (`f` before `g` but `g` runs first) — that's the mathematical convention. If the backwards order bothers you, use `pipe(g, f)` instead: same result, argument order matches the data flow (left to right). `pipe(trim, validate)` reads as "trim first, then validate."

How It Works in Rust

// compose(f, g)(x) = f(g(x))  — mathematical convention (f applied last)
pub fn compose<A, B, C, F, G>(f: F, g: G) -> impl Fn(A) -> C
where
 F: Fn(B) -> C,
 G: Fn(A) -> B,
{
 move |x| f(g(x))  // f and g are moved into the closure
}

// pipe(g, f)(x) = f(g(x))  — data-flow convention (g applied first)
pub fn pipe<A, B, C, F, G>(g: G, f: F) -> impl Fn(A) -> C
where
 F: Fn(B) -> C,
 G: Fn(A) -> B,
{
 move |x| f(g(x))
}

// Trait extension: any Fn gets a .then_apply(next) method
pub trait Compose<A, B>: Fn(A) -> B + Sized {
 fn then_apply<C, H: Fn(B) -> C>(self, next: H) -> impl Fn(A) -> C {
     move |x| next(self(x))
 }
}
impl<A, B, F: Fn(A) -> B> Compose<A, B> for F {}

// Usage:
let square_then_double = compose(double, square);  // square first, double second
let square_then_double = square.then_apply(double); // method chain style

The `impl Fn` return type hides the concrete closure type, which the compiler knows but can't name. The `move` keyword is required because the returned closure lives beyond the function call.

What This Unlocks

Pipeline construction — compose a sequence of transformations once, reuse the resulting function everywhere.
Adapter pattern — wrap a function with pre/post-processing without touching its implementation.
Trait extension — adding `.then_apply` to any `Fn` shows how Rust traits enable expressive APIs.

Key Differences

Concept	OCaml	Rust
Syntax	`let compose f g x = f (g x)`	Explicit `move` closure required
Return type	Inferred polymorphic function	`impl Fn(A) -> C`
Partial application	`let f = compose double`	Requires explicit closure or `twice_partial`-style wrapper
Argument order	`compose f g` (f last, mathematical)	Same, or `pipe(g, f)` for data-flow order
Trait method	Not available	`.then_apply(next)` via trait extension

//! # Function Composition
//! OCaml CS3110 — Compose two functions into a pipeline: `compose f g x = f(g(x))`.

/// Idiomatic Rust: generic `compose` returns a closure, mirroring OCaml's `let compose f g x = f (g x)`.
///
/// The returned closure captures `f` and `g` by move, so they must be `'static` if stored.
pub fn compose<A, B, C, F, G>(f: F, g: G) -> impl Fn(A) -> C
where
    F: Fn(B) -> C,
    G: Fn(A) -> B,
{
    move |x| f(g(x))
}

/// Pipeline style: `pipe(g, f)` applies `g` first, then `f` — argument order mirrors a data pipeline.
///
/// This is `compose` with the arguments flipped, matching Rust's left-to-right reading convention.
pub fn pipe<A, B, C, F, G>(g: G, f: F) -> impl Fn(A) -> C
where
    F: Fn(B) -> C,
    G: Fn(A) -> B,
{
    move |x| f(g(x))
}

/// Trait-based composition: extend any `Fn` with a `.compose_with` combinator.
pub trait Compose<A, B>: Fn(A) -> B + Sized {
    /// Returns a new closure that applies `self` first, then `next`.
    fn then_apply<C, H: Fn(B) -> C>(self, next: H) -> impl Fn(A) -> C {
        move |x| next(self(x))
    }
}

impl<A, B, F: Fn(A) -> B> Compose<A, B> for F {}

// Standalone helpers used in tests and OCaml comparison.
pub fn double(x: i32) -> i32 {
    2 * x
}

pub fn square(x: i32) -> i32 {
    x * x
}

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

    // --- compose ---

    #[test]
    fn test_compose_square_then_double() {
        // OCaml: let square_then_double = compose double square
        let square_then_double = compose(double, square);
        assert_eq!(square_then_double(3), 18); // square(3)=9, double(9)=18
        assert_eq!(square_then_double(4), 32); // square(4)=16, double(16)=32
    }

    #[test]
    fn test_compose_double_then_square() {
        let double_then_square = compose(square, double);
        assert_eq!(double_then_square(3), 36); // double(3)=6, square(6)=36
    }

    #[test]
    fn test_compose_identity() {
        // Composing with identity leaves the function unchanged.
        let identity = |x: i32| x;
        let id_then_double = compose(double, identity);
        assert_eq!(id_then_double(5), 10);
    }

    // --- pipe ---

    #[test]
    fn test_pipe_square_then_double() {
        // pipe(g, f) = apply g first, then f — same result, clearer reading order.
        let square_then_double = pipe(square, double);
        assert_eq!(square_then_double(3), 18);
        assert_eq!(square_then_double(4), 32);
    }

    // --- trait-based ---

    #[test]
    fn test_then_apply_square_then_double() {
        let square_then_double = square.then_apply(double);
        assert_eq!(square_then_double(3), 18);
        assert_eq!(square_then_double(4), 32);
    }

    #[test]
    fn test_compose_with_closures() {
        // Works with anonymous closures, not just named functions.
        let add_one = |x: i32| x + 1;
        let times_three = |x: i32| x * 3;
        let f = compose(times_three, add_one); // add_one first, then times_three
        assert_eq!(f(4), 15); // add_one(4)=5, times_three(5)=15
    }
}

fn main() {
    println!("{:?}", square_then_double(3), 18);
    println!("{:?}", square_then_double(4), 32);
    println!("{:?}", double_then_square(3), 36);
}

let compose f g x = f (g x)
let double x = 2 * x
let square x = x * x
let square_then_double = compose double square
let () =
  Printf.printf "square_then_double 3 = %d\n" (square_then_double 3);
  Printf.printf "square_then_double 4 = %d\n" (square_then_double 4)

📊 Detailed Comparison

Comparison: Function Composition

OCaml — Curried compose

🐪 Show OCaml equivalent

let compose f g x = f (g x)
let square_then_double = compose double square
(* square_then_double 3 = 18 *)

Rust — Generic compose (direct translation)

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

let square_then_double = compose(double, square);
// square_then_double(3) == 18

Rust — Pipeline style (left-to-right argument order)

pub fn pipe<A, B, C, F, G>(g: G, f: F) -> impl Fn(A) -> C
where
 F: Fn(B) -> C,
 G: Fn(A) -> B,
{
 move |x| f(g(x))
}

let square_then_double = pipe(square, double);

Rust — Trait extension

let square_then_double = square.then_apply(double);
// square_then_double(3) == 18

Comparison Table

Aspect	OCaml	Rust
Return type	Inferred polymorphic `'a -> 'b`	Explicit `impl Fn(A) -> C`
Closure capture	Automatic	Requires `move` keyword
Partial application	Built-in currying	Returns explicit closure
Type parameters	Implicit (`'a`, `'b`)	Explicit (`A`, `B`, `C`)
Method chaining	Not built-in	Via trait extension
Argument order	Mathematical (f∘g)	Two conventions: compose or pipe