Теория категорий
Категории: объекты и морфизмы
Опасное заявление: типы в Haskell, SQL-запросы к базе, электрические цепи, группы симметрий кристаллов - это математически одно и то же. Не метафора, не аналогия. Буквально одна структура. Эйленберг и Мак-Лейн в 1945 году искали способ описать «естественность» в топологии - и случайно создали язык, который объединяет половину математики под одной крышей. Haskell Functor, Monad, Applicative - это прямые кодировки теоркатных конструкций в типы. Гротендик использовал теорию категорий для доказательства теорем, которые иначе не поддавались никакому языку. Через 30 минут станет видно почему.
- **Haskell / Scala / Rust**: `Functor`, `Monad`, `Applicative` - не абстрактные паттерны, а точные кодировки категорных конструкций. `fmap` - это функтор, `>>=` - это монадный морфизм.
- **Компиляторы (GHC, LLVM)**: оптимизации типа «fusion» и «deforestation» - категорные законы, применяемые автоматически. Компилятор доказывает эквивалентность программ через морфизмы.
- **Базы данных**: реляционная алгебра (SELECT, JOIN, PROJECT) - это категория. Функторы между схемами - это SQL VIEW и schema migration.
- **Квантовые вычисления**: квантовые схемы - морфизмы в категории Гильбертовых пространств. ZX-calculus - буквально теория категорий для квантового железа.
- **Теория типов и proof assistants**: Coq, Agda, Lean основаны на изоморфизме Карри-Говарда-Ламбека: типы = объекты, программы = морфизмы, доказательства = термы.
Категория
Математика умеет изучать объекты изнутри: смотреть на элементы множества, на точки пространства, на биты структуры данных. Теория категорий делает ровно противоположное. Объекты здесь - чёрные ящики. Никакого содержимого. Только **стрелки** - морфизмы - которые идут от одного объекта к другому. И именно из паутины этих стрелок вся информация об объекте и складывается.
Категория C состоит из трёх компонентов: 1. класс объектов Ob(C) 2. для каждой пары объектов A, B - множество морфизмов Hom(A, B) 3. операция композиции морфизмов, удовлетворяющая аксиомам ассоциативности и существования identity.
| Категория | Объекты | Морфизмы |
|---|---|---|
| **Set** | Множества | Функции между множествами |
| **Grp** | Группы | Гомоморфизмы групп |
| **Top** | Топологические пространства | Непрерывные отображения |
| **Pos** | Частично упорядоченные множества | Монотонные функции |
| **Vect_K** | Векторные пространства над K | Линейные отображения |
Одна и та же теорема, доказанная в абстрактной категории, автоматически работает в Set, в Grp, в Top, в типах Haskell. Не нужно доказывать четыре раза. Это и есть главный выигрыш: теория категорий - машина для переноса знаний между математическими мирами.
Рождение теории категорий
В 1945 году Сэмюэл Эйленберг и Сондерс Мак-Лейн опубликовали статью «General Theory of Natural Equivalences». Их целью было формализовать понятие «естественности» в алгебраической топологии. Категории были вспомогательным инструментом - но инструмент оказался мощнее, чем задача, для которой его создали.
Философия «объект определяется своими связями» - не просто эстетика. Это инструмент. В Haskell тип `a` ничего не говорит о своей реализации. Но если для `a` существует функтор - уже известно, как его отображать. Если монада - как цеплять вычисления. Структура определяется стрелками, а не содержимым.
В категории Set объектами являются множества. Что является морфизмами?
Морфизм
Морфизм - стрелка f: A → B. Это слово звучит пугающе, но за ним скрывается знакомая вещь: функция, гомоморфизм, непрерывное отображение, SQL JOIN. Всё, что берёт что-то типа A и даёт что-то типа B, - потенциальный морфизм. Разница с обычной функцией: морфизм не обязан знать, что внутри A или B. Только направление.
Множество всех морфизмов из A в B обозначается **Hom(A, B)** или **Hom_C(A, B)**, если нужно указать категорию. Это называется **hom-set** (hom-множество). Для каждой пары объектов существует своё hom-множество, которое может быть пустым.
**Эндоморфизм** f: A → A - стрелка в себя. Hom(A, A) никогда не пусто: там всегда есть хотя бы identity. В Haskell функция `negate :: Int -> Int` - эндоморфизм. Монада `IO a -> IO a` - тоже эндоморфизм, только в другой категории. **Изоморфизм** - обратимая стрелка: существует g: B → A такой, что g ∘ f = id_A и f ∘ g = id_B. Изоморфные объекты категорически неразличимы - именно поэтому в математике часто говорят «с точностью до изоморфизма».
В коде hom-множество Hom(Int, String) - это все возможные функции `Int -> String`: `show`, `toHex`, `toBinary`, `toRoman`, ... бесконечно много. Hom(Bool, Bool) - ровно четыре функции: `id`, `not`, `const True`, `const False`. Размер hom-множества говорит о том, насколько объекты «связаны».
| Категория | Эндоморфизм A → A | Изоморфизм A ≅ B |
|---|---|---|
| **Set** | Функция из множества в себя | Биекция |
| **Grp** | Автоморфизм группы | Изоморфизм групп |
| **Top** | Непрерывное отображение в себя | Гомеоморфизм |
| **Vect** | Линейный оператор | Обратимое линейное отображение |
Функция f: A → A называется эндоморфизмом. Что из следующего верно?
Композиция
Есть стрелка f: A → B и стрелка g: B → C. Обязана существовать стрелка g ∘ f: A → C. Это не теорема, не следствие - это **аксиома**. Без замкнутости под композицией объект называется графом, не категорией. Разница принципиальная: в графе можно нарисовать A→B и B→C без A→C. В категории - нельзя.
Аксиома ассоциативности: для любых f: A → B, g: B → C, h: C → D выполняется **h ∘ (g ∘ f) = (h ∘ g) ∘ f**. Порядок применения скобок не имеет значения. Благодаря этому можно писать h ∘ g ∘ f без скобок.
Unix pipes `cat file | grep error | wc -l` - это буквально запись g ∘ f ∘ h слева направо. Каждая команда - морфизм. Pipe - операция композиции. Ассоциативность означает: не важно, сначала скомпоновать `cat | grep`, а потом `| wc`, или сначала `grep | wc`, а потом подключить `cat`. Результат тот же - и именно это позволяет строить пайплайны произвольной длины без осечек.
Важная деталь: g ∘ f читается «g после f» - сначала f, потом g. В диаграммах стрелки идут слева направо (A → B → C), но в формуле - справа налево (g ∘ f). Это постоянный источник путаницы даже у опытных математиков. Haskell решил это по-своему: оператор `>>>` из `Control.Category` позволяет писать в прямом порядке: `f >>> g`.
Даны морфизмы f: A → B, g: B → C, h: C → D. Какое утверждение верно?
Тождественный морфизм
Для каждого объекта A существует морфизм **id_A: A → A**, который ничего не делает. Звучит скучно. Но это вторая аксиома категории - без неё всё рассыпается. Если убрать identity, нельзя будет говорить об изоморфизмах, о нейтральных элементах, о том, что объект «сам на себя похож». Это фундамент, который не виден, пока цел.
Аксиома identity: для любого морфизма f: A → B выполняется **f ∘ id_A = f** (правый нейтральный элемент) и **id_B ∘ f = f** (левый нейтральный элемент). Identity - это нейтральный элемент относительно композиции.
Identity - нейтральный элемент для композиции, как 0 для сложения и 1 для умножения. Но математически интереснее другое: identity - это то, что позволяет задать понятие изоморфизма. Если f: A → B и g: B → A такие, что g ∘ f = id_A и f ∘ g = id_B, - объекты неразличимы в категорном смысле. В Haskell это `Iso` из пакета `lens`. В теории баз данных - изоморфные схемы.
Четыре компонента собраны. **(1)** Объекты - чёрные ящики. **(2)** Морфизмы - стрелки между ними. **(3)** Композиция, замкнутая и ассоциативная. **(4)** Identity для каждого объекта. Минимальная конструкция, в которую влезает половина математики. Следующий шаг - функторы: отображения между категориями. Именно там начинается настоящая магия переноса теорем.
| Аксиома | Формула | Аналогия |
|---|---|---|
| Замкнутость композиции | f: A→B, g: B→C ⟹ g∘f: A→C | Два звена цепи = цепь |
| Ассоциативность | h∘(g∘f) = (h∘g)∘f | Скобки не важны |
| Левый identity | id_B ∘ f = f | 0 + x = x |
| Правый identity | f ∘ id_A = f | x + 0 = x |
Заметьте: понятие «нейтральный элемент» встречается везде - 0 в сложении, 1 в умножении, пустая строка в конкатенации, пустой список в append. Это не совпадение. Все они - identity в своих категориях. Теория категорий делает это явным и доказывает свойства один раз для всех случаев сразу.
Категория - это то же самое, что ориентированный граф
Граф - только визуализация. Категория требует замкнутость под композицией и identity - этого у произвольного графа нет
Граф рисует стрелки A→B и B→C, не обязывая к существованию A→C. Категория не рисует - она утверждает: если f: A→B и g: B→C, то g∘f: A→C существует и живёт в Hom(A,C). Кроме того, граф не требует петель на узлах, а в категории id_A - аксиома, не опция. Попытка назвать произвольный граф категорией - как назвать коллекцию файлов программой: форма похожа, семантика отсутствует.
Какую роль играет тождественный морфизм id_A в категории?
Ключевые идеи
- **Категория** - коллекция объектов и морфизмов с двумя аксиомами: ассоциативная композиция и identity для каждого объекта
- **Морфизм** f: A → B - не функция и не отображение в обычном смысле. Стрелка, которая знает только source и target, не внутренность объектов
- **Hom(A,B)** - множество всех стрелок из A в B. Может быть пустым, может содержать много морфизмов. Именно через hom-множества объект определяется своим окружением
- **Категория = граф + замкнутость + identity**: нарисовать стрелки мало - нужно чтобы их композиция всегда существовала и у каждого узла была петля-identity
Связанные темы
Категории - фундамент для всех дальнейших конструкций:
- Функторы — Отображения между категориями, сохраняющие структуру
- Естественные преобразования — Морфизмы между функторами - следующий уровень абстракции
Вопросы для размышления
- Какие категории встречаются в повседневной жизни? (Подсказка: объекты - города, морфизмы - дороги?)
- Почему ассоциативность композиции важна для программирования? Что было бы, если бы (h ∘ g) ∘ f ≠ h ∘ (g ∘ f)?
- Можно ли построить категорию с одним объектом? Что она будет представлять?