Category Theory
Monads in Programming
async/await, optional chaining `?.`, SQL JOIN, Rust's `?` - four constructs from four different languages, one mathematical object underneath. They are all bind for some monad. Once seen, the pattern replaces memorized tricks with composable structure.
- **async/await in JavaScript**: `await` is monadic bind for Promise. An `async function` returns a Promise (lifting into the IO monad). `Promise.all` is analogous to `sequence` for monads
- **Rust Result/Option**: the `?` operator is monadic bind. `Option::and_then` is Kleisli composition. `Result::map_err` is functorial mapping over the error side
- **GraphQL resolvers**: each resolver is a Kleisli morphism in a monad (context + possible error). DataLoader is a monad transformer for batching requests
Предварительные знания
Maybe
Maybe (or Option) is the simplest and most common monad. It models **partial computations**: functions that might not return a result. Instead of null-pointer exceptions or special error codes, Maybe makes the possibility of failure **explicit in the type**. A chain of Maybe computations automatically short-circuits on the first failure.
**The Maybe monad**: T(A) = Just(A) | Nothing. Unit η_A: A → Maybe A is Just. Multiplication μ: Maybe(Maybe A) → Maybe A flattens the nesting (Just(Just a) ↦ Just a, everything else ↦ Nothing). bind: `ma >>= f = case ma of Nothing → Nothing; Just a → f a`.
Maybe is a categorical object. In Set: the monad P(A) = A ∪ {⊥} with ⊥ as a special "failure value". In Haskell: `Maybe a = Nothing | Just a`. In Rust: `Option<T> = None | Some(T)`. In Swift: `Optional<T>`. The same monad everywhere-because it is a categorical construction, independent of the language.
| Operation | Maybe<A> | Explanation |
|---|---|---|
| return/pure a | Just a | Place a value in context (η) |
| Nothing >>= f | Nothing | Failure propagates (μ) |
| Just a >>= f | f(a) | Apply function to the value |
| fmap f (Just a) | Just (f a) | Transform inside the context |
| join (Just (Just a)) | Just a | Flatten double context (μ) |
**Monad axioms** for Maybe: 1. left unit: `return a >>= f = f(a)`, i.e., Just a >>= f = f(a) ✓ 2. right unit: `ma >>= return = ma`, i.e., Just a >>= Just = Just a, Nothing >>= Just = Nothing ✓ 3. associativity: `(ma >>= f) >>= g = ma >>= (a => f(a) >>= g)`, both paths through Nothing or Just agree ✓.
What happens to the chain `getUser(99) >>= getAddress >>= getCity` when getUser(99) = Nothing?
List
The List monad models **nondeterministic computations**: instead of one result, a function returns a list of possible results. bind for List is flatMap: apply the function to each element and concatenate the results. This is a powerful way to explore a space of alternatives.
**The List monad**: T(A) = [A] (list). Unit: a ↦ [a]. Multiplication (join): [[a₁,...], [b₁,...], ...] ↦ [a₁,..., b₁,...] (concatenation). bind: `xs >>= f = concatMap f xs = join(map f xs)`.
**Connection to algebra**: as we saw in ct-08, the T-algebras of the List monad are monoids. This is not a coincidence: List is the "free monoid monad". The Kleisli category for List is the category of binary relations (an arrow A →_List B is a subset of A × B). Kleisli composition = relational composition.
| Monadic operation | List | SQL analogy |
|---|---|---|
| return a | [a] | SELECT a (one row) |
| xs >>= f | concatMap f xs | JOIN xs ON f(x) |
| guard cond | if cond then [()] else [] | WHERE cond |
| mconcat xss | concat xss | UNION ALL |
| mzero / empty | [] | WHERE FALSE (zero rows) |
What does `[1,2,3] >>= (x => [x, x*x])` return in the List monad?
Io
The IO monad is the most important in Haskell: it separates "pure" computations (no side effects) from "impure" ones (I/O, state mutation). `IO a` is not a value of type A-it is a **description of an action** that, when executed, will produce A. The monadic structure allows actions to be sequenced without violating purity.
**The IO monad**: `IO A` is a description of a computation that produces A with possible side effects. `return a` creates an action that simply returns a with no effects. bind (>>=) sequences actions: the result of the first is passed to the second. The function `main :: IO ()` is the entry point that "runs" the entire chain.
**Categorical interpretation**: IO is a monad on Hask (the category of Haskell types). The unit η: A → IO A lifts pure values into IO. The multiplication μ: IO(IO A) → IO A executes the outer action, obtains an `IO A`, then executes the inner. This is sequential execution.
**Alternative approaches**: Free IO and Tagless Final represent IO through F-algebras explicitly. In Tagless Final, effects are described by type classes and the concrete monad is chosen at the last moment. Both approaches apply categorical ideas (F-algebras, initial algebras) to make the structure of effectful programs transparent.
Why does `IO<A>` in Haskell not violate the purity of functions, even though it describes effects?
Monad Transformers
In practice combining multiple effects is often necessary: partiality + state + logging + I/O. **Monad transformers** solve this: `MaybeT m a` is the Maybe monad "wrapped around" an arbitrary monad m. The result is a stack of effects: `MaybeT (StateT s IO) a` is a computation with state, possible failure, and IO.
A **monad transformer** MaybeT: (m: Monad) → Monad is defined as `MaybeT m a = m (Maybe a)`. It "lifts" Maybe semantics into any monad m. Similarly: `StateT s m a = s → m (a, s)`, `WriterT w m a = m (a, w)`, `ReaderT r m a = r → m a`.
| Transformer | Added effect | Example stack |
|---|---|---|
| MaybeT m a | Partiality (failure) | MaybeT IO a: IO with possible failure |
| EitherT e m a | Typed errors | EitherT String IO a: IO with errors |
| StateT s m a | Mutable state | StateT Cache IO a: IO with a cache |
| WriterT w m a | Logging (Monoid w) | WriterT [Log] IO a: IO with a log |
| ReaderT r m a | Immutable config | ReaderT Config IO a: IO with config |
**Alternatives to transformers**: in modern Haskell and other languages, **Tagless Final** and **Free Monads** are popular. Tagless Final: effects are described by type classes, the concrete monad is chosen at the last moment. Free Monad: an F-algebra over an "effect language", interpreted into an arbitrary monad. Both approaches apply categorical ideas (F-algebras, initial algebras).
Monads in programming are only about Haskell and functional programming
Monads appear in every language: Promise/async-await is the IO monad; Optional/nullable is Maybe; Observable is a List monad with time; Result/Either is the error monad
async/await in JS/TypeScript is do-notation for the Promise monad. `then` is `>>=`. `Promise.resolve` is `return`. Rust's `?` operator is a monadic bind for Result. Even null propagation `?.` is a monadic bind for Maybe. Monads are everywhere-just not always called by that name.
MaybeT IO a is:
Key Ideas
- **Maybe**: the monad of partial computations; the chain short-circuits on the first Nothing; the type-level analogue of null-safety
- **List**: the nondeterminism monad; bind = flatMap; relational queries = monadic computations over List
- **IO**: the monad of effect descriptions; IO<A> is "a program returning A"; purity is preserved by separating description from execution
- **Monad transformers** (MaybeT, StateT, WriterT) stack effects; modern alternatives are Tagless Final and Free Monads
Related Topics
Monads in programming connect to many concepts:
- Monads in Category Theory — The previous lesson: the mathematical foundation-an endofunctor with η and μ, the Kleisli and Eilenberg-Moore categories
- Category Theory in CS — Monads as the foundation of type theory and the denotational semantics of programming languages
Вопросы для размышления
- Implement the monad Result<A, E> = Ok(A) | Err(E) in TypeScript with operations return, bind, map, and mapErr. Verify that all three monad laws hold.
- async/await is syntactic sugar for Promise. Rewrite an async function without async/await, using only .then(), to make the Kleisli structure explicit.
- The transformer StateT s Maybe a = s → Maybe (a, s). When and why is such a stack needed? Come up with a problem for which this transformer is a perfect fit.