Это четвертая статья в цикле «Теория категорий для программистов».
Понять пользу категорий можно изучая различные примеры. Категории бывают всех форм и размеров и часто появляются в самых неожиданных местах. Мы начнем с самых простых.
Без объектов
Самая простая категория — без объектов и, как следствие, без морфизмов. Это очень грустная категория, но она важна в контексте других категорий, например, в категории всех категорий (да, такая есть). Если вы считаете, что пустое множество осмысленно, то почему бы не быть пустой категории?
Простые графы
Вы можете строить категории, просто соединяя объекты стрелками. Начините с любого направленного графа и превратите его в категорию, просто добавив больше стрелок. Во-первых, добавьте единичную стрелку в каждом узле. Потом, для любых двух стрелок, таких, что конец одной совпадает с началом другой (другими словами, любые две компонуемых стрелки), нужно добавить новую стрелку, которая будет их композицией. Каждый раз, когда вы добавляете новую стрелку, вам нужно рассмотреть её композицию со всеми другими стрелками (кроме единичных). Как правило, получается бесконечное число стрелок, но это нормально.
На этот процесс можно смотреть и как на создание категории, в которой есть один объект для каждой ноды графа, и все возможные цепочки компонуемых ребер в качестве морфизмов. (Вы можете смотреть на единичные морфизмы, как на цепочки длины ноль.)
Такая категория называется свободной категорией, порожденной данным графом. Это пример свободной конструкции, процесса дополнения структуры, расширяя ее минимальным количеством элементов, чтобы удовлетворить законы конструкции (в данном случае, законы категории). Потом мы увидим больше примеров такой конструкции.
Порядки
А теперь кое-что совсем другое! Категория, в которой морфизмы — отношения между объектами: отношение меньше или равно. Давайте проверим, действительно ли это является категорией. У нас есть единичные морфизмы? Каждый объект меньше или равен самому себе! У нас есть композиция? Если A <= B и B <= С, то А <= C! Композиция ассоциативна? Да! Множество с таким соотношением называется предпорядок, и мы показали, что предпорядок — это категория.
Можно так же взять более сильную зависимость, которая удовлетворяет дополнительному условию, что если A <= В и В <= A то A должен быть такой же, как B. Это называется частичным порядком.
Наконец, можно наложить условие, что любые два объекта связаны друг с другом, тогда получится линейный или полный порядок.
Охарактеризуем эти упорядоченные множества, как категории. Предпорядок — это категория, где есть не более одного морфизма из любого объекта A в любой объект B. Еще одно название для такой категории «тонкая». Предпорядок — это тонкая категория.
Множество морфизмов из объекта a в объект b в категории C называется hom-множество и записывается как C(a, b) (или, иногда, HomC(a, b)). Таким образом, каждое hom-множество в предпорядке либо пустое, либо одноэлементное, в том числе и hom-множество С(a, a), множество морфизмов из a в само себя, которое должно быть одноэлементным и содержать только единичный морфизм. В предпорядке можно иметь циклы, в частичном же порядке они запрещены.
Можно легко убедиться, что любой ориентированный ациклический граф порождает своей свободной категорией частичный порядок.
Очень важно уметь распознавать предпорядки, частичные и полные порядки из-за сортировки. Алгоритмы сортировки, например, быстрая сортировка, пузырьковая сортировка, сортировка слиянием, и т.д., могут работать корректно только на полных порядках. Частичные порядки могут быть отсортированы с помощью топологической сортировки.
Моноид, как множество
Моноид — удивительно простая, но удивительно мощная концепция. Эта концепция лежит в основе арифметики: и сложение и умножение образуют моноид. Моноиды широко распространены в программировании. Они появляются в виде строк, списков, сворачиваемых структур данных, фьючерсы в параллельном программировании, события в функциональном реактивном программирования и так далее.
Традиционно, моноид определяется как множество с бинарной операцией. Все, что требуется от этой операции — её ассоциативность, и наличие единственного специального элемента, который ведет себя как единица по отношению к этой операции.
Например, натуральные числа со сложением и нулем образуют моноид. Ассоциативность означает, что:
(a + b) + c = a + (b + c)
(Другими словами, мы можем опустить скобки при сложении чисел.)
Нейтральный элемент — ноль потому, что:
0 + a = a
и
a + 0 = a
Второе уравнение излишне потому, что сложение коммутативно (a + b = b + a), но коммутативность не является частью определения моноида. Например, конкатенация не является коммутативной но она образует моноид. Нейтральный элемент для конкатенации строк, кстати, будет пустой строкой, которая может быть присоединена с любой стороны строки без ее изменения.
В Haskell мы можем определить класс типов для моноидов — тип, для которого существует нейтральный элемент называемый mempty и бинарная операция с названием mappend:
class Monoid m where
mempty :: m
mappend :: m -> m -> m
Сигнатура типа для функции двух аргументов, m -> m -> m, на первый взгляд может выглядеть странной, но она станет понятной после того как мы поговорим о каррировании.
Вы можете интерпретировать сигнатуру с несколькими стрелками двумя основными способами: как функция с несколькими аргументами, с крайним правым типом в качестве возвращаемого, или как функцию одного аргумента (самого левого), возвращающую функцию. Последнюю интерпретацию можно подчеркнуть при помощи скобок (которые являются избыточными, так как стрелка правоассоциативна), например: m -> (m -> m). Мы вернемся к этой интерпретации чуть позже.
Обратите внимание, что в Haskell нет никакого способа выразить моноидальные свойства mempty и mappend (то есть то, что mempty нейтральна и что mappend ассоциативна). Ответственность за это лежит на программисте. (прим. переводчика: в GHC есть похожий механизм, предназначенный для другой цели, но он может использоваться, как известный компилятору комментарий: www.haskell.org/haskellwiki/GHC/Using_rules)
Классы Haskell не так навязчивы, как классы C++. Когда вы определяете новый тип, вы не должны указывать его класс заранее. Вы можете полениться и объявить, что данный тип будет экземпляром некоторого класса гораздо позже. В качестве примера, давайте объявим, что тип String — моноид, предоставив реализацию mempty и mappend (это, по сути, сделали за вас в стандартной Prelude):
instance Monoid String where
mempty = ""
mappend = (++)
Здесь мы повторно использовали оператор конкатенации списков (++) потому, что строка, на самом деле, — список символов.
Немного о синтаксисе Haskell: любой инфиксный оператор может быть превращен в двухаргументную функцию с помощью заключения его в скобки. Имея две строки, вы можете объединить их, вставив между ними ++:
"Hello " ++ "world!"
или передав их в качестве двух аргументов в функцию (++):
(++) "Hello " "world!"
Заметьте, что аргументы функции не разделены запятыми и не окружены скобками. (Это, наверное, самое сложное, к чему нужно привыкнуть, во время изучения Haskell.)
Стоит заметить, что Haskell дает возможность выразить равенство функций напрямую:
mappend = (++)
Концептуально, это не то же самое, что и равенство значений, возвращаемых функцией:
mappend s1 s2 = (++) s1 s2
Первое представляет равенство морфизмов в категории Hask (или Set, если игнорировать bottom). Такие уравнения не только более емкие, но и часто обобщаемы и на другие категории. Второе называется экстенсиональным равенством, и заявляет тот факт, что для любых двух входных строк, результаты mappend и (++) равны. Так как значения аргументов иногда называют точками (например: значение f в точке х), это называется точечной нотацией. Функциональное равенство без указания аргументов называется безточечной нотацией. (Кстати, уравнения в безточечной нотации часто включают композицию функций, которую обозначают в виде точки, так что новичкам такое название может казаться странным.)
Ближайшим аналогом объявления моноида в C++ будет предложенный синтаксис для концептов.
template<class T>
T mempty = delete;
template<class T>
T mappend(T, T) = delete;
template<class M>
concept bool Monoid = requires (M m) {
{ mempty<M> } -> M;
{ mappend(m, m); } -> M;
};
Первое определение использует шаблон-значение (тоже предложены в стандарт). Полиморфное значение — это семейство значений, разное значение для каждого типа.
Ключевое слово delete означает, что значение по умолчанию не определено: они должны быть указаны индивидуально для каждого случая. Так же, нет реализации по умолчанию для mappend.
Концепт Monoid является предикатом (отсюда тип bool), который проверяет, существуют ли соответствующие определения mempty и mappend для данного типа М.
Реализовать концепт Monoid можно, предоставив соответствующие специализации и перегрузки:
template<>
std::string mempty<std::string> = {""};
std::string mappend(std::string s1, std::string s2) {
return s1 + s2;
}
Моноид как категория
Это было «знакомое» определение моноида в терминах элементов множества. Но, как вы знаете, в теории категорий мы пытаемся уйти от множеств и их элементов, а вместо этого говорить об объектах и морфизмах. Так давайте немного изменим наш ход мысли, и подумаем о применении бинарного оператора, как об их «перемешивании» или «сдвиге» внутри множества.
Например, существует операция добавления 5 к любому натуральному числу. Она отображает 0 в 5, 1 в 6, 2 в 7, и так далее. Это функция, определенная на множестве натуральных чисел. Это хорошо: у нас есть функция и множество. В общем, для любого числа n есть функция добавления n — «сумматор» n.
Как эти сумматоры компоновать? Композиция функции, которая добавляет 5, с функцией, которая добавляет 7, является функцией, которая добавляет 12. Таким образом, композиция сумматоров удовлетворяет правилам, эквивалентным правилам сложения. Это тоже хорошо: мы можем заменить сложение композицией функций.
Но это еще не все: существует также сумматор для нейтрального элемента, нулевой. Добавление нуля не изменяет элементы, так что это единичная функция в множестве натуральных чисел.
Вместо того, чтобы давать вам традиционные правила сложения, я мог бы также дать вам правила композиции сумматоров, без потери информации. Обратите внимание, что композиция сумматоров ассоциативна, поскольку композиция функций ассоциативна; и у нас есть нулевой сумматор, соответствующий единичной функции.
Проницательный читатель мог заметить, что отображение целых чисел в сумматоры следует из второго толкования сигнатуры типа mappend: m -> (m -> m). Тип говорит нам о том, что mappend отображает элемент множества моноида в функцию, действующую на этом множестве.
Теперь я хочу, чтобы вы забыли, что вы имеете дело с множеством натуральных чисел и просто думать о нем, как о едином объекте, блобе с кучей морфизмов — сумматоров. Моноид — это категория одного объекта. На самом деле, название моноид происходит от греческого моно — значит, одинокий. Каждый моноид может быть описан, как категории с одним объектом и набором морфизмов, которые следуют соответствующим правилам композиции.
Конкатенация строк интересна тем, что у нас есть выбор определения правого или левого добавления. Модели зеркально обратны друг другу. Можно легко убедиться, что добавлению справа «bar» к «foo» соответствует добавление слева «rab» к «oof».
Вы можете задать вопрос: каждый ли категориальный моноид — категория одного объекта — определяет уникальное множество с бинарным оператором. Оказывается, мы всегда можем извлечь множество из категории одного объекта. Это будет множество морфизмов — сумматоров в нашем примере. Другими словами, мы имеем hom-множество М(m, m) одного объекта m в категории М. Мы можем легко определить бинарный оператор в этом множестве: моноидальное произведение двух элементов этого множества — это элемент, соответствующий композиции соответствующих им морфизмов. Если вы дадите мне два элемента М(m, m), соответствующие морфизмам f и g, их произведение будет соответствовать композиции g∘f. Композиция всегда существует потому, что источник и результат этих морфизмов — один и тот же объект. И она ассоциативна по правилам категории. Тождественный морфизм является нейтральным элементом этого произведения. Таким образом, мы всегда можем восстановить моноид-множество из категориального моноида. Они являются одним и тем же.
<img align=«center width=»300" height=«197» src=«habrastorage.org/getpro/habr/post_images/a46/aec/49b/a46aec49b795d894b2b940b2f84447d1.jpg» alt=«image»/>
Существует только одна маленькая проблема для математиков: морфизмы не обязаны формировать множество. В мире категорий есть вещи, больше, чем множества. Категория, в которой морфизмы между любыми двумя объектами образуют множество, называется локально маленькой. Как и было обещано, я буду игнорировать такие тонкости, но я решил, что нужно этот факт упомянуть.
Много интересных явлений в теории категорий происходит из за того, что элементы hom-множества можно рассматривать и как морфизмы, которые следуют правилам композиции, и как элементы множества. Здесь композиция морфизмов в М переводит в моноидальное произведение в множестве М(m, m).
Теория категорий для программистов: предисловие
Категория: суть композиции
Типы и функции
Категории, большие и малые
Автор: Monnoroch
