Категории большие и маленькие

Вы можете действительно прочувствовать категории на нескольких примерах. Категории бывают разных форм и размеров и часто проявляются в неожиданных местах. Начнем с самых простых.

Без объектов

Самая банальная категория - та, в которой ноль объектов и, соответственно, ноль морфизмов. Это очень унылая категория сама по себе, но она может быть важна в контексте других категорий, например, в категории всех категорий (да, такая существует). Если Вы считаете, что пустое множество имеет смысл, тогда почему пустая категория не может?

Простые графы

Можно создавать категории, просто соединяя объекты стрелками. Можете себе представить любой ориентированный граф и сделать из него категорию, просто добавив больше стрелок. Во-первых, добавьте тождественную стрелку для каждой вершины. Затем для любых двух стрелок таких, что конец одной совпадает с началом другой (другими словами, для любых двух компонуемых стрелок), добавьте новую стрелку - их композицию. Каждый раз, когда Вы добавляете новую стрелку, нужно так же учесть ее композицию с любой другой стрелкой (за исключением тождественных стрелок) и с самой собой. Обычно все заканчивается бесконечным количеством стрелок, но это нормально.

Можно по-другому рассматривать этот процесс - Вы создаете категорию, в которой для каждой вершины есть объект, а все возможные цепочки компонуемых вершин графа - это морфизмы. (Можно даже рассматривать тождественные морфизмы как особые случаи цепочек с длиной ноль.)

Такая категория называется свободной категорией, порожденной заданным графом. Это пример свободного конструирования (от англ. free construction - предложите лучший перевод, срочно!) - процесс завершения заданной структуры путем расширения ее минимальным числом элементов для удовлетворения ее законов (здесь имеются в виду законы категории). Мы увидим больше примеров далее.

Порядки

А теперь нечто совершенно другое! Категория, где морфизм - это отношение между объектами: отношение "быть меньше или равным". Давайте убедимся, что это на самом деле категория. Есть ли у нас тождественные морфизмы? Каждый объект меньше или равен самому себе: да! Есть ли у нас композиция? Если a <= b и b <= c, тогда a <= c: да! Композиция ассоциативна? Да! Множество с подобным отношением называется предпорядком, так что предпорядок на самом деле является категорией.

Можно задать более строгое отношение, которое удовлетворяет дополнительному условию: если a <= b и b <= a, тогда aдолжно быть равно b. Это называется частично упорядоченное множество.

Наконец, можно наложить условие, что любые два объекта находятся в отношении друг с другом, так или иначе; и это дает нам линейно упорядоченное множество или вполне упорядоченное множество.

Давайте опишем эти упорядоченные множества как категории. Предпорядок - это категория, где любой объект a с любым объектом bсоединяет не более одного морфизма. Другое название такой категории - "тонкая" ("thin"). Предпорядок - тонкая категория.

Множество морфизмов от объекта a к объекту b в категории C называется hom-множеством и записывается как C(a, b) (или, иногда, $Hom_C (a, b)$). Так что каждое hom-множество в предпорядке либо пустое, либо содержит единственный элемент. В любом предпорядке это относится и к hom-множеству С(a, a), множеству морфизмов от a к a, которое должно содержать единственный элемент - тождество. В предпорядке, впрочем, могут быть циклы. Циклы запрещены в частично упорядоченных множествах.

Очень важно уметь распознавать предпорядки, частично и вполне упорядоченные множества - все из-за сортировки. Алгоритмы сортировки, такие как quicksort, сортировка "пузырьком", сортировка слиянием и прочие, корректно работают только для вполне упорядоченных множеств. Частично упорядоченные множества могут быть отсортированы с использованием топологической сортировки.

Моноид как множество

Моноид - ошеломляюще простое, но поразительно мощное понятие. Это понятие, стоящее за простейшей арифметикой: и сложение, и умножение формируют моноид. Моноиды вездесущи в программировании. Они проявляются как строки, списки, сворачиваемые структуры данных, futures в конкурентном программирование, события в функциональном реактивном программировании и так далее.

Традиционно моноид определяется как множество с бинарной операцией. Все, что требуется от этой операции, - ассоциативность и наличие особого элемента, который выступает в качестве нейтрального элемента по отношению к этой операции.

Например, натуральные числа с нулем формируют моноид по сложению. Ассоциативность означает, что

(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 ассоциативна). Ответственность за выполнение этих условий лежит на программисте.

Классы в Haskell не такие навязчивые как классы в C++. При определении нового типа необязательно указывать его класс заранее. Можно спокойно отложить это в долгий ящик и объявить заданный тип экземпляром какого-либо класса гораздо позже. Для примера, давайте объявим String моноидом, реализовав mempty и mappend (это, по сути, сделано за Вас в стандартной библиотеке Prelude):

instance Monoid String where
    mempty = ""
    mappend = (++)

Мы переиспользовали оператор сложения списков (++), потому что String - это всего лишь список символов.

Немного о синтаксисе Haskell: любой инфиксный оператор может быть преобразован в функцию двух аргументов - нужно окружить его скобками. Две строки можно сложить вставкой ++ между ними:

"Hello " ++ "world!"

или передачей их в качестве аргумента заключенному в скобки (++):

(++) "Hello " "world!"

Обратите внимание, что аргументы функции не разделены запятыми и не окружены скобками. (К этому, возможно, сложнее всего привыкнуть при изучении Haskell.)

Стоит подчеркнуть, что Haskell позволяет выразить равенство функций, как, например:

mappend = (++)

Концептуально это отличается от выражения равенства значений, производимых функциями:

mappend s1 s2 = (++) s1 s2

Первое соответствует равенству морфизмов в категории Hask (или Set, если мы игнорируем bottom, который обозначает незавершающиеся вычисления). Такие равенства не только более краткие, но и часто могут быть обобщены на другие категории. Второе называется экстенциональное равенство и обозначает факт, что для любых двух входных строк выходная строка для mappend и (++) будет одна и та же. Так как значения аргументов иногда называются точки ("значение f в точке x"), это так же называется точечное равенство. Равенство функций без указания аргументов описывается как бесточечное. (Между прочим, бесточечные равенства часто включают композицию функций, которая символизируется точкой, что может смутить начинающих.)

Ближайшим приближением к определению моноида в 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 для заданного типа M.

Конкретизация концепта 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 отображает элемент множества моноида на функцию, определенную на этом множестве.

А теперь я хочу, чтобы Вы забыли, что имеете дело с множеством натуральных чисел, и просто представили единственный объект, шарик с пучком моноидов - сумматоров. Моноид - это категория из одного объекта. На самом деле название "моноид" происходит от греческого mono, что означает "одинокий". Каждый моноид может быть описан как категория из одного объекта с множеством морфизмов, которые подчиняются соотвествующим правилам композиции.

Сложение строк интересно тем, что мы можем выбрать между присоединением справа и присоединением слева (прим. пер. - здесь потерялся каламбур со словами "append" и "prepend" во втором случае :( ). Таблицы композиции двух вариантов зеркально противоположны друг другу. Можно легко убедиться, что присоединение "bar" после "foo" соответствует присоединению "foo" перед "bar".

Можно задаться вопросом: определяет ли каждый категорийный моноид - категория с одним объектом - уникальный моноид-множество с бинарным оператором? Оказывается, всегда можно извлечь множество из категории с одним объектом. Это множество является множеством морфизмов - сумматоров в нашем примере. Другими словами, в нашем распоряжении hom-множество M(m, m) единственного объекта mв категории M. Мы можем легко определить бинарный оператор на этом множестве: моноидальный продукт двух элементов множества - это элемент, соответствующий композиции соответствующих морфизмов. Если взять два элемента M(m, m), соответствующих f и g, их продуктом будет композиция g∘f. Такая композиция всегда существует, так как исходный и целевой объекты этих морфизмов - это один и тот же объект. И она ассоциативна по правилам категорий. Тождественный морфизм - нейтральный элемент данного продукта. Так что мы всегда можем восстановить моноид-множество из моноида-категории. Во всех отношениях они одно и то же.

hom-множество моноида как морфизмы и точки на множестве

Осталась лишь одна маленькая оговорка для математиков: морфизмы не обязаны формировать множество. В мире категорий существуют вещи большие, чем множества. Категория, в которой морфизмы между двумя любыми объектами образуют множество, называется локально малой. Как и обещал, я буду в большинстве случаев игнорировать такие тонкости, но я решил, что нужно упомянуть эту для галочки.

Многие интересные явления в теории категорий основаны на том факте, что элементы hom-множества могут быть представлены как морфизмы, подчиняющиеся правилам композиции, и как точки на множестве. В данном случае, композиция морфизмов в M преобразуется в моноидальный продукт на множестве M(m, m).

Благодарности

Хотелось бы поблагодарить Эндрю Саттона за переработку моего кода концепта моноида на C++ в соответствии с последней версией их с Бьерном Страуструпом предложения.

Упражнения

1. Сделайте свободную категорию из:

   1. графа с одной вершиной и без ребер;

   2. графа с одной вершиной и одним (ориентированным) ребром (подсказка: это ребро может быть скомпоновано само с собой);

   3. графа с двумя вершинами и одной стрелкой между ними;

   4. графа с одной вершиной и 26 стрелками, помеченными буквами алфавита: a, b, c, ... z.

2. Какой это порядок?

   1. Множество множеств с отношением включения: A содержится в B, если каждый элемент Aтак же является элементом B.

   2. Типы C++ с отношением "подтип": T1 является подтипом T2, если указатель на T1может быть передан в функцию, которая ожидает указатель на T2, без ошибки при компиляции.

3. Учитывая, что Bool - это множество из двух значений (True и False), покажите, что оно образует моноиды-множества с операторами && (AND) и || (OR).

4. Представьте моноид Bool с оператором AND как категорию: перечислите морфизмы и их правила композиции.

5. Представьте сложение по модулю 3 в качестве моноида-категории.

Ценные комментарии

pigworker

В то время как верно, что сортировка по предпорядку требует, чтобы этот предпорядок был вполне упорядочен, забавно, что основные требования предпорядка не важны для сортировки. Как я рассказал в статье "Как держать своих соседей в порядке", если нужна только локальная сортировка - например, соседние элементы на выходе связаны отношением <= - нужно знать только, что (x <= y) или (y <= x) для любых x и y, и отношению <= необязательно быть предпорядком. Конечно, после сортировки, если требуются полезные выводы о несоседних элементах на выходе, то действительно требуется, чтобы отношение <=было предпорядком.

Список [Камень, Бумага, Ножницы] локально отсортирован по отношению "не побеждает".

Luka Rahne

Я не понимаю, как возможно определить категорию с бесконечным числом стрелок на основе графа конечного размера.

Bartosz Milewski

@Luka: В категории может быть много стрелок, соединяющих одни и те же объекты. В графе это бы соответствовало нескольким (ориентированным) ребрам, соединяющим две вершины. Такие графы иногда называют мультиграфами с циклами.

Brian Slesinsky

Как определить, что две стрелки на самом деле одинаковы? Как программист, я привык думать, что вершины имеют уникальный идентификатор, а ребра - упорядоченные пары вершин. Очевидно, что такой подход в данном случае не работает.

Bartosz Milewski

@Brian: Нужно так же помечать и ребра. В примере категории множеств у функций есть названия: f, g, h.

kramer

Читая "(другими словами, для любых двух компонуемых стрелок)", я не уверен, что тождественные стрелки компонуемы. Следующее предложение явно исключает тождественные стрелки, но не понятно, относится ли это к предыдущему предложению или нет.

Предположив, что тождественные стрелки не компонуемы, было бы более ясно сделать шаг "добавьте тождественную стрелку для каждой вершины" последним, а не первым.

...

Bartosz Milewski

Тождественные стрелки компонуемы; просто не нужно рассматривать их как источники новых соединений. Композиция тождественной стрелки с любой другой возвращает ту же самую стрелку, а не новое соединение.

Klaus-Yusuff Reller

Я понимаю, что f, g и f . g "представляют" тождественную функцию. Но что такое "hom-множество"? Возможно ли показать его в коде?

Bartosz Milewski

Klaus-Yussuf: Нет, они не представляют тождественную функцию. Они представляют, к примеру, операции вроде (+2) или (+10) (части операторов Haskell), которые можно компоновать:

(+2) . (+10) = (+12)

Тождественная функция - это (+0). Hom-множество - это множество всех таких операций. Здесь это подмножество функций типа Int -> Int.

Adrian

Застрял на этой части главы: "Так что мы всегда можем восстановить моноид-множество из моноида-категории."

Думаю, что в целом я понимаю, что Вы имели в виду, но у меня не получается применить формальный жаргон. Так, если я возьму сумматоры, например, эта система может быть описана несколькими способами:

(1) множество чисел с оператором + и 0 в качестве нейтрального элемента (моноид),

(2) категория с одним объектом - множеством чисел - и компонуемыми стрелками - сумматорами (категория),

(3) множество сумматоров с оператором "композиции" и +0 в качестве нейтрального элемента (моноид).

Здесь я предполагаю, что (3) - это моноид-множество, тогда моноид-категория - это... (1) и (2)? Вот на чем я застрял: я не понимаю, почему моноид-категория так названа - это сокращенная форма для "категории с одним объектом, который является моноидом"?

Bartosz Milewski

@adrian: Категорийным моноидом является (3), потому что Вы ничего не говорите о том, чем является объект. Он просто есть, и точка. Он служит точкой соединения стрелок. Вся информация закодирована в правилах композиции для этих стрелок - в "таблице умножения стрелок".

Однако стрелки формируют множество. В этом множестве мы легко можем задать бинарный оператор: результат "умножения" двух стрелок - это стрелка, полученная их композицией. Теперь можно забыть о том, что это стрелки, и рассматривать их как элементы множества. Получится множество с бинарным оператором (и нейтральным элементом) - это и есть моноид с точки зрения теории множеств.

Это два эквивалентных способа рассмотрения одного и того же.

misha

Что двойственно моноиду?

Bartosz Milewski

@misha: Возьмите моноид и переверните в нем все стрелки. Получится категория (двойственная категория) с одним объектом. Любая категория с единственным объектом является моноидом. Так что двойник моноида - это моноид. Хотя необязательно, что точно такой же. К примеру, возьмем строковый моноид со стрелками "присоединить строку к началу". Двойник будет моноид со стрелками "присоединить строку к концу".

Некоторые говорят о комоноидах, но они определены в контексте категорий с большей структурой - моноидальных категорий.

valentin

Я бы хотел переспросить, с какого именно графа Вы начали? Я так же не могу понять превращение всех целых чисел в один объект. Вы говорите, что в типах мы можем игнорировать значения, а потом, магическим образом, люди как-то догадываются, что Void имеет только одно сопоставление с Bool, в то время как () имеет две различных стрелки к Bool. Если целевое значение важно, то почему Вы не различаете их в случае Void -> Bool?

Я имею в виду, что M(Bool, Bool) должен иметь один объект и 4 рефлексивных функции (морфизма), если мы учитываем значения, и 1 ссылку на сам объект, если не учитываем. Из заданий на этой неделе я вижу, что значения не важны. Однако единственная свинка, рисующая несколько рефлексивных морфизмов, в тексте говорит иначе. Ответы на задания прошлой недели демонстрируют полный хаос: некоторые значения учтены, некоторые нет. В частности, может быть m ^ n функций типа N -> M, где типы N и M имеют n и m значений соответственно. Это означает, что функций типа Void -> Bool должно быть 2 ^ 0 = 1, типа () -> Bool - 2 ^ 1 = 2. Хорошо, теперь понятно чуть лучше. Но я все еще не понимаю, как закончить построение графа на этой неделе, потому что Вы ничего не говорите о количестве значений каждой вершины.

Bartosz Milewski

Категории - это абстракция, что означает следующее: Вы берете что-либо и убираете (отнимаете) детали до тех пор, пока не доберетесь до сути. В этом случае Вы берете множество значений {True, False} и определяете на нем функции. Одна функция выполняет логическое И этих значений и True, другая же выполняет эту операцию над этими значениями и False. Посмотрите на композицию этих функций. Получается некая "таблица умножения" для этих функций. Запишите ее.

Теперь забудьте о значениях внутри множества и рассматривайте их как непрозрачный объект. Есть один объект и два морфизма с правилами композиции, которые Вы только что определили. Это категория (так ли это?). Если так, то это моноид, потому что задан только один объект.

nepalez

Если я все правильно понял, моноид - это специальный тип категории, который обладает одинаковой структурой в каждой точке.

А именно - если у нас есть объект 1 со стрелкой 1 -> 3, тогда "одинаковая" стрелка существует в точке 3: 3 -> 5. В этом смысле мы можем сказать, что 1 -> 3 и 3 -> 5 - "одинаковая" стрелка, и тогда можем забыть о различиях между 1 и 3 и перейти к единственному объекту Set с обобщенными стрелками.

Это верно, или нужно соблюсти другие ограничения, чтобы категорию можно было назвать моноидальной?

Bartosz Milewski

@nepalez: Во-первых, что такое "точка"? В моноиде как категории существует только один объект. Попробуйте выполнить упражнения 3-5, чтобы отработать переключение от картины с точки зрения теории множеств на картину с точки зрения теории категорий.

Также, "моноидальная категория" - еще одна концепция, о которой я еще не рассказывал.