Учебник по Haskell

. . .

A 1

A 2

. . .

0

A 3

. . .

. . .

A 4

Такой объект называют начальным (initial object). Его принято обозначать нулём, словно это начало от-

счёта. Для любого объекта A из категории A с начальным объектом 0 существует и только одна стрел-

ка f : 0 → B. Можно сказать, что начальный объект определяет функцию, которая переводит объекты A в

стрелки f : 0 → A. Эту функцию обозначают специальными скобками ( | · |), она называется катаморфизмом

(catamorphism).

( | A |) = f : 0 → A

У начального объекта есть несколько важных свойств. Они очень часто встречаются в разных вариациях,

в понятиях, которые определяются через понятие начального объекта:

( | 0 |) = id 0

тождество

f, g : 0 → A ⇒ f = g

уникальность

f : A → B

⇒ ( | A |) ; f = ( | B |)

слияние (fusion)

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

ведущая из начального объекта в начальный является тождественной стрелкой. В самом деле по определе-

нию начального объекта для каждого объекта может быть только одна стрелка, которая начинается в 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