нию начального объекта для каждого объекта может быть только одна стрелка, которая начинается в 0 и
заканчивается в этом объекте. Стрелка ( | 0 |) начинается в 0 и заканчивается в 0, но у нас уже есть одна та-
кая стрелка, по определению категории для каждого объекта определена тождественная стрелка, значит эта
стрелка является единственной.
Второе свойство следует из единственности стрелки, ведущей из начального объекта в данный. Третье
свойство лучше изобразить графически:
f
A
B
( | A |)
( | B |)
0
Поскольку стрелки ( | A |) и f можно соединить, то должна быть определена стрелка ( | A |) ; f : 0 > B, но
поскольку в категории с начальным объектом из начального объекта 0 в объект B может вести лишь одна
стрелка, то стрелка ( | A |) ; f должна совпадать с ( | B |).
234 | Глава 15: Теория категорий
Конечный объект
Дуализируем понятие начального объекта. Пусть в категории A есть объект 1, такой что для любого
объекта A существует и только одна стрелка, которая начинается из этого объекта и заканчивается в объекте
1. Такой объект называют конечным (terminal object):
. . .
A 1
A 2
. . .
1
A 3
. . .
. . .
A 4
Конечный объект определяет в категории функцию, которая ставит в соответствие объектам стрелки,
которые начинаются из данного объекта и заканчиваются в конечном объекте. Такую функцию называют
анаморфизмом (anamorphism), и обозначают специальными скобками [( · )], которые похожи на перевёрнутые
скобки для катаморфизма:
[( A )] = f : A > 1
Можно дуализировать и свойства:
[( 1 )] = id 1
тождество
f, g : A > 1 ? f = g
уникальность
f : A > B
? f ; [( B )] = [( A )]
слияние (fusion)
Приведём иллюстрацию для свойства слияния:
f
A
B
[( A )]
[( B )]
1
15.7 Сумма и произведение
Давным-давно, когда мы ещё говорили о типах, мы говорили, что типы конструируются с помощью двух
базовых операций: суммы и произведения. Сумма говорит о том, что значение может быть либо одним зна-
чением либо другим. А произведение обозначает сразу несколько значений. В Haskell есть два типа, которые
представляют собой сумму и произведение в общем случае. Тип для суммы это Either:
data Either a b = Left a | Right b
Произведение в самом общем виде представлено кортежами:
data (a, b) = (a, b)
В теории категорий сумма и произведение определяются как начальный и конечный объекты в специаль-
ных категориях. Теория категорий изучает объекты по тому как они взаимодействуют с остальными объек-
тами. Взаимодействие обозначается с помощью стрелок. Специальные свойства стрелок определяют объект.
Например представим, что мы не можем заглядывать внутрь суммы типов, как бы мы могли взаимодей-
ствовать с объектом, который представляет собой сумму двух типов A+ B? Нам необходимо уметь создавать
объект типа A + B из объектов A и B извлекать их из суммы. Создание объектов происходит с помощью
двух специальных конструкторов:
inl : A > A + B
inr : B > A + B
Сумма и произведение | 235
Также нам хочется уметь как-то извлекать значения. По смыслу внутри суммы A+ B хранится либо объект
A либо объект B и мы не можем заранее знать какой из них, поскольку внутреннее содержание A + B от
нас скрыто, но мы знаем, что это только A или B. Это говорит о том, что если у нас есть две стрелки A > C
и B > C, то мы как-то можем построить A + B > C. У нас есть операция:
out( f, g) : A + B > C
f : A > C, g : B > C
При этом для того, чтобы стрелки inl, inr и out были согласованы необходимо, чтобы выполнялись
свойства:
inl ; out( f, g) = f
inr ; out( f, g) = g
Для любых функций f и g. Графически это свойство можно изобразить так:
A
inl
A + B
inr
B
out
f
g
C
Итак суммой двух объектов A и B называется объект A + B и две стрелки inl : A > A + B и inr : B >
A + B такие, что для любых двух стрелок f : A > C и g : B > C определена одна и только одна стрелка
h : A + B > C такая, что выполнены свойства:
inl ; h = f
inr ; h = g
В этом определении объект A + B вместе со стрелками inl и inr, определяет функцию, которая по
некоторому объекту C и двум стрелкам f и g строит стрелку h, которая ведёт из объекта A + B в объект
C. Этот процесс определения стрелки по объекту напоминает определение начального элемента. Построим
специальную категорию, в которой объект A+ B будет начальным. Тогда функция out будет катаморфизмом.
Функция out принимает две стрелки и возвращает третью. Посмотрим на типы:
f : A > C
inl : A > A + B
g : B > C
inr : B > A + B
Каждая из пар стрелок в столбцах указывают на один и тот же объект, а начинаются они из двух разных
объектов A и B. Определим категорию, в которой объектами являются пары стрелок ( a 1 , a 2), которые на-
чинаются из объектов A и B и заканчиваются в некотором общем объекте D. Эту категорию ещё называют
клином. Стрелками в этой категории будут такие стрелки f : ( d 1 , d 2) > ( e 1 , e 2), что стрелки в следующей
диаграмме коммутируют (не важно по какому пути идти из двух разных точек).
A
B
d
e
1
2
e 1
d 2
D
E
f
Композиция стрелок – это обычная композиция в исходной категории, в которой определены объекты A
и B, а тождественная стрелка для каждого объекта, это тождественная стрелка для того объекта, в котором