Учебник по Haskell

• T ηA ; µA = idTA

• T µA ; µTA = µTTA ; µA

Преобразование η – это функция return, а преобразование µ – это функция join. В теории категорий в

классе Monad другие методы. Перепишем эти свойства в виде функций Haskell:

join . fmap return

= id

join . fmap join

= join . join

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

точку). Выражение T ηA означает применение функтора T к стрелке ηA. Ведь преобразование это семейство

стрелок, которые параметризованы объектами категории. На языке Haskell это означает применить fmap к

полиморфной функции (функции с параметром).

Также эти свойства можно изобразить графически:

T η

T A

A

µ

T T A

A

T A

T µ

T T T A

A

T T A

µT A

µA

T T A

T A

µA

Категория Клейсли

Если у нас есть монада T , определённая в категории A, то мы можем построить в этой категории кате-

горию специальных стрелок вида A → T B. Эту категорию называют категорией Клейсли.

• Объекты категории Клейсли AT – это объекты исходной категории A.

232 | Глава 15: Теория категорий

• Стрелки в AT это стрелки из A вида A → T B, мы будем обозначать их A →T B

• Композиция стрелок f : A →T B и g : B →T C определена с помощью естественных преобразований

монады T :

f ; T g = f ; T g ; µ

Значок ; T указывает на то, что слева от равно композиция в AT . Справа от знака равно используется

композиция в исходной категории A.

• Тождественная стрелка – это естественное преобразование η.

Можно показать, что категория Клейсли действительно является категорией и свойства операций компо-

зиции и тождества выполнены.

15.5 Дуальность

Интересно, что если в категории A перевернуть все стрелки, то снова получится категория. Попробуйте

нарисовать граф со стрелками, и затем мысленно переверните направление всех стрелок. Все пути исход-

ного графа перейдут в перевёрнутые пути нового графа. При этом пути будут проходить через те же точки.

Сохранятся композиции стрелок, только все они будут перевёрнуты. Такую категорию обозначают Aop. Но

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

о категориях, эту операцию называют дуализацией. Определим её:

dual A

=

A

если A является объектом

dual x

=

x

если x обозначает стрелку

dual ( f : A → B) = dual f : B → A

A и B поменялись местами

dual ( f ; g)

=

dual g ; dual f

f и g поменялись местами

dual ( idA)

=

idA

Есть такое свойство, если и в исходной категории A выполняется какое-то утверждение, то в перевёр-

нутой категории Aop выполняется перевёрнутое (дуальное) свойство. Часто в теории категорий из одних

понятий получают другие дуализацией. При этом мы можем не проверять свойства для нового понятия,

они будут выполняться автоматически. К дуальным понятиям обычно добавляют приставку “ко”. Приведём

пример, получим понятие комонады.

Для начала вспомним определение монады. Монада – это эндофунктор (функтор, у которого совпадают

начало и конец или домен и кодомен) T : A → A и два естественных преобразования η : I → T и

µ : T T → T , такие что выполняются свойства:

• T η ; µ = id

• T µ ; µ = µ ; µ

Дуализируем это определение. Комонада – это эндофунктор T : A → A и два естественных преобразо-

вания η : T → I и µ : T T → T , такие что выполняются свойства

• µ ; T η = id

• µ ; T µ = µ ; µ

Мы просто переворачиваем домены и кодомены в стрелках и меняем порядок в композиции. Проверьте

сошлись ли типы. Попробуйте нарисовать графическую схему свойств комонады и сравните со схемой для

монады.

Можно также определить и категорию коКлейсли. В категории коКлейсли все стрелки имеют вид T A →

B. Теперь дуализируем композицию из категории Клейсли:

f ; T g = f ; T g ; µ

Теперь получим композицию в категории коКлейсли:

g ; T f = µ ; T g ; f

Мы перевернули цепочки композиций слева и справа от знака равно. Проверьте сошлись ли типы. Не

забывайте что в этом определении η и µ естественные преобразования для комонады. Нам не нужно прове-

рять является ли категория коКлейсли действительно категорией. Нам не нужно опять проверять свойства

Дуальность | 233

стрелки тождества и ассоциативности композиции, если мы уже проверили их для монады. Следовательно

перевёрнутое утверждение будет выполняться в перевёрнутой категории коКлейсли. В этом основное пре-

имущество определения через дуализацию.

Этим приёмом мы можем воспользоваться и в Haskell, дуализируем класс Monad:

class Monad m where

return

:: a -> m a

(>>=)

:: m a -> (a -> m b) -> m b

Перевернём все стрелки:

class Comonad c where

coreturn

:: c a -> a

cobind

:: c b -> (c b -> a) -> c a

15.6 Начальный и конечный объекты

Начальный объект

Представим, что в нашей категории есть такой объект 0, который соединён со всеми объектами. При-

чём стрелка начинается из этого объекта и для каждого объекта может быть только одна стрелка которая

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