604: Monad Laws — Rust Deep Dive

The Problem This Solves

The Intuition

• `unit(value)` — start the line with a value (like `Some(x)` or `Ok(x)`)
• `bind(f)` — add a station: if the line is running, apply `f`; if it's stopped, propagate the stopped state

unit(a).bind(f)  ==  f(a)

m.bind(unit)  ==  m

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

How It Works in Rust

trait Monad: Sized {
 type Inner;               // the A in Option<A>
 type Wrapped<B>: Monad<Inner=B>;  // the Option<B> produced by bind
 fn unit(a: Self::Inner) -> Self;
 fn bind<B>(self, f: impl FnOnce(Self::Inner) -> Self::Wrapped<B>) -> Self::Wrapped<B>;
}

impl<A> Monad for Option<A> {
 type Inner = A;
 type Wrapped<B> = Option<B>;
 fn unit(a: A) -> Option<A> { Some(a) }
 fn bind<B>(self, f: impl FnOnce(A) -> Option<B>) -> Option<B> {
     self.and_then(f)   // bind IS and_then — no magic
 }
}

impl<A, E: Clone> Monad for Result<A, E> {
 type Inner = A;
 type Wrapped<B> = Result<B, E>;
 fn unit(a: A) -> Result<A, E> { Ok(a) }
 fn bind<B>(self, f: impl FnOnce(A) -> Result<B, E>) -> Result<B, E> {
     self.and_then(f)   // same: bind IS and_then
 }
}

// Law 1: unit(a).bind(f) == f(a)
fn left_identity<A: Clone, B: PartialEq>(a: A, f: impl Fn(A) -> Option<B> + Clone) -> bool {
 let left  = Option::unit(a.clone()).bind(f.clone());
 let right = f(a);
 left == right
}

// Law 2: m.bind(unit) == m
fn right_identity<A: PartialEq + Clone>(m: Option<A>) -> bool {
 m.clone().bind(Option::unit) == m
}

// Law 3: m.bind(f).bind(g) == m.bind(|x| f(x).bind(g))
fn 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.clone()).bind(g.clone());
 let right = m.bind(move |x| f(x).bind(g.clone()));
 left == right
}

let f = |x: i32| if x > 0 { Some(x*2) } else { None };
let g = |x: i32| if x < 100 { Some(x+1) } else { None };

assert!(left_identity(5, f));            // true: Some(5).bind(f) == f(5)
assert!(right_identity(Some(5)));        // true: Some(5).bind(Some) == Some(5)
assert!(right_identity(None::<i32>));    // true: None.bind(Some) == None
assert!(associativity(Some(5), f, g));   // true: grouping doesn't matter
assert!(associativity(None, f, g));      // true: None is transparent

// Rust's equivalent of Haskell's do-notation or OCaml's let*
fn compute(s: &str) -> Option<i32> {
 let n      = s.parse::<i32>().ok()?;         // bind step 1
 let doubled = if n > 0 { Some(n*2) } else { None }?;  // bind step 2
 Some(doubled + 1)                             // unit at the end
}
// Each ? is one monadic bind. This IS the do-notation pattern.

What This Unlocks

• Generic monadic code. With the `Monad` trait, you can write algorithms that work over any monad — `Option`, `Result`, or your own types — and the laws guarantee they'll compose correctly.
• Confident refactoring of pipelines. Law 3 (associativity) means you can extract any sub-chain from a larger pipeline into its own function without changing the result. This is the theoretical foundation for why `?`-based code refactors safely.
• Foundation for monad transformers. Stacking effects (e.g., `Option` + logging, or `Result` + state) requires knowing the laws hold for each layer. This pattern is the entry point to advanced effect composition in Rust.

Key Differences