чает составную стрелку. Вводится специальная операция “точка с запятой”, которая называется композицией
стрелок: Это правило говорит о том, что связи распространяются по объектам. Теперь у нас есть не просто
объекты и стрелки, а целая сеть объектов, связанных между собой. Тот факт, что связи действительно рас-
пространяются отражается свойством:
f ; ( g ; h) = ( f ; g) ; h
Это свойство называют ассоциативностью. Оно говорит о том, что стрелки, которые образуют составную
стрелку являются цепочкой и нам не важен порядок их группировки, важно лишь кто за кем идёт. Подра-
зумевается, что стрелки f, g и h имеют подходящие типы для композиции, что их можно соединять. Это
свойство похоже на интуитивное понятие пути, как цепочки отрезков.
Связи между объектами можно трактовать как преобразования объектов. Стрелка f : A > B – это способ,
с помощью которого мы можем перевести объект A в объект B. Композиция в этой аналогии приобретает
естественную интерпретацию. Если у нас есть способ f : A > B преобразования объекта A в объект B, и
способ g : B > C преобразования объекта B в объект C, то мы конечно можем, применив сначала f, а
затем g, получить из объекта A объект C.
Когда мы думаем о стрелках как о преобразовании, то естественно предположить, что у нас есть преобра-
зование, которое ничего не делает, как тождественная функция. В будем говорить, что для каждого объекта
A есть стрелка idA, которая начинается из этого объекта и заканчивается в нём же.
| 227
idA : A > A
Тот факт, что стрелка idA ничего не делает отражается свойствами, которые должны выполняться для
всех стрелок:
idA ; f
=
f
f ; idA
=
f
Если мы добавим к любой стрелке тождественную стрелку, то от этого ничего не изменится.
Всё готово для того чтобы дать формальное определение понятия категории (category). Категория это:
• Набор объектов (object).
• Набор стрелок (arrow) или морфизмов (morphism).
• Каждая стрелка соединяет два объекта, но объекты могут совпадать. Так обозначают, что стрелка f
начинается в объекте A и заканчивается в объекте B:
f : A > B
При этом стрелка соединяет только два объекта:
f : A > B, f : A > B
?
A = A , B = B
• Определена операция композиции или соединения стрелок. Если конец одной стрелки совпадает с
началом другой, то их можно соединить вместе:
f : A > B, g : B > C
? f ; g : A > C
• Для каждого объекта есть стрелка, которая начинается и заканчивается в этом объекте. Эту стрелку
называют тождественной (identity):
idA : A > A
Должны выполняться аксиомы:
• Тождество id
id ; f = f
f ; id = f
• Ассоциативность ;
f ; ( g ; h) = ( f ; g) ; h
Приведём примеры категорий.
• Одна точка с одной тождественной стрелкой образуют категорию.
• В категории Set объектами являются все множества, а стрелками – функции. Стрелки соединяются с
помощью композиции функций, тождественная стрелка, это тождественная функция.
• В категории Hask объектами являются типы Haskell, а стрелками – функции, стрелки соединяются с
помощью композиции функций, тождественная стрелка, это тождественная функция.
• Ориентированный граф может определять категорию. Объекты – это вершины, а стрелки это связанные
пути в графе. Соединение стрелок – это соединение путей, а тождественная стрелка, это путь в котором
нет ни одного ребра.
228 | Глава 15: Теория категорий
• Упорядоченное множество, в котором есть операция сравнения на больше либо равно задаёт катего-
рию. Объекты – это объекты множества. А стрелки это пары объектов таких, что первый объект меньше
второго. Первый объект в паре считается начальным, а второй конечным.
( a, b) : a > b
если a ? b
Стрелки соединяются так:
( a, b) ; ( b, c) = ( a, c)
Тождественная стрелка состоит из двух одинаковых объектов:
ida = ( a, a)
Можно убедиться в том, что это действительно категория. Для этого необходимо проверить аксиомы
ассоциативности и тождества. Важно проверить, что те стрелки, которые получаются в результате ком-
позиции, не нарушали бы основного свойства данной структуры, то есть тот факт, что второй элемент
пары всегда больше либо равен первого элемента пары.
Отметим, что бывают такие области, в которых стрелки или преобразования с одинаковыми именами
могут соединять несколько разных объектов. Например в Haskell есть классы, поэтому функции с одними
и теми же именами могут соединять разные объекты. Если все условия категории для объектов и стрелок
выполнены, кроме этого, то такую систему называют прекатегорией (pre-category). Из любой прекатегории
не сложно сделать категорию, если включить имена объектов в имя стрелки. Тогда у каждой стрелки будут
только одна пара объектов, которые она соединяет.
15.2 Функтор
Вспомним определение класса Functor:
class Functor f where
fmap :: (a -> b) -> (f a -> f b)
В этом определении участвуют тип f и метод fmap. Можно сказать, что тип f переводит произвольные
типы a в специальные типы f a. В этом смысле тип f является функцией, которая определена на типах. Метод
fmap переводит функции общего типа a -> b в специальные функции f a -> f b.
При этом должны выполняться свойства:
fmap id
= id
fmap (f . g) = fmap f . fmap g