Function Composition
Higher-Order FunctionsClosuresComposition
Tutorial Video
Text description (accessibility)
This video demonstrates the "Function Composition" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Higher-Order Functions, Closures, Composition. Write a function `compose` that takes two functions `f` and `g` and returns their composition—a new function that applies `g` first, then `f` to the result. Key difference from OCaml: 1. **Type Parameters:** OCaml infers everything; Rust requires explicit type parameters `A, B, C` for the domain and codomain.
Tutorial
The Problem
Write a function compose that takes two functions f and g and returns their composition—a new function that applies g first, then f to the result.
🎯 Learning Outcomes
🦀 The Rust Way
Rust uses higher-rank trait bounds to express composition. The compose function is generic over the function types F and G, and returns an impl Fn that captures both functions. This provides zero-cost abstraction—no runtime overhead.
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))
}
Code Example
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))
}
pub fn double(x: i32) -> i32 { 2 * x }
pub fn square(x: i32) -> i32 { x * x }
fn main() {
let square_then_double = compose(double, square);
println!("square_then_double 3 = {}", square_then_double(3)); // 18
println!("square_then_double 4 = {}", square_then_double(4)); // 32
}Key Differences
A, B, C for the domain and codomain.F: Fn(B) -> C and G: Fn(A) -> B to express that f and g are callable with specific signatures.impl Fn, which can be: - A closure capturing f and g
- A function pointer (less flexible but more concrete)
move captures are explicit; OCaml's closures capture implicitly.OCaml Approach
In OCaml, functions are first-class values. compose f g creates a new function by simply wrapping f (g x) in a closure. OCaml's type system infers the composition automatically.
let compose f g x = f (g x)
Full Source
#![allow(clippy::all)]
// Solution 1: Idiomatic Rust — compose as a higher-order function
// Takes two functions and returns a closure that applies them in sequence
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))
}
// Solution 2: Using function pointers — when you need a concrete type
// More restrictive than closures but gives an explicit function type
pub fn compose_fn<A, B, C>(f: fn(B) -> C, g: fn(A) -> B) -> impl Fn(A) -> C {
move |x| f(g(x))
}
// Helper functions matching the OCaml example
pub fn double(x: i32) -> i32 {
2 * x
}
pub fn square(x: i32) -> i32 {
x * x
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_compose_square_then_double_3() {
// square(3) = 9, double(9) = 18
let square_then_double = compose(double, square);
assert_eq!(square_then_double(3), 18);
}
#[test]
fn test_compose_square_then_double_4() {
// square(4) = 16, double(16) = 32
let square_then_double = compose(double, square);
assert_eq!(square_then_double(4), 32);
}
#[test]
fn test_compose_zero() {
// square(0) = 0, double(0) = 0
let square_then_double = compose(double, square);
assert_eq!(square_then_double(0), 0);
}
#[test]
fn test_compose_negative() {
// square(-2) = 4, double(4) = 8
let square_then_double = compose(double, square);
assert_eq!(square_then_double(-2), 8);
}
#[test]
fn test_compose_double_then_square() {
// Reverse order: double first, then square
let double_then_square = compose(square, double);
// double(3) = 6, square(6) = 36
assert_eq!(double_then_square(3), 36);
}
#[test]
fn test_compose_with_custom_functions() {
let add_one = |x: i32| x + 1;
let multiply_by_3 = |x: i32| x * 3;
// multiply_by_3 first, then add_one
let composed = compose(add_one, multiply_by_3);
// multiply_by_3(5) = 15, add_one(15) = 16
assert_eq!(composed(5), 16);
}
#[test]
fn test_compose_fn_pointers() {
// Using function pointers instead of closures
let square_then_double = compose_fn(double, square);
assert_eq!(square_then_double(3), 18);
}
}
✓ Tests
Rust test suite
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_compose_square_then_double_3() {
// square(3) = 9, double(9) = 18
let square_then_double = compose(double, square);
assert_eq!(square_then_double(3), 18);
}
#[test]
fn test_compose_square_then_double_4() {
// square(4) = 16, double(16) = 32
let square_then_double = compose(double, square);
assert_eq!(square_then_double(4), 32);
}
#[test]
fn test_compose_zero() {
// square(0) = 0, double(0) = 0
let square_then_double = compose(double, square);
assert_eq!(square_then_double(0), 0);
}
#[test]
fn test_compose_negative() {
// square(-2) = 4, double(4) = 8
let square_then_double = compose(double, square);
assert_eq!(square_then_double(-2), 8);
}
#[test]
fn test_compose_double_then_square() {
// Reverse order: double first, then square
let double_then_square = compose(square, double);
// double(3) = 6, square(6) = 36
assert_eq!(double_then_square(3), 36);
}
#[test]
fn test_compose_with_custom_functions() {
let add_one = |x: i32| x + 1;
let multiply_by_3 = |x: i32| x * 3;
// multiply_by_3 first, then add_one
let composed = compose(add_one, multiply_by_3);
// multiply_by_3(5) = 15, add_one(15) = 16
assert_eq!(composed(5), 16);
}
#[test]
fn test_compose_fn_pointers() {
// Using function pointers instead of closures
let square_then_double = compose_fn(double, square);
assert_eq!(square_then_double(3), 18);
}
}Deep Comparison
OCaml vs Rust: Function Composition
Side-by-Side Code
OCaml
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) (* 18 *)
Printf.printf "square_then_double 4 = %d\n" (square_then_double 4) (* 32 *)
Rust (idiomatic)
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))
}
pub fn double(x: i32) -> i32 { 2 * x }
pub fn square(x: i32) -> i32 { x * x }
fn main() {
let square_then_double = compose(double, square);
println!("square_then_double 3 = {}", square_then_double(3)); // 18
println!("square_then_double 4 = {}", square_then_double(4)); // 32
}
Rust (with function pointers)
pub fn compose_fn<A, B, C>(f: fn(B) -> C, g: fn(A) -> B) -> impl Fn(A) -> C {
move |x| f(g(x))
}
// Usage:
let square_then_double = compose_fn(double, square);
Type Signatures
| Concept | OCaml | Rust |
|---|---|---|
| Compose type | ('a -> 'b) -> ('c -> 'a) -> ('c -> 'b) | F: Fn(B) -> C, G: Fn(A) -> B |
| Return type | Implicit closure | impl Fn(A) -> C |
| Function type | int -> int | fn(i32) -> i32 |
| Closure capture | Automatic (lexical) | Explicit with move |
Key Insights
A, B, C) to represent the domain, intermediate value, and codomain. This explicitness is a feature—the types are clear to the compiler and all callers.F: Fn(B) -> C syntax is equivalent to OCaml's ('a -> 'b) annotation. The Fn trait allows Rust to accept any callable (closure, function pointer, or function item) as long as it has the right signature.impl Fn return type means Rust generates monomorphized code for each specific composition. There's no vtable or dynamic dispatch—the composition is inlined at compile time.move keyword explicitly captures f and g by ownership. In OCaml, this happens automatically. Rust's explicitness prevents accidental lifetime issues. - impl Fn (what we use here): maximally flexible, accepts any callable, zero overhead
- fn(A) -> B (function pointers): more restrictive, requires function items, still zero overhead
When to Use Each Style
**Use idiomatic Rust (impl Fn + closures) when:** You need maximum flexibility—accepting any callable (closures, function items, methods) and returning an efficient, inlined composition.
**Use function pointers (fn(A) -> B) when:** You specifically need to work with function items (not closures) and want a concrete, simple signature. This is less flexible but clearer in some contexts.
Use OCaml when: You want the ultimate simplicity and don't need the explicit type control that Rust provides. OCaml's implicit polymorphism is elegant for mathematical function composition.
Common Pitfalls (Rust)
| Pitfall | Example | Solution |
|---|---|---|
Forgetting move | \|x\| f(g(x)) might not compile | Add move to capture f and g by value |
| Wrong trait bound | Using Fn instead of FnOnce | Use Fn for functions called multiple times |
| Concrete function types | let c: fn(i32)->i32 = compose(double, square) | Use impl Fn return type instead |
Performance
Both implementations compile to identical machine code:
impl Fn, the composition is monomorphized and inlined—you get the same performance as hand-written move |x| f(g(x)).Exercises
compose3 function that chains three unary functions f, g, h so that compose3(f, g, h)(x) returns f(g(h(x))).compose_n that takes a Vec<Box<dyn Fn(i32) -> i32>> and returns a single composed function applying them right-to-left.Vec<String>.