Unknown - haskell-notes

соединят данный объект с 0. Графически эту ситуацию можно изобразить так:

. . .

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 Eithera b = Lefta | Rightb

Произведение в самом общем виде представлено кортежами:

data(a, b) =(a, b)

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

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

тами. Взаимодействие обозначается с помощью стрелок. Специальные свойства стрелок определяют объект.

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

ствовать с объектом, который представляет собой сумму двух типов A + B ? Нам необходимо уметь создавать

объект типа A + B из объектов A и B извлекать их из суммы. Создание объектов происходит с помощью