Unknown - haskell-notes

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

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 )

Можно убедиться в том, что это действительно категория. Для этого необходимо проверить аксиомы

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

позиции, не нарушали бы основного свойства данной структуры, то есть тот факт, что второй элемент

пары всегда больше либо равен первого элемента пары.

Отметим, что бывают такие области, в которых стрелки или преобразования с одинаковыми именами