> For the complete documentation index, see [llms.txt](https://0nkery.gitbook.io/bartosz-milewski-category-theory-for-programmers/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://0nkery.gitbook.io/bartosz-milewski-category-theory-for-programmers/kategorii-bolshie-i-malenkie.md). # Категории большие и маленькие Вы можете действительно прочувствовать категории на нескольких примерах. Категории бывают разных форм и размеров и часто проявляются в неожиданных местах. Начнем с самых простых. ## Без объектов Самая банальная категория - та, в которой ноль объектов и, соответственно, ноль морфизмов. Это очень унылая категория сама по себе, но она может быть важна в контексте других категорий, например, в категории всех категорий (да, такая существует). Если Вы считаете, что пустое множество имеет смысл, тогда почему пустая категория не может? ## Простые графы Можно создавать категории, просто соединяя объекты стрелками. Можете себе представить любой ориентированный граф и сделать из него категорию, просто добавив больше стрелок. Во-первых, добавьте тождественную стрелку для каждой вершины. Затем для любых двух стрелок таких, что конец одной совпадает с началом другой (другими словами, для любых двух *компонуемых* стрелок), добавьте новую стрелку - их композицию. Каждый раз, когда Вы добавляете новую стрелку, нужно так же учесть ее композицию с любой другой стрелкой (за исключением тождественных стрелок) и с самой собой. Обычно все заканчивается бесконечным количеством стрелок, но это нормально. Можно по-другому рассматривать этот процесс - Вы создаете категорию, в которой для каждой вершины есть объект, а все возможные *цепочки* компонуемых вершин графа - это морфизмы. (Можно даже рассматривать тождественные морфизмы как особые случаи цепочек с длиной ноль.) Такая категория называется *свободной категорией*, порожденной заданным графом. Это пример свободного конструирования (от англ. *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 в конкурентном программирование, события в функциональном реактивном программировании и так далее. Традиционно моноид определяется как множество с бинарной операцией. Все, что требуется от этой операции, - ассоциативность и наличие особого элемента, который выступает в качестве нейтрального элемента по отношению к этой операции. Например, натуральные числа с нулем формируют моноид по сложению. Ассоциативность означает, что ```haskell (a + b) + c = a + (b + c) ``` (Другими словами, мы можем опустить скобки при сложении чисел.) Нейтральный элемент - ноль, потому что ```haskell 0 + a = a a + 0 = a ``` Второе уравнение избыточно, так как сложение коммутативно (`a + b = b + a`), но коммутативность не входит в определение моноида. К примеру, сложение строк не коммутативно, но все же формирует моноид. Нейтральный элемент для сложения строк, кстати, - пустая строка, которая может быть приписана к строке с любой стороны без ее изменения. В Haskell можно определить класс типов для моноидов - тип, для которого существует нейтральный элемент `mempty` и бинарная операция `mappend`: ```haskell 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`): ```haskell instance Monoid String where mempty = "" mappend = (++) ``` Мы переиспользовали оператор сложения списков (`++`), потому что `String` - это всего лишь список символов. Немного о синтаксисе Haskell: любой инфиксный оператор может быть преобразован в функцию двух аргументов - нужно окружить его скобками. Две строки можно сложить вставкой `++` между ними: ```haskell "Hello " ++ "world!" ``` или передачей их в качестве аргумента заключенному в скобки `(++)`: ```haskell (++) "Hello " "world!" ``` Обратите внимание, что аргументы функции не разделены запятыми и не окружены скобками. (К этому, возможно, сложнее всего привыкнуть при изучении Haskell.) Стоит подчеркнуть, что Haskell позволяет выразить равенство функций, как, например: ```haskell mappend = (++) ``` Концептуально это отличается от выражения равенства значений, производимых функциями: ```haskell mappend s1 s2 = (++) s1 s2 ``` Первое соответствует равенству морфизмов в категории **Hask** (или **Set**, если мы игнорируем bottom, который обозначает незавершающиеся вычисления). Такие равенства не только более краткие, но и часто могут быть обобщены на другие категории. Второе называется *экстенциональное* равенство и обозначает факт, что для любых двух входных строк выходная строка для `mappend` и `(++)` будет одна и та же. Так как значения аргументов иногда называются *точки* ("значение `f` в точке `x`"), это так же называется точечное равенство. Равенство функций без указания аргументов описывается как *бесточечное*. (Между прочим, бесточечные равенства часто включают композицию функций, которая символизируется точкой, что может смутить начинающих.) Ближайшим приближением к определению моноида в C++ было бы использование (пока еще обсуждаемого) синтаксиса концептов. ```cpp template T mempty = delete; template T mappend(T, T) = delete; template concept bool Monoid = requires (M m) { { mempty } -> M; { mappend(m, m); } -> M; }; ``` Первое определение использует шаблон значения (так же обсуждается). Полиморфное значение - это семейство значений, различное для каждого типа. Ключевое слово `delete` означает, что значение по умолчанию не определено: его придется определить в каждом отдельном случае. Похожим образом, нет значения по умолчанию для `mappend`. Концепт `Monoid` является предикатом (поэтому тип `bool`), который проверяет, существуют ли подходящие определения `mempty` и `mappend` для заданного типа `M`. Конкретизация концепта `Monoid` может быть осуществлена реализацией подходящих специализаций и перегрузок: ```cpp template<> std::string mempty = { "" }; 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*, что означает "одинокий". Каждый моноид может быть описан как категория из одного объекта с множеством морфизмов, которые подчиняются соотвествующим правилам композиции. ![](https://bartoszmilewski.files.wordpress.com/2014/12/monoid.jpg?w=236\&h=300) Сложение строк интересно тем, что мы можем выбрать между присоединением справа и присоединением слева (*прим. пер. - здесь потерялся каламбур со словами "append" и "prepend" во втором случае :(* ). Таблицы композиции двух вариантов зеркально противоположны друг другу. Можно легко убедиться, что присоединение "bar" после "foo" соответствует присоединению "foo" перед "bar". Можно задаться вопросом: определяет ли каждый категорийный моноид - категория с одним объектом - уникальный моноид-множество с бинарным оператором? Оказывается, всегда можно извлечь множество из категории с одним объектом. Это множество является множеством морфизмов - сумматоров в нашем примере. Другими словами, в нашем распоряжении hom-множество `M(m, m)` единственного объекта `m`в категории `M`. Мы можем легко определить бинарный оператор на этом множестве: моноидальный продукт двух элементов множества - это элемент, соответствующий композиции соответствующих морфизмов. Если взять два элемента `M(m, m)`, соответствующих `f` и `g`, их продуктом будет композиция `g∘f`. Такая композиция всегда существует, так как исходный и целевой объекты этих морфизмов - это один и тот же объект. И она ассоциативна по правилам категорий. Тождественный морфизм - нейтральный элемент данного продукта. Так что мы всегда можем восстановить моноид-множество из моноида-категории. Во всех отношениях они одно и то же. ![](https://bartoszmilewski.files.wordpress.com/2014/12/monoidhomset.jpg)\ *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), которые можно компоновать: ```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, чтобы отработать переключение от картины с точки зрения теории множеств на картину с точки зрения теории категорий. > > Также, "моноидальная категория" - еще одна концепция, о которой я еще не рассказывал.