Unknown - haskell-notes

• Композиция стрелок 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 Monadm where

return

::a ->m a

( >>=)

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

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

class Comonadc where

coreturn

::c a ->a

cobind

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

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

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

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

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