Теория категорий

Монады в теории категорий

«Монада - это моноид в категории эндофункторов» - когда-то этот афоризм казался загадкой. После этого урока он станет очевидным. Монады в теории категорий - не программистская выдумка, а фундаментальная алгебраическая структура, которую Эйленберг и Маклейн изучали задолго до Haskell. Они объясняют рекурсивные типы данных, сворачивание структур и «вычислительные эффекты» в едином языке.

**Рекурсивные типы данных**: начальные F-алгебры - это именно рекурсивные типы (List, Tree). Fold/catamorphism - единственный гомоморфизм из начальной алгебры. Это объясняет, почему fold «правильнее» explicit recursion
**Haskell do-notation**: монадические `do`-блоки - синтаксический сахар для клейсли-цепочек. IO-монада - алгебра над монадой IO; чистые функции - морфизмы в категории Клейсли
**Базы данных**: SQL-запрос - монадическая цепочка (flatMap для JOIN). Монада List моделирует реляционную алгебру: декартово произведение = (>>=) для списков

Предварительные знания

Adjoint Functors

Monad

«Монада - это моноид в категории эндофункторов» - эта формулировка пугает, но за ней стоит простая идея. Монада - это способ «оборачивать» объекты в контекст (Maybe, List, IO) с двумя операциями: «поместить в контекст» (unit/return) и «разгладить двойной контекст» (join/bind). Теория категорий делает это точным.

**Монада** на категории C - это тройка (T, η, μ), где T: C → C - эндофунктор, η: Id_C ⇒ T (единица, unit), μ: T² ⇒ T (умножение, join), удовлетворяющие аксиомам: μ ∘ Tη = μ ∘ ηT = Id_T (единица слева и справа) и μ ∘ Tμ = μ ∘ μT (ассоциативность).

**Монада как моноид**: категория эндофункторов [C, C] с тензорным произведением «∘» (композиция) - моноидальная категория. Монада - это именно **моноид в этой моноидальной категории**: объект T с морфизмами η: I → T (единица, I = тождественный функтор) и μ: T⊗T → T (умножение), удовлетворяющими аксиомам моноида. Отсюда и формулировка Маклейна.

Монада T	T(A)	η (unit)	μ (join)
Maybe	A \| null	a ↦ Just a	Just(Just a) ↦ Just a, rest ↦ Nothing
List	A[]	a ↦ [a]	[[a₁,...],[b₁,...]] ↦ [a₁,...,b₁,...]
Reader r	r → A	a ↦ const a	f: r→(r→A) ↦ r ↦ f(r)(r)
State s	s → (A × s)	a ↦ s ↦ (a, s)	join = выполнить внешнее, потом внутреннее
IO	«действие IO»	pure a	join = последовательное выполнение

Монады: от алгебры к программированию

Монады ввёл Роджер Годеман в 1958 году под названием «стандартные конструкции» в контексте гомологической алгебры. Независимо Маклейн использовал их как «тройки» (triples). В программирование монады ввёл Юджин Могги в 1989 году как способ моделировать вычислительные эффекты. Фил Уодлер popularized их для Haskell в 1992 году.

Что означает аксиома ассоциативности монады: μ ∘ Tμ = μ ∘ μT?

Kleisli

**Категория Клейсли** даёт способ «работать» с монадой так, как если бы T-вычисления были обычными функциями. Объекты - те же, что в C. Но морфизмы A → B в категории Клейсли - это морфизмы A → T(B) в C: «функции с эффектом». Композиция в Клейсли использует μ, чтобы «разгладить» двойной контекст.

**Категория Клейсли** C_T для монады (T, η, μ) имеет те же объекты, что C. Морфизм A →_T B в C_T - это морфизм A → T(B) в C. Тождественный морфизм A →_T A - это η_A: A → T(A). Композиция g ⋆ f (где f: A →_T B, g: B →_T C) - это μ_C ∘ T(g) ∘ f: A → T(C).

**Сопряжение из Клейсли**: функтор F_T: C → C_T отправляет A в A, а морфизм f: A → B в η_B ∘ f: A → T(B). Функтор G_T: C_T → C отправляет A в T(A), а клейсли-морфизм f: A →_T B в μ_B ∘ T(f): T(A) → T(B). Пара F_T ⊣ G_T - сопряжение, порождающее монаду T = G_T ∘ F_T. Это «наименьшее» сопряжение из всех, порождающих T.

В Haskell монадические вычисления пишутся именно в клейсли-стиле: `(>>=) :: m a -> (a -> m b) -> m b` - это клейсли-композиция. Нотация `do` - синтаксический сахар для клейсли-цепочек. Каждая монадическая функция `a -> m b` - это клейсли-морфизм.

В категории Клейсли для монады T, чем является тождественный морфизм A → A?

Eilenberg Moore

**Категория Эйленберга-Мура** - другой способ «распутать» монаду. Вместо Клейсли-морфизмов, она строит **алгебры монады**: объекты с операцией «свернуть контекст». T-алгебра над (T, η, μ) - это объект A с морфизмом α: T(A) → A, задающим «интерпретацию» контекста. Это «наибольшее» сопряжение, порождающее T.

**T-алгебра** (алгебра над монадой T) - это пара (A, α: T(A) → A), удовлетворяющая: α ∘ η_A = id_A (единица) и α ∘ μ_A = α ∘ T(α) (ассоциативность). Категория C^T алгебр над T - **категория Эйленберга-Мура**. Сопряжение F^T ⊣ G^T в C^T порождает ту же монаду T.

**Теорема Клейсли-Эйленберга-Мура**: любая монада T на C порождается сопряжением, причём таких сопряжений может быть много. Среди них есть наименьшее (категория Клейсли C_T) и наибольшее (категория Эйленберга-Мура C^T). Любое другое сопряжение, порождающее T, «вкладывается» между C_T и C^T.

Монада T	T-алгебра (A, α: T(A) → A)	Категория алгебр C^T
Maybe M(A) = A \| null	(A, α) где α(null) = default ∈ A	Указывающие множества (pointed sets)
List L(A) = A[]	(A, α: A[] → A)	Моноиды (с fold = concat+)
Writer (W,·)	(A, α: W×A → A)	W-множества (W действует на A)
State S(A) = s→(A×s)	Сложные алгебры состояний	Категория состояний

T-алгебра (A, α: T(A) → A) для монады List - это:

Algebras

**F-алгебры** и **F-коалгебры** - обобщение понятия алгебры в теории категорий. Для функтора F: C → C, F-алгебра - пара (A, α: F(A) → A), F-коалгебра - пара (A, α: A → F(A)). Это мощный подход к определению типов данных через их структуру: списки, деревья, потоки.

**Начальная F-алгебра** (initial algebra) - это F-алгебра (μF, in: F(μF) → μF), такая что для любой F-алгебры (A, α) существует единственный гомоморфизм (складка, fold): μF → A. **Конечная F-коалгебра** (final coalgebra) - двойственна: (νF, out: νF → F(νF)), принимающая любую коалгебру единственным образом.

**Теорема Ламбека**: начальная F-алгебра (μF, in) - это изоморфизм in: F(μF) ≅ μF. То есть μF является **неподвижной точкой** функтора F! Это формализует идею, что `List<A> = Nil | Cons(A, List<A>)` - рекурсивный тип данных как наименьшая неподвижная точка. Двойственно, конечная коалгебра - наибольшая неподвижная точка.

Функтор F	Начальная алгебра μF	Конечная коалгебра νF
F(X) = 1 + A × X	List<A> (конечные списки)	Stream<A> (бесконечные потоки)
F(X) = A + X × X	BinaryTree<A>	BinaryTree<A> (бесконечные деревья)
F(X) = 1 + X	ℕ (натуральные числа)	ℕ ∪ {∞} (расширенные)
F(X) = A × X^B	Бесконечные деревья с ветвлением B	Функции B* → A

Монада - это сложная абстракция, специфичная для Haskell

Монада - базовая категорная конструкция (эндофунктор с η и μ), встречающаяся везде: в алгебре, топологии, теории вычислений. Haskell просто сделал её явной

Примеры монад: Power Set (P, η: A ↦ {a}, μ: PP(A) → P(A) = объединение) - монада в Set. Любое сопряжение G ∘ F - монада. Монады формализуют «вычислительные эффекты» (Maybe = частичность, List = недетерминизм, IO = ввод/вывод) - не только программистская выдумка.

По теореме Ламбека, начальная F-алгебра (μF, in: F(μF) → μF) удовлетворяет:

Ключевые идеи

**Монада** (T, η, μ) - эндофунктор с единицей и умножением; аксиомы = аксиомы моноида в категории эндофункторов
**Категория Клейсли** C_T: морфизмы A → B - это A → T(B); идентичность = η; композиция использует μ
**Категория Эйленберга-Мура** C^T: объекты - T-алгебры (A, α: T(A)→A); порождает «наибольшее» сопряжение для T
**Начальная F-алгебра** μF ≅ F(μF) (теорема Ламбека) - рекурсивный тип данных как неподвижная точка функтора

Связанные темы

Монады - центральный узел теории категорий:

Монады в программировании — Следующий урок показывает конкретные монады (Maybe, List, IO) и трансформеры монад на практике
Сопряжённые функторы — Каждое сопряжение порождает монаду. Клейсли и Эйленберг-Мур - крайние случаи сопряжений для данной монады

Вопросы для размышления

Монада List - это «монада свободного моноида». Почему алгебры монады List - это именно моноиды? Выпишите аксиомы T-алгебры для List и сравните с аксиомами моноида.
Чем категория Клейсли отличается от категории Эйленберга-Мура для одной и той же монады? Приведите пример для Maybe-монады.
По теореме Ламбека, List<A> ≅ 1 + A × List<A>. Как это соотносится с рекурсивным определением типа данных в Haskell? Почему начальная алгебра - «наименьшая» неподвижная точка?

Связанные уроки