603 Fundamental

Functor Laws

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Functor Laws" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Functors are the fundamental abstraction for mapping over container types. Key difference from OCaml: 1. **HKT requirement**: These morphisms ideally require higher

Tutorial

The Problem

Functors are the fundamental abstraction for mapping over container types. A functor must satisfy two laws: identity (fmap id == id) and composition (fmap (f . g) == fmap f . fmap g). These laws ensure that mapping preserves structure. Rust's Iterator, Option, and Result are all functors. Understanding functor laws helps verify that custom collection types behave correctly when mapped over.

🎯 Learning Outcomes

• The categorical definition and the mathematical laws that must hold

• How to implement this pattern in Rust despite the lack of higher-kinded types

• The relationship to more familiar functional idioms (fold, unfold, map)

• Key concepts: map, fmap, identity and composition laws

• Where this pattern appears in production systems and when simpler alternatives suffice

Code Example

#![allow(clippy::all)]
//! # Functor Laws
//!
//! Functors must satisfy identity and composition laws.

/// Functor trait - map a function over a wrapped value.
pub trait Functor {
    type Inner;
    type Mapped<B>;
    fn fmap<B>(self, f: impl Fn(Self::Inner) -> B) -> Self::Mapped<B>;
}

impl<A> Functor for Option<A> {
    type Inner = A;
    type Mapped<B> = Option<B>;
    fn fmap<B>(self, f: impl Fn(A) -> B) -> Option<B> {
        self.map(f)
    }
}

impl<A> Functor for Vec<A> {
    type Inner = A;
    type Mapped<B> = Vec<B>;
    fn fmap<B>(self, f: impl Fn(A) -> B) -> Vec<B> {
        self.into_iter().map(f).collect()
    }
}

/// Identity law: fmap id == id
pub fn check_identity<F: Functor<Inner = A> + Clone + PartialEq, A: Clone>(fa: F) -> bool
where
    F::Mapped<A>: PartialEq<F>,
{
    let mapped = fa.clone().fmap(|x| x);
    mapped == fa
}

/// Composition law: fmap (g . f) == fmap g . fmap f
pub fn check_composition<A: Clone, B: Clone, C: PartialEq>(
    fa: Option<A>,
    f: impl Fn(A) -> B + Clone,
    g: impl Fn(B) -> C + Clone,
) -> bool {
    let left = fa.clone().map(|x| g(f(x)));
    let right = fa.map(f).map(g);
    left == right
}

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

    #[test]
    fn test_option_identity() {
        let opt = Some(42);
        let mapped = opt.clone().fmap(|x| x);
        assert_eq!(mapped, opt);
    }

    #[test]
    fn test_option_composition() {
        let opt = Some(5);
        let f = |x: i32| x * 2;
        let g = |x: i32| x + 1;
        assert!(check_composition(opt, f, g));
    }

    #[test]
    fn test_vec_functor() {
        let v = vec![1, 2, 3];
        let mapped = v.fmap(|x| x * 2);
        assert_eq!(mapped, vec![2, 4, 6]);
    }
}

(* Functor laws verification in OCaml *)
module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

module OptionFunctor : FUNCTOR with type 'a t = 'a option = struct
  type 'a t = 'a option
  let map = Option.map
end

module ListFunctor : FUNCTOR with type 'a t = 'a list = struct
  type 'a t = 'a list
  let map = List.map
end

(* Law verification *)
let identity_law fa =
  List.map Fun.id fa = fa

let composition_law f g fa =
  List.map (fun x -> g (f x)) fa = List.map g (List.map f fa)

let () =
  let xs = [1;2;3;4;5] in
  Printf.printf "identity law: %b\n" (identity_law xs);
  let f x = x * 2 in
  let g x = x + 1 in
  Printf.printf "composition law: %b\n" (composition_law f g xs)

Key Differences

HKT requirement: These morphisms ideally require higher-kinded types for full generality; Rust uses GATs or associated types as approximations.

Performance: Rust's implementations are more verbose but compile to efficient machine code; OCaml's implementations are more concise with similar runtime performance.

Practical adoption: In Haskell, recursive schemes from recursion-schemes are widely used; in Rust and OCaml, direct recursion is more common in practice.

Theoretical value: Understanding these patterns deepens intuition for all recursive programming, even when direct recursion is used in production code.

OCaml Approach

OCaml's pattern matching and recursive types make morphism implementations natural. The Fix type and F-algebra/coalgebra patterns translate directly, though without Haskell's typeclass machinery:

(* OCaml recursive schemes use:
   - Recursive variant types for F-algebras
   - Higher-order functions for the morphism
   - GADTs for type-safe fixed points in advanced cases *)

Full Source

#![allow(clippy::all)]
//! # Functor Laws
//!
//! Functors must satisfy identity and composition laws.

/// Functor trait - map a function over a wrapped value.
pub trait Functor {
    type Inner;
    type Mapped<B>;
    fn fmap<B>(self, f: impl Fn(Self::Inner) -> B) -> Self::Mapped<B>;
}

impl<A> Functor for Option<A> {
    type Inner = A;
    type Mapped<B> = Option<B>;
    fn fmap<B>(self, f: impl Fn(A) -> B) -> Option<B> {
        self.map(f)
    }
}

impl<A> Functor for Vec<A> {
    type Inner = A;
    type Mapped<B> = Vec<B>;
    fn fmap<B>(self, f: impl Fn(A) -> B) -> Vec<B> {
        self.into_iter().map(f).collect()
    }
}

/// Identity law: fmap id == id
pub fn check_identity<F: Functor<Inner = A> + Clone + PartialEq, A: Clone>(fa: F) -> bool
where
    F::Mapped<A>: PartialEq<F>,
{
    let mapped = fa.clone().fmap(|x| x);
    mapped == fa
}

/// Composition law: fmap (g . f) == fmap g . fmap f
pub fn check_composition<A: Clone, B: Clone, C: PartialEq>(
    fa: Option<A>,
    f: impl Fn(A) -> B + Clone,
    g: impl Fn(B) -> C + Clone,
) -> bool {
    let left = fa.clone().map(|x| g(f(x)));
    let right = fa.map(f).map(g);
    left == right
}

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

    #[test]
    fn test_option_identity() {
        let opt = Some(42);
        let mapped = opt.clone().fmap(|x| x);
        assert_eq!(mapped, opt);
    }

    #[test]
    fn test_option_composition() {
        let opt = Some(5);
        let f = |x: i32| x * 2;
        let g = |x: i32| x + 1;
        assert!(check_composition(opt, f, g));
    }

    #[test]
    fn test_vec_functor() {
        let v = vec![1, 2, 3];
        let mapped = v.fmap(|x| x * 2);
        assert_eq!(mapped, vec![2, 4, 6]);
    }
}

(* Functor laws verification in OCaml *)
module type FUNCTOR = sig
  type 'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

module OptionFunctor : FUNCTOR with type 'a t = 'a option = struct
  type 'a t = 'a option
  let map = Option.map
end

module ListFunctor : FUNCTOR with type 'a t = 'a list = struct
  type 'a t = 'a list
  let map = List.map
end

(* Law verification *)
let identity_law fa =
  List.map Fun.id fa = fa

let composition_law f g fa =
  List.map (fun x -> g (f x)) fa = List.map g (List.map f fa)

let () =
  let xs = [1;2;3;4;5] in
  Printf.printf "identity law: %b\n" (identity_law xs);
  let f x = x * 2 in
  let g x = x + 1 in
  Printf.printf "composition law: %b\n" (composition_law f g xs)

✓ Tests Rust test suite

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

    #[test]
    fn test_option_identity() {
        let opt = Some(42);
        let mapped = opt.clone().fmap(|x| x);
        assert_eq!(mapped, opt);
    }

    #[test]
    fn test_option_composition() {
        let opt = Some(5);
        let f = |x: i32| x * 2;
        let g = |x: i32| x + 1;
        assert!(check_composition(opt, f, g));
    }

    #[test]
    fn test_vec_functor() {
        let v = vec![1, 2, 3];
        let mapped = v.fmap(|x| x * 2);
        assert_eq!(mapped, vec![2, 4, 6]);
    }
}

Deep Comparison

Functor Laws

A Functor wraps a value and lets you map functions over it.

Laws

Identity: fmap id == id

Composition: fmap (g . f) == fmap g . fmap f

Rust Functors

• Option<T> - map over Some

• Vec<T> - map over elements

• Result<T, E> - map over Ok

Exercises

Laws verification: Write tests that verify the categorical laws for this morphism on a specific data type.

New data type: Apply the morphism to a different recursive data type (e.g., apply catamorphism to a rose tree instead of a binary tree).

Comparison: Implement the same computation using direct recursion and the morphism — measure whether the morphism version composes more cleanly.

Open Source Repos

functional-rust

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

Rust