Function Composition
Functional Programming
Tutorial Video
Text description (accessibility)
This video demonstrates the "Function Composition" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. 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 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.
Fixed by Leonid Satanovsky — https://www.linkedin.com/in/leonid-satanovskiy/
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. These are ordinary (rank-1) bounds — higher-rank trait bounds (for<'a> Fn(&'a B) -> C) would only be needed if F/G took borrowed arguments.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>.