естественную интерпретацию. Если у нас есть способ 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
Теперь вспомним о категории Hask. В этой категории объектами являются типы, а стрелками функции.
Функтор f отображает объекты и стрелки категории Hask в объекты и стрелки f Hask. При этом оказывается,
что за счёт свойств функтора f Hask образует категорию.
• Объекты – это типы f a.
• Стрелки – это функции fmap f.
• Композиция стрелок это просто композиция функций.
• Тождественная стрелка это fmap id.
Проверим аксиомы:
fmap f . fmap id = fmap f . id = fmap f
fmap id . fmap f = id . fmap f = fmap f
fmap f . (fmap g . fmap h)
=
fmap f . fmap (g . h)
=
fmap (f . (g . h))
=
fmap ((f . g) . h)
=
fmap (f . g) . fmap h
=
(fmap f . fmap g) . fmap h
Функтор | 229
Видно, что аксиомы выполнены, так функтор f порождает категорию f Hask. Интересно, что поскольку
Hask содержит все типы, то она содержит и типы f Hask. Получается, что мы построили категорию внутри
категории. Это можно пояснить на примере списков. Тип [] погружает любой тип в список, а функцию для
любого типа можно превратить в функцию, которая работает на списках с помощью метода fmap. При этом с
помощью класса Functor мы проецируем все типы и все функции в мир списков [a]. Но сам этот мир списков
содержится в категории Hask.
С помощью функторов мы строим внутри одной категории другую категорию, при этом внутренняя ка-
тегория обладает некоторой структурой. Так если раньше у нас были только произвольные типы a и произ-
вольные функции a -> b, то теперь все объекты имеют тип [a] и все функции имеют тип [a] -> [b]. Также и
функтор Maybe переводит произвольное значение, в значение, которое обладает определённой структурой. В
нём выделен дополнительный элемент Nothing, который обозначает отсутствие значения. Если по типу val
:: a мы ничего не можем сказать о содержании значения val, то по типу val :: Maybe a, мы знаем один
уровень конструкторов. Например мы уже можем проводить сопоставление с образцом.
Теперь давайте вернёмся к теории категорий и дадим формальное определение понятия. Пусть A и B –
категории, тогда функтором из A в B называют отображение F , которое переводит объекты A в объекты B
и стрелки A в стрелки B, так что выполнены следующие свойства:
F f
:
F A >B F B если f : A >A B
F idA
=
idF A
для любого объекта A из A
F ( f ; g)
=
F f ; F g
если ( f ; g) подходят по типам
Здесь запись >A и >B означает, что эти стрелки в разных категориях. После отображения стрелки f
из категории A мы получаем стрелку в категории B, это и отражено в типе F f : F A >B F B. Первое
свойство говорит о том, что после отображения стрелки соединяют те же объекты, что и до отображения.
Второе свойства говорит о сохранении тождественных стрелок. А последнее свойство, говорит о том, что
“пути” между объектами также сохраняются. Если мы находимся в категории A в объекте A и перед нами
есть путь состоящий из нескольких стрелок в объект B, то неважно как мы пойдём в F B либо мы пройдём
этот путь в категории A и в самом конце переместимся в F B или мы сначала переместимся в F A и затем
