226 Expert

Category Basics

Functional Programming

Tutorial

The Problem

Category theory provides the mathematical foundation for functional programming abstractions — functors, monads, and natural transformations are all categorical concepts. A category consists of objects (types), morphisms (functions), composition (.), and identity (id). The category of types and functions (called Hask in Haskell, Typ in type theory) is the mathematical model that explains why Option, Result, and Vec all have map, and why and_then (bind) has its signature.

🎯 Learning Outcomes

• Understand the three components of a category: objects, morphisms, and composition

• Learn the identity and associativity laws for function composition

• See Rust's type system as the objects and functions as morphisms in a category

• Connect categorical composition to Rust's function composition combinator

Code Example

#![allow(clippy::all)]
// Example 226: Category Basics
// A category has objects, morphisms, composition, and identity.
// In Rust: types = objects, functions = morphisms.

// === Approach 1: Simple compose and identity functions ===

fn identity<A>(a: A) -> A {
    a
}

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

// === Approach 2: Category trait (explicit abstraction) ===

trait Category {
    type Obj;
    // We represent morphisms as boxed closures for flexibility
    fn id() -> Box<dyn Fn(Self::Obj) -> Self::Obj>;
    fn compose(
        f: Box<dyn Fn(Self::Obj) -> Self::Obj>,
        g: Box<dyn Fn(Self::Obj) -> Self::Obj>,
    ) -> Box<dyn Fn(Self::Obj) -> Self::Obj>;
}

struct FnCategoryI32;

impl Category for FnCategoryI32 {
    type Obj = i32;

    fn id() -> Box<dyn Fn(i32) -> i32> {
        Box::new(|x| x)
    }

    fn compose(f: Box<dyn Fn(i32) -> i32>, g: Box<dyn Fn(i32) -> i32>) -> Box<dyn Fn(i32) -> i32> {
        Box::new(move |x| f(g(x)))
    }
}

// === Approach 3: Kleisli category (a -> Option<b>) ===

fn kleisli_id<A>(a: A) -> Option<A> {
    Some(a)
}

fn kleisli_compose<A, B, C>(
    f: impl Fn(B) -> Option<C> + 'static,
    g: impl Fn(A) -> Option<B> + 'static,
) -> impl Fn(A) -> Option<C> {
    move |a| g(a).and_then(|b| f(b))
}

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

    #[test]
    fn test_compose_basic() {
        let f = |x: i32| x + 1;
        let g = |x: i32| x * 2;
        assert_eq!(compose(f, g)(5), 11);
    }

    #[test]
    fn test_identity_laws() {
        let f = |x: i32| x + 1;
        assert_eq!(compose(identity, f)(10), f(10));
        assert_eq!(compose(f, identity)(10), f(10));
    }

    #[test]
    fn test_associativity() {
        let f = |x: i32| x + 1;
        let g = |x: i32| x * 2;
        let h = |x: i32| x - 3;
        assert_eq!(compose(compose(f, g), h)(7), compose(f, compose(g, h))(7));
    }

    #[test]
    fn test_kleisli_compose() {
        let safe_div = |x: i32| -> Option<i32> {
            if x == 0 {
                None
            } else {
                Some(100 / x)
            }
        };
        let safe_succ = |x: i32| -> Option<i32> { Some(x + 1) };
        let k = kleisli_compose(safe_succ, safe_div);
        assert_eq!(k(5), Some(21));
        assert_eq!(k(0), None);
    }
}

(* Example 226: Category Basics *)
(* A category has objects, morphisms, composition, and identity *)

(* === Approach 1: Category as composition and identity === *)

(* In OCaml, types are objects and functions are morphisms.
   Composition is (.) and identity is Fun.id *)

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

(* Category laws:
   1. Left identity:  compose id f = f
   2. Right identity: compose f id = f
   3. Associativity:  compose (compose f g) h = compose f (compose g h) *)

let () =
  let f x = x + 1 in
  let g x = x * 2 in
  let h x = x - 3 in
  (* Left identity *)
  assert (compose id f 5 = f 5);
  (* Right identity *)
  assert (compose f id 5 = f 5);
  (* Associativity *)
  assert (compose (compose f g) h 10 = compose f (compose g h) 10);
  Printf.printf "Approach 1 - Category laws verified\n"

(* === Approach 2: Explicit Category module type === *)

module type CATEGORY = sig
  type ('a, 'b) morphism
  val id : ('a, 'a) morphism
  val compose : ('b, 'c) morphism -> ('a, 'b) morphism -> ('a, 'c) morphism
end

(* The category of OCaml types and functions *)
module FnCategory : CATEGORY with type ('a, 'b) morphism = 'a -> 'b = struct
  type ('a, 'b) morphism = 'a -> 'b
  let id x = x
  let compose f g x = f (g x)
end

let () =
  let open FnCategory in
  let f = fun x -> x + 1 in
  let g = fun x -> x * 2 in
  let result = compose f g 5 in
  assert (result = 11);
  assert (compose id f 5 = f 5);
  Printf.printf "Approach 2 - FnCategory works: compose (+1) (*2) 5 = %d\n" result

(* === Approach 3: Kleisli category (morphisms a -> 'b option) === *)

module KleisliOption = struct
  type ('a, 'b) morphism = 'a -> 'b option
  let id x = Some x
  let compose f g x =
    match g x with
    | None -> None
    | Some y -> f y
end

let () =
  let open KleisliOption in
  let safe_div x = if x = 0 then None else Some (100 / x) in
  let safe_succ x = Some (x + 1) in
  assert (compose safe_succ safe_div 5 = Some 21);
  assert (compose safe_succ safe_div 0 = None);
  (* Identity law *)
  assert (compose id safe_div 5 = safe_div 5);
  assert (compose safe_div id 5 = safe_div 5);
  Printf.printf "Approach 3 - Kleisli category verified\n"

let () = Printf.printf "✓ All tests passed\n"

Key Differences

Infix composition: Haskell uses . for compose; OCaml uses >> or |>; Rust uses compose(f, g) — named function, no infix operator.

Category laws: Both languages' compose and identity satisfy the laws by construction — they are mathematical truths, not runtime assertions.

Type system as category: The connection between the Rust type system and category theory enables reasoning about abstraction correctness.

Kleisli category: Functions A -> Option<B> form a different category (Kleisli category for Option) where composition is and_then — this is the mathematical model for monadic composition.

OCaml Approach

OCaml's standard library provides Fun.compose (since OCaml 4.08):

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

OCaml's pipeline operator |> is related: x |> f = f x. Function composition is idiomatic OCaml; category theory is explicitly taught in the OCaml community through libraries like Base.Fn.compose.

Full Source

#![allow(clippy::all)]
// Example 226: Category Basics
// A category has objects, morphisms, composition, and identity.
// In Rust: types = objects, functions = morphisms.

// === Approach 1: Simple compose and identity functions ===

fn identity<A>(a: A) -> A {
    a
}

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

// === Approach 2: Category trait (explicit abstraction) ===

trait Category {
    type Obj;
    // We represent morphisms as boxed closures for flexibility
    fn id() -> Box<dyn Fn(Self::Obj) -> Self::Obj>;
    fn compose(
        f: Box<dyn Fn(Self::Obj) -> Self::Obj>,
        g: Box<dyn Fn(Self::Obj) -> Self::Obj>,
    ) -> Box<dyn Fn(Self::Obj) -> Self::Obj>;
}

struct FnCategoryI32;

impl Category for FnCategoryI32 {
    type Obj = i32;

    fn id() -> Box<dyn Fn(i32) -> i32> {
        Box::new(|x| x)
    }

    fn compose(f: Box<dyn Fn(i32) -> i32>, g: Box<dyn Fn(i32) -> i32>) -> Box<dyn Fn(i32) -> i32> {
        Box::new(move |x| f(g(x)))
    }
}

// === Approach 3: Kleisli category (a -> Option<b>) ===

fn kleisli_id<A>(a: A) -> Option<A> {
    Some(a)
}

fn kleisli_compose<A, B, C>(
    f: impl Fn(B) -> Option<C> + 'static,
    g: impl Fn(A) -> Option<B> + 'static,
) -> impl Fn(A) -> Option<C> {
    move |a| g(a).and_then(|b| f(b))
}

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

    #[test]
    fn test_compose_basic() {
        let f = |x: i32| x + 1;
        let g = |x: i32| x * 2;
        assert_eq!(compose(f, g)(5), 11);
    }

    #[test]
    fn test_identity_laws() {
        let f = |x: i32| x + 1;
        assert_eq!(compose(identity, f)(10), f(10));
        assert_eq!(compose(f, identity)(10), f(10));
    }

    #[test]
    fn test_associativity() {
        let f = |x: i32| x + 1;
        let g = |x: i32| x * 2;
        let h = |x: i32| x - 3;
        assert_eq!(compose(compose(f, g), h)(7), compose(f, compose(g, h))(7));
    }

    #[test]
    fn test_kleisli_compose() {
        let safe_div = |x: i32| -> Option<i32> {
            if x == 0 {
                None
            } else {
                Some(100 / x)
            }
        };
        let safe_succ = |x: i32| -> Option<i32> { Some(x + 1) };
        let k = kleisli_compose(safe_succ, safe_div);
        assert_eq!(k(5), Some(21));
        assert_eq!(k(0), None);
    }
}

(* Example 226: Category Basics *)
(* A category has objects, morphisms, composition, and identity *)

(* === Approach 1: Category as composition and identity === *)

(* In OCaml, types are objects and functions are morphisms.
   Composition is (.) and identity is Fun.id *)

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

(* Category laws:
   1. Left identity:  compose id f = f
   2. Right identity: compose f id = f
   3. Associativity:  compose (compose f g) h = compose f (compose g h) *)

let () =
  let f x = x + 1 in
  let g x = x * 2 in
  let h x = x - 3 in
  (* Left identity *)
  assert (compose id f 5 = f 5);
  (* Right identity *)
  assert (compose f id 5 = f 5);
  (* Associativity *)
  assert (compose (compose f g) h 10 = compose f (compose g h) 10);
  Printf.printf "Approach 1 - Category laws verified\n"

(* === Approach 2: Explicit Category module type === *)

module type CATEGORY = sig
  type ('a, 'b) morphism
  val id : ('a, 'a) morphism
  val compose : ('b, 'c) morphism -> ('a, 'b) morphism -> ('a, 'c) morphism
end

(* The category of OCaml types and functions *)
module FnCategory : CATEGORY with type ('a, 'b) morphism = 'a -> 'b = struct
  type ('a, 'b) morphism = 'a -> 'b
  let id x = x
  let compose f g x = f (g x)
end

let () =
  let open FnCategory in
  let f = fun x -> x + 1 in
  let g = fun x -> x * 2 in
  let result = compose f g 5 in
  assert (result = 11);
  assert (compose id f 5 = f 5);
  Printf.printf "Approach 2 - FnCategory works: compose (+1) (*2) 5 = %d\n" result

(* === Approach 3: Kleisli category (morphisms a -> 'b option) === *)

module KleisliOption = struct
  type ('a, 'b) morphism = 'a -> 'b option
  let id x = Some x
  let compose f g x =
    match g x with
    | None -> None
    | Some y -> f y
end

let () =
  let open KleisliOption in
  let safe_div x = if x = 0 then None else Some (100 / x) in
  let safe_succ x = Some (x + 1) in
  assert (compose safe_succ safe_div 5 = Some 21);
  assert (compose safe_succ safe_div 0 = None);
  (* Identity law *)
  assert (compose id safe_div 5 = safe_div 5);
  assert (compose safe_div id 5 = safe_div 5);
  Printf.printf "Approach 3 - Kleisli category verified\n"

let () = Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_compose_basic() {
        let f = |x: i32| x + 1;
        let g = |x: i32| x * 2;
        assert_eq!(compose(f, g)(5), 11);
    }

    #[test]
    fn test_identity_laws() {
        let f = |x: i32| x + 1;
        assert_eq!(compose(identity, f)(10), f(10));
        assert_eq!(compose(f, identity)(10), f(10));
    }

    #[test]
    fn test_associativity() {
        let f = |x: i32| x + 1;
        let g = |x: i32| x * 2;
        let h = |x: i32| x - 3;
        assert_eq!(compose(compose(f, g), h)(7), compose(f, compose(g, h))(7));
    }

    #[test]
    fn test_kleisli_compose() {
        let safe_div = |x: i32| -> Option<i32> {
            if x == 0 {
                None
            } else {
                Some(100 / x)
            }
        };
        let safe_succ = |x: i32| -> Option<i32> { Some(x + 1) };
        let k = kleisli_compose(safe_succ, safe_div);
        assert_eq!(k(5), Some(21));
        assert_eq!(k(0), None);
    }
}

Exercises

Verify the identity law: write a test that compose(f, identity) == f for a specific function f.

Verify associativity: compose(h, compose(g, f)) == compose(compose(h, g), f) for concrete f, g, h.

Implement Kleisli composition kleisli_compose<A, B, C>(f: impl Fn(A) -> Option<B>, g: impl Fn(B) -> Option<C>) -> impl Fn(A) -> Option<C> and verify its laws.

Open Source Repos

functional-rust

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

Rust