Теория категорий для алгебры

Haskell - язык программирования с 10 000+ пакетами - строится на теории категорий: монады, функторы, аппликативы - это математические структуры теории категорий. Rust enum и struct - это буквально суммы и произведения объектов. Folding списка - универсальный катаморфизм, теорема теории категорий.

• **Haskell/Rust типы:** `Maybe`, `Either`, `List` - это начальные алгебры в категории типов; законы функтора - это теоремы теории категорий
• **Компиляторные оптимизации:** GHC Haskell использует теорию начальных алгебр для deforestation (устранения промежуточных структур данных через fold/build)
• **Базы данных:** функторы описывают отображения схем; миграции - естественные преобразования; реляционная алгебра - категориальная структура

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

• Теория Галуа

Функторы в алгебре

Haskell - язык программирования с 10 000+ пакетами - строится на теории категорий: монады, функторы, аппликативы - это математические структуры теории категорий. Функтор F: C → D - отображение категорий, сохраняющее структуру: объекты в объекты, морфизмы в морфизмы, с сохранением композиции и тождественных морфизмов. Забывающий функтор Grp → Set забывает алгебраическую структуру; свободный функтор Set → Grp строит свободные группы.

В Haskell: `fmap` для `Maybe`, `[]`, `IO` - это именно функтор в категориальном смысле. Закон функтора: fmap id = id и fmap (f . g) = fmap f . fmap g. TypeClass Functor в Haskell - точно это.

Универсальная алгебра

Универсальная алгебра изучает алгебраические структуры через сигнатуры и уравнения (equational theories). Многообразие (variety) - класс алгебраических структур, задаваемый уравнениями. Группы, кольца, решётки - многообразия. Теорема Биркгофа: класс алгебр является многообразием тогда и только тогда, когда он замкнут относительно гомоморфных образов, подалгебр и прямых произведений (HSP-теорема).

**Примеры многообразий:** группы (6 уравнений), абелевы группы (+1 уравнение), кольца (12 уравнений), булевы алгебры (конечное число уравнений). Не-многообразие: конечные группы (замкнутость по P нарушена: ∏ ℤ/nℤ бесконечна).

Алгебраические типы данных и начальные алгебры

Алгебраические типы данных (ADT) в Haskell/Rust - это буквально алгебра: произведения типов (A × B, struct), суммы типов (A + B, enum). Натуральные числа - начальная алгебра для функтора F(X) = 1 + X: ℕ = Fix(F) = 1 + (1 + (1 + ...)). Список - начальная алгебра для F(X) = 1 + A×X. Это не метафора - это теорема теории категорий.

**Теорема Ламбека:** если (A, α: FA → A) - начальная F-алгебра, то α - изоморфизм. Значит A ≅ F(A) - рекурсивное уравнение типов. Для ℕ: ℕ ≅ 1 + ℕ (ноль или следующий), для List[a]: List[a] ≅ 1 + a × List[a] (пустой или голова + хвост).

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

• **Функторы:** F: C→D сохраняет объекты, морфизмы, композицию и id; Free ⊣ Forget - сопряжение; fmap в Haskell - это функтор
• **Универсальная алгебра:** многообразие = класс, задаваемый уравнениями = HSP-замкнутый класс; коммутативность, ассоциативность - уравнения
• **ADT и начальные алгебры:** ℕ = Fix(1+X), List[A] = Fix(1+A×X); fold = катаморфизм = единственный гомоморфизм из начальной алгебры
• **Произведения и суммы:** A×B (struct/tuple), A+B (enum/Either); категориальные конструкции за типами данных

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

Теория категорий объединяет всю алгебру:

• Теория групп — Группы - объекты категории Grp; функторы между алгебрами - гомоморфизмы; сопряжение Free⊣Forget
• Теория Галуа — Соответствие Галуа - антиэквивалентность категорий: подполя ↔ подгруппы - это контравариантный функтор

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

• Монада в Haskell - это моноид в категории эндофункторов. Что это означает конкретно: что такое «умножение» монады и «единица», и как они связаны с bind (>>=) и return?
• Fix f в Haskell - начальная алгебра функтора f. Напишите тип бинарного дерева через Fix и реализуйте fold (катаморфизм) для него.
• Ковариантные и контравариантные функторы: функтор Hom(A, -) ковариантен, Hom(-, B) контравариантен. Как это связано с тем, что функции Rust в Fn(A → B) ковариантны по B и контравариантны по A?