604 Expert

Monad Laws

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Monad Laws" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Monads extend functors with sequential composition. Key difference from OCaml: 1. **HKT requirement**: These morphisms ideally require higher

Tutorial

The Problem

Monads extend functors with sequential composition. Three laws must hold: left identity (return a >>= f == f a), right identity (m >>= return == m), and associativity ((m >>= f) >>= g == m >>= (f . (g =<<))). These laws ensure that monadic operations compose predictably. Option and Result in Rust satisfy these laws — and_then is monadic bind.

🎯 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: bind/and_then, pure/return, left identity, right identity, associativity

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

Code Example

#![allow(clippy::all)]
//! # Monad Laws
//!
//! Monads must satisfy left identity, right identity, and associativity.

/// Monad operations for Option.
pub trait OptionMonad<A> {
    fn pure(a: A) -> Self;
    fn bind<B>(self, f: impl FnOnce(A) -> Option<B>) -> Option<B>;
}

impl<A> OptionMonad<A> for Option<A> {
    fn pure(a: A) -> Self {
        Some(a)
    }
    fn bind<B>(self, f: impl FnOnce(A) -> Option<B>) -> Option<B> {
        self.and_then(f)
    }
}

/// Left identity: pure(a).bind(f) == f(a)
pub fn check_left_identity<A: Clone, B: PartialEq>(a: A, f: impl Fn(A) -> Option<B>) -> bool {
    let left = Option::pure(a.clone()).bind(&f);
    let right = f(a);
    left == right
}

/// Right identity: m.bind(pure) == m
pub fn check_right_identity<A: Clone + PartialEq>(m: Option<A>) -> bool {
    let left = m.clone().bind(Option::pure);
    left == m
}

/// Associativity: m.bind(f).bind(g) == m.bind(|x| f(x).bind(g))
pub fn check_associativity<A: Clone, B: Clone, C: PartialEq>(
    m: Option<A>,
    f: impl Fn(A) -> Option<B> + Clone,
    g: impl Fn(B) -> Option<C> + Clone,
) -> bool {
    let left = m.clone().bind(&f).bind(&g);
    let right = m.bind(|x| f(x).bind(&g));
    left == right
}

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

    #[test]
    fn test_left_identity() {
        let f = |x: i32| Some(x * 2);
        assert!(check_left_identity(5, f));
    }

    #[test]
    fn test_right_identity() {
        assert!(check_right_identity(Some(42)));
        assert!(check_right_identity(None::<i32>));
    }

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

    #[test]
    fn test_bind_chain() {
        let result = Some(5).bind(|x| Some(x + 1)).bind(|x| Some(x * 2));
        assert_eq!(result, Some(12));
    }
}

(* Monad laws in OCaml *)
let (>>=) = Option.bind
let return x = Some x

(* Left identity: return a >>= f == f a *)
let left_identity a f = (return a >>= f) = f a

(* Right identity: m >>= return == m *)
let right_identity m = (m >>= return) = m

(* Associativity: (m >>= f) >>= g == m >>= (fun x -> f x >>= g) *)
let associativity m f g =
  ((m >>= f) >>= g) = (m >>= fun x -> f x >>= g)

let () =
  let f x = if x > 0 then Some (x*2) else None in
  let g x = if x < 100 then Some (x+1) else None in
  Printf.printf "left_identity(5,f): %b\n"     (left_identity 5 f);
  Printf.printf "right_identity(Some 5): %b\n" (right_identity (Some 5));
  Printf.printf "right_identity(None): %b\n"   (right_identity None);
  Printf.printf "associativity: %b\n"          (associativity (Some 5) f g)

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)]
//! # Monad Laws
//!
//! Monads must satisfy left identity, right identity, and associativity.

/// Monad operations for Option.
pub trait OptionMonad<A> {
    fn pure(a: A) -> Self;
    fn bind<B>(self, f: impl FnOnce(A) -> Option<B>) -> Option<B>;
}

impl<A> OptionMonad<A> for Option<A> {
    fn pure(a: A) -> Self {
        Some(a)
    }
    fn bind<B>(self, f: impl FnOnce(A) -> Option<B>) -> Option<B> {
        self.and_then(f)
    }
}

/// Left identity: pure(a).bind(f) == f(a)
pub fn check_left_identity<A: Clone, B: PartialEq>(a: A, f: impl Fn(A) -> Option<B>) -> bool {
    let left = Option::pure(a.clone()).bind(&f);
    let right = f(a);
    left == right
}

/// Right identity: m.bind(pure) == m
pub fn check_right_identity<A: Clone + PartialEq>(m: Option<A>) -> bool {
    let left = m.clone().bind(Option::pure);
    left == m
}

/// Associativity: m.bind(f).bind(g) == m.bind(|x| f(x).bind(g))
pub fn check_associativity<A: Clone, B: Clone, C: PartialEq>(
    m: Option<A>,
    f: impl Fn(A) -> Option<B> + Clone,
    g: impl Fn(B) -> Option<C> + Clone,
) -> bool {
    let left = m.clone().bind(&f).bind(&g);
    let right = m.bind(|x| f(x).bind(&g));
    left == right
}

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

    #[test]
    fn test_left_identity() {
        let f = |x: i32| Some(x * 2);
        assert!(check_left_identity(5, f));
    }

    #[test]
    fn test_right_identity() {
        assert!(check_right_identity(Some(42)));
        assert!(check_right_identity(None::<i32>));
    }

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

    #[test]
    fn test_bind_chain() {
        let result = Some(5).bind(|x| Some(x + 1)).bind(|x| Some(x * 2));
        assert_eq!(result, Some(12));
    }
}

(* Monad laws in OCaml *)
let (>>=) = Option.bind
let return x = Some x

(* Left identity: return a >>= f == f a *)
let left_identity a f = (return a >>= f) = f a

(* Right identity: m >>= return == m *)
let right_identity m = (m >>= return) = m

(* Associativity: (m >>= f) >>= g == m >>= (fun x -> f x >>= g) *)
let associativity m f g =
  ((m >>= f) >>= g) = (m >>= fun x -> f x >>= g)

let () =
  let f x = if x > 0 then Some (x*2) else None in
  let g x = if x < 100 then Some (x+1) else None in
  Printf.printf "left_identity(5,f): %b\n"     (left_identity 5 f);
  Printf.printf "right_identity(Some 5): %b\n" (right_identity (Some 5));
  Printf.printf "right_identity(None): %b\n"   (right_identity None);
  Printf.printf "associativity: %b\n"          (associativity (Some 5) f g)

✓ Tests Rust test suite

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

    #[test]
    fn test_left_identity() {
        let f = |x: i32| Some(x * 2);
        assert!(check_left_identity(5, f));
    }

    #[test]
    fn test_right_identity() {
        assert!(check_right_identity(Some(42)));
        assert!(check_right_identity(None::<i32>));
    }

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

    #[test]
    fn test_bind_chain() {
        let result = Some(5).bind(|x| Some(x + 1)).bind(|x| Some(x * 2));
        assert_eq!(result, Some(12));
    }
}

Deep Comparison

Monad Laws

A Monad has pure (wrap) and bind (chain) operations.

Laws

Left Identity: pure(a).bind(f) == f(a)

Right Identity: m.bind(pure) == m

Associativity: m.bind(f).bind(g) == m.bind(|x| f(x).bind(g))

Rust Monads

• Option<T> - Some/and_then

• Result<T, E> - Ok/and_then

• Vec<T> - singleton/flat_map

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