Учебник по Haskell

стрелки – маленькими буквами f, g, h, … Для того чтобы связи было интереснее изучать мы введём такое

правило:

f

A

B

g

f ; g

C

Если конец стрелки f указывает на начало стрелки g, то должна быть такая стрелка f ; g, которая обозна-

чает составную стрелку. Вводится специальная операция “точка с запятой”, которая называется композицией

стрелок: Это правило говорит о том, что связи распространяются по объектам. Теперь у нас есть не просто

объекты и стрелки, а целая сеть объектов, связанных между собой. Тот факт, что связи действительно рас-

пространяются отражается свойством:

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)