text: <#define currentChapter |15>
  
  <!-- Switch argument character to $ to escape |  -->
  <#mode save>
  <#mode user |"<#" ">" "\B" "$" ">" "<" ">" "#" "">
  
  <#html
  \newcommand{\Or}[0]{\ |\ }
  \newcommand{\cata}[1]{(\hspace{-1.8pt}|\,#1\,|\hspace{-1.8pt})}
  >
  <#mode restore>
  
  <#html
  \newcommand{\Ra}[0]{\rightarrow }
  \newcommand{\RA}[0]{\Rightarrow }
  \newcommand{\Br}[1]{\{#1\} }
  
  \newcommand{\Co}{\:\mathbf{;}\:}
  \newcommand{\CoT}{\:\mathbf{;_{T}}\:}
  \newcommand{\Ha}{\In{H}}
  \newcommand{\CatA}{\mathcal{A}}
  \newcommand{\CatB}{\mathcal{B}}
  \newcommand{\ana}[1]{[\hspace{-2.4pt}(\,#1\,)\hspace{-2.4pt}]}
  
  \newcommand{\Alg}{\textbf{Alg}(F)} 
  \newcommand{\CoAlg}{\textbf{CoAlg}(F)} 
  >
  
  # Теория категорий
  
  Многие понятия в Haskell позаимствованы из теории
  категорий, например это функторы, монады. Теория категорий --
  это скорее язык, математический жаргон, она настолько общая,
  что кажется ей нет никакого применения. Возможно это
  и так, но в этом языке многие сущности, которые лишь
  казались родственными и было смутное интуитивное ощущение
  их близости, становятся тождественными.
  
  Теория категорий занимается описанием функций. 
  В лямбда-исчислении основной операцией была подстановка
  значения в функцию, а в теории категорий мы сосредоточимся
  на операции композиции. Мы будем соединять различные объекты
  так, чтобы структура объектов сохранялась. Структура 
  объекта будет определяться свойствами, которые продолжают 
  выполнятся после преобразования объекта.
  
  ## Категория
  
  Мы будем говорить об объектах и связях между ними. 
  Связи принято называть "стрелками" или 
  "морфизмами". Далее мы будем пользоваться 
  термином стрелка. У стрелки есть начальный объект,
  его называют *доменом* (domain) и конечный объект,
  его называют *кодоменом* (codomain). 
  
  <#tikz_ arrow>
  
  В этой записи стрелка $f$ соединяет объекты $A$ и $B$,
  в тексте мы будем писать это так $f:A \Ra B$, словно
  стрелка это функция, а объекты это типы.
  Мы будем обозначать объекты большими буквами $A$, $B$, $C$, ...,
  а стрелки -- маленькими буквами $f$, $g$, $h$, ...
  Для того чтобы связи было интереснее изучать мы введём такое 
  правило:
  
  <#tikz_ composition>
  
  Если конец стрелки $f$ указывает на начало стрелки $g$, 
  то должна быть такая стрелка $f \Co g$, которая обозначает
  *составную* стрелку. Вводится специальная 
  операция "точка с запятой", 
  которая называется композицией стрелок:
  Это правило говорит о 
  том, что связи распространяются по объектам.
  Теперь у нас есть не просто объекты и стрелки, а целая сеть
  объектов, связанных между собой. Тот факт, что связи действительно
  распространяются отражается свойством:
  
  $$f \Co (g \Co h) = (f \Co g) \Co h$$
  
  Это свойство называют ассоциативностью. Оно говорит о том,
  что стрелки, которые образуют составную стрелку являются
  цепочкой и нам не важен порядок их группировки, важно
  лишь кто за кем идёт. Подразумевается, что стрелки $f$, $g$
  и $h$ имеют подходящие типы для композиции, что их можно
  соединять. Это свойство похоже на интуитивное понятие
  пути, как цепочки отрезков. 
  
  Связи между объектами можно трактовать как преобразования
  объектов. Стрелка $f : A \Ra B$ -- это способ, с помощью которого
  мы можем перевести объект $A$ в объект $B$. Композиция 
  в этой аналогии приобретает естественную интерпретацию. Если 
  у нас есть способ $f : A \Ra B$ преобразования объекта
  $A$ в объект $B$, и способ $g : B \Ra C$ преобразования 
  объекта $B$ в объект $C$, то мы конечно можем, применив
  сначала $f$, а затем $g$, получить из объекта $A$ объект $C$.
  
  Когда мы думаем о стрелках как о преобразовании, то 
  естественно предположить, что у нас есть преобразование,
  которое ничего не делает, как тождественная функция. 
  В будем говорить, что для каждого объекта $A$ есть стрелка $id_A$,
  которая начинается из этого объекта и заканчивается в нём же.
  
  $$id_A : A \Ra A$$
  
  Тот факт, что стрелка $id_A$ ничего не делает отражается
  свойствами, которые должны выполняться для всех стрелок:
  
  <#html
  --------------     -----------      -------
  $id_A \Co f$           $=$          $f$
  $f \Co id_A$           $=$          $f$
  --------------     -----------      -------
  >
  
  <#tex
  \begin{eqnarray*}
  id_A \Co f &=& f \\
  f \Co id_B &=& f \\
  \end{eqnarray*}
  >
  
  Если мы добавим к любой стрелке тождественную стрелку,
  то от этого ничего не изменится. 
  
  Всё готово для того чтобы дать формальное определение понятия
  \Structs{категории} *категории* (category). Категория это:
  
  
  *   Набор *объектов* (object).
  
  *   Набор *стрелок* (arrow) или *морфизмов* (morphism).
  
  *   Каждая стрелка соединяет два объекта, но объекты могут совпадать. 
      Так обозначают, что стрелка $f$ начинается в объекте $A$ и заканчивается 
      в объекте $B$:
  
      $$f : A \Ra B$$
  
      При этом стрелка соединяет только два объекта:
  
      $$f : A \Ra B,\ f : A' \Ra B' \qquad \RA \qquad A=A',\ B=B'$$
  
  *   Определена операция композиции или соединения стрелок. 
      Если конец одной стрелки совпадает с началом другой,
      то их можно соединить вместе:
  
      $$f:A \Ra B,\ g : B\Ra C \quad \RA \quad f \Co g : A \Ra C$$
  
  *   Для каждого объекта есть стрелка, которая начинается
      и заканчивается в этом объекте. Эту стрелку называют
      *тождественной* (identity):
  
      $$id_A : A \Ra A$$
  
  
  Должны выполняться аксиомы:
  
          
  *   Тождество $id$
  
      $$id \Co f = f$$
  
      $$f \Co id = f$$
  
  *   Ассоциативность $\Co$
  
      $$f \Co (g \Co h) = (f \Co g) \Co h$$
  
  
  Приведём примеры категорий. 
  
  
  *   Одна точка с одной тождественной стрелкой образуют категорию.
  
  *   В категории **Set** объектами являются все множества,
      а стрелками -- функции. Стрелки соединяются с помощью композиции
      функций, тождественная стрелка, это тождественная функция.
  
  *   В категории **Hask** объектами являются типы Haskell,
          а стрелками -- функции, стрелки соединяются с помощью
          композиции функций, тождественная стрелка, это тождественная
          функция. 
          
  *   Ориентированный граф может определять категорию. 
      Объекты -- это вершины, а стрелки это связанные пути 
      в графе. Соединение стрелок -- это соединение путей,
      а тождественная стрелка, это путь в котором нет ни одного ребра.
      
  *   Упорядоченное множество, в котором есть операция сравнения
      на больше либо равно задаёт категорию. Объекты -- это объекты
      множества. А стрелки это пары объектов таких, что первый
      объект меньше второго. Первый объект в паре считается начальным,
      а второй конечным. 
      
      $$(a, b) : a \Ra b  \qquad \text{если } a \leq b$$
      
      Стрелки соединяются так:
  
      $$(a, b) \Co (b, c) = (a, c)$$
  
      Тождественная стрелка состоит из двух одинаковых объектов:
  
      $$id_a = (a, a)$$
      
      Можно убедиться в том, что это действительно категория.
      Для этого необходимо проверить аксиомы ассоциативности и тождества.
      Важно проверить, что те стрелки, которые получаются в результате композиции,
      не нарушали бы основного свойства данной структуры, то есть тот
      факт, что второй элемент пары всегда больше либо равен первого
      элемента пары.
  
  
  
  Отметим, что бывают такие области, в которых стрелки или преобразования
  с одинаковыми именами могут соединять несколько разных
  объектов. Например в Haskell есть классы, поэтому функции с одними и теми
  же именами могут соединять разные объекты. Если все условия категории для
  объектов и стрелок выполнены, кроме этого, то такую систему
  называют *прекатегорией* (pre-category). Из любой прекатегории
  не сложно сделать категорию, если включить имена объектов в имя
  стрелки. Тогда у каждой стрелки будут только одна пара объектов,
  которые она соединяет. 
  
  ## Функтор
  
  Вспомним определение класса `Functor`:
  
  ~~~
  class Functor f where
      fmap :: (a -> b) -> (f a -> f b)
  ~~~
  
  В этом определении участвуют тип `f` и метод `fmap`.
  Можно сказать, что тип `f` переводит произвольные типы `a` в 
  специальные типы `f a`. В этом смысле тип `f` является функцией, которая
  определена на типах. Метод `fmap` переводит функции общего
  типа `a -> b` в специальные функции `f a -> f b`. 
  
  При этом должны выполняться свойства:
  
  ~~~
  fmap id  = id
  fmap (f . g) = fmap f . fmap g
  ~~~
  
  Теперь вспомним о категории `Hask`. В этой категории объектами являются
  типы, а стрелками функции. Функтор  `f` отображает объекты и 
  стрелки категории `Hask` в объекты и стрелки `f Hask`.
  При этом оказывается, что за счёт свойств функтора `f Hask`
  образует категорию. 
  
  
  *   Объекты -- это типы `f a`.
  
  *   Стрелки -- это функции `fmap f`.
  
  *   Композиция стрелок это просто композиция функций.
  
  *   Тождественная стрелка это `fmap id`.
  
  
  Проверим аксиомы:
  
  ~~~
  fmap f . fmap id = fmap f . id = fmap f
  fmap id . fmap f = id . fmap f = fmap f
  
      fmap f . (fmap g . fmap h) 
  =   fmap f . fmap (g . h) 
  =   fmap (f . (g . h))
  =   fmap ((f . g) . h)
  =   fmap (f . g) . fmap h
  =   (fmap f . fmap g) . fmap h
  ~~~
  
  Видно, что аксиомы выполнены, так функтор `f` порождает
  категорию `f Hask`. Интересно, что поскольку `Hask`
  содержит все типы, то она содержит и типы `f Hask`. 
  Получается, что мы построили категорию внутри категории. 
  Это можно пояснить на примере списков. Тип `[]`
  погружает любой тип в список, а функцию для любого типа
  можно превратить в функцию, которая работает на списках с 
  помощью метода `fmap`. При этом с помощью класса `Functor`
  мы проецируем все типы и все функции в мир списков `[a]`.
  Но сам этот мир списков содержится в категории `Hask`.
  
  С помощью функторов мы строим внутри одной категории 
  другую категорию, при этом внутренняя категория обладает
  некоторой структурой. Так если раньше у нас были только произвольные
  типы `a` и произвольные функции `a -> b`, то теперь
  все объекты имеют тип `[a]` и все функции имеют тип
  `[a] -> [b]`. Также и функтор `Maybe` переводит произвольное значение,
  в значение, которое обладает определённой структурой. 
  В нём выделен дополнительный элемент `Nothing`, который 
  обозначает отсутствие значения. Если по типу `val :: a` 
  мы ничего не можем сказать о содержании значения `val`,
  то по типу `val :: Maybe a`, мы знаем один уровень
  конструкторов. Например мы уже можем проводить сопоставление
  с образцом.
  
  Теперь давайте вернёмся к теории категорий и дадим формальное 
  определение понятия. Пусть $\CatA$ и $\CatB$ -- категории,
  тогда \Structs{функторы}
  *функтором* из $\CatA$ в $\CatB$ называют отображение
  $F$, которое переводит объекты $\CatA$ в объекты $\CatB$ и
  стрелки $\CatA$ в стрелки $\CatB$, так что выполнены следующие
  свойства:
  
  <#html
  ---------------    ------   -------                 --------------------------
  $F f$               $:$     $FA \Ra_{\CatB} FB$     если  $f: A \Ra_{\CatA} B$
  $F id_A$            $=$     $id_{FA}$               для любого объекта 
                                                      $A$ из $\CatA$
  $F (f \Co g)$       $=$     $Ff \Co Fg$             если $(f \Co g)$
  ----------------   -------  -------                 --------------------------
  >
  
  <#tex
  \begin{equation*}\begin{array}{llll}
  F f     &:& FA \Ra_{\CatB} FB & \text{если } f: A \Ra_{\CatA} B \\
  F id_A  &=& id_{FA}           & \text{для любого объекта } A \text{ из } \CatA\\
  F (f \Co g) &=& Ff \Co Fg     & \text{если } (f \Co g)
  \text{ подходят по типам}\\
  \end{array}\end{equation*}
  >
  
  Здесь запись $\Ra_\CatA$ и $\Ra_\CatB$ означает, что эти стрелки
  в разных категориях. После отображения стрелки $f$
  из категории $\CatA$ мы получаем стрелку в категории $\CatB$,
  это и отражено в типе $Ff : FA \Ra_\CatB FB$. Первое свойство
  говорит о том, что после отображения стрелки соединяют те же объекты,
  что и до отображения. Второе свойства говорит о сохранении тождественных
  стрелок. А последнее свойство, говорит о том, что "пути" 
  между объектами также сохраняются. Если мы находимся в категории
  $\CatA$ в объекте $A$ и перед нами есть путь состоящий
  из нескольких стрелок в объект $B$, то неважно как мы пойдём
  в $FB$ либо мы пройдём этот путь в категории $\CatA$ и в самом
  конце переместимся в $FB$ или мы сначала переместимся в $FA$
  и затем пройдём по образу пути в категории $FB$. Так и так мы попадём
  в одно и то же место. Схематически это можно изобразить так:
  
  <#tikz_ functor>
  
  Стрелки сверху находятся в категории $\CatA$, а стрелки
  снизу находятся в категории $\CatB$. Функтор $F : \CatA \Ra \CatA$, 
  который переводит категорию $\CatA$ в себя называют 
  \Structs{эндофункторы}
  *эндофунктором* (endofunctor). Функторы отображают
  одни категории в другие сохраняя структуру первой категории. 
  Мы словно говорим, что внутри второй категории есть 
  структура подобная первой. Интересно, что последовательное
  применение функторов, также является функтором. Мы будем
  писать последовательное применение функторов $F$ и $G$ 
  слитно, как $FG$. Также можно определить
  и тождественный функтор, который ничего не делает с категорией,
  мы будем обозначать его как $I_\CatA$ или просто $I$, если
  категория на которой он определён понятна из контекста.
  Это говорит о том, что мы можем построить категорию, в которой
  объектами будут другие категории, а стрелками будут функторы.
  
  ## Естественное преобразование
  
  В программировании часто приходится переводить данные из 
  одной структуры в другую. Каждая из структур хранит какие-то
  конкретные значения, но мы ничего с ними не делаем мы просто
  перекладываем содержимое из одного ящика в другой. 
  Например в нашем ящике только один отсек, но вдруг
  нам пришло бесконечно много подарков, что поделать нам
  приходится сохранить первый попавшийся, отбросив остальные.
  Главное в этой аналогии это то, что мы ничего не меняем, а 
  лишь перекладываем содержимое из одной структуры в другую.
  
  В Haskell это можно описать так:
  
  ~~~
  onlyOne :: [a] -> Maybe a
  onlyOne []      = Nothing
  onlyOne (a:as)  = Just a
  ~~~
  
  В этой функции мы перекладываем элементы из списка `[a]`
  в частично определённое значение `Maybe`. 
  Тоже самое происходит и в функции `concat`:
  
  ~~~
  concat :: [[a]] -> [a]
  ~~~
  
  Элементы перекладываются из списка списков в один список. 
  В теории категорий этот процесс называется естественным
  преобразованием. Структуры определяются функторами. 
  Поэтому в определении будет участвовать два функтора.
  В функции `onlyOne` это были функторы `[]` и `Maybe`.
  При перекладывании элементов мы можем
  просто выбросить все элементы:
  
  ~~~
  burnThemALl :: [a] -> ()
  burnThemAll = const ()
  ~~~
  
  Можно сказать, что единичный тип также определяет функтор.
  Это константный функтор, он переводит любой тип в 
  единственное значение `()`, а функцию в `id`:
  
  ~~~
  data Empty a = Empty
  
  instance Functor Empty where
      fmap = const id
  ~~~
  
  Тогда тип функции `burnThemAll` будет параметризован и слева и 
  справа от стрелки:
  
  ~~~
  burnThemAll :: [a] -> Empty a
  burnThemAll = const Empty
  ~~~
  
  Пусть даны две категории $\CatA$ и $\CatB$ и два функтора
  $F,G : \CatA \Ra \CatB$. *Преобразованием* (transformation)
  в $\CatB$ из $F$ в $G$ называют семейство стрелок $\varepsilon$:
  
  $$\varepsilon_A : FA \Ra_\CatB GA 
          \qquad \text{для любого } A \text{ из } \CatA$$
  
  Рассмотрим преобразование `onlyOne :: [a] -> Maybe a`. 
  Категории $\CatA$ и $\CatB$ в данном случае совпадают~-- 
  это категория `Hask`. Функтор $F$ -- это список, а функтор
  $G$ это `Maybe`. Преобразование `onlyOne` для 
  каждого объекта `a` из `Hask` определяет стрелку
  
  ~~~
  onlyOne :: [a] -> Maybe a
  ~~~
  
  Так мы получаем семейство стрелок, параметризованное объектом из `Hask`:
  
  ~~~
  onlyOne :: [Int] -> Maybe Int
  onlyOne :: [Char] -> Maybe Char
  onlyOne :: [Int -> Int] -> Maybe (Int -> Int)
  ...
  ...
  ~~~
  
  Теперь давайте определим, что значит перекладывать из одной
  структуры в другую, не меняя содержания. Представим, что функтор --
  это контейнер. Мы можем менять его содержание с помощью
  метода `fmap`. Например мы можем прибавить единицу ко
  всем элементам списка `xs` с помощью выражения \mbox{\In{fmap (+1) xs}}.
  Точно так же мы можем прибавить единицу к частично определённому
  значению. С точки зрения теории категорий суть понятия 
  "останется неизменным при перекладывании" заключается
  в том, что если мы возьмём любую функцию к примеру прибавление
  единицы, то нам неважно когда её применять до функции `onlyOne`
  или после. И в том и в другом случае мы получим одинаковый
  ответ. Давайте убедимся в этом:
  
  ~~~
      onlyOne $ fmap (+1) [1,2,3,4,5]
  =>  onlyOne [2,3,4,5,6]
  =>  Just 2
  
      fmap (+1) $ onlyOne [1,2,3,4,5]
  =>  fmap (+1) $ Just 1
  =>  Just 2
  ~~~
  
  Результаты сошлись, обратите внимание на то, что функции
  `fmap (+1)` в двух вариантах являются разными функциями.
  Первая работает на списках, а вторая на частично определённых 
  значениях. Суть в том, что если при перекладывании значение
  не изменилось, то нам не важно когда выполнять преобразование
  внутри функтора `[]` или внутри функтора `Maybe`. 
  Теперь давайте выразим это на языке теории категорий.
  
  Преобразование $\varepsilon$ в категории $\CatB$ из 
  функтора $F$ в функтор $G$ называют 
  \Structs{естественные преобразования}
  *естественным* (natural), если 
  
  $$Ff \Co \varepsilon_B \ =\ \varepsilon_A \Co Gf 
      \qquad \text{для любого } f : A \Ra_\CatA B$$
  
  Это свойство можно изобразить графически:
  
  <#tikz_ natural>
  
  По смыслу ясно, что если у нас есть три структуры данных 
  (или три функтора), и мы просто переложили данные из первой
  во вторую, а затем переложили данные из второй в третью,
  ничего не меняя, то итоговое преобразование, которое составлено из
  последовательного применения перекладывания данных, также
  не меняет данные. Это говорит о том, что композиция двух
  естественных преобразований также является естественным 
  преобразованием. 
  Также мы можем составить тождественное
  преобразование: для двух одинаковых функторов $F : \CatA \Ra \CatB$, 
  это будет семейство тождественных стрелок в \mbox{категории $\CatB$}.
  Получается, что для двух категорий $\CatA$ и $\CatB$ мы
  можем составить категорию $Ftr(\CatA,\CatB)$, в которой
  объектами будут функторы из $\CatA$ в $\CatB$, а стрелками
  будут естественные преобразования. Поскольку естественные
  преобразования являются стрелками, которые соединяют
  функторы, мы будем обозначать их как обычные
  стрелки. Так запись $\eta : F \Ra G$ обозначает 
  преобразование $\eta$, которое  переводит функтор $F$ 
  в функтор $G$.
  
  Интересно, что изначально создатели теории категорий
  Саундедерс Маклейн и Сэмюэль Эйленберг придумали понятие
  естественного преобразования, а затем, чтобы дать ему обоснование
  было придумано понятие функтора, и наконец для того чтобы
  дать обоснование функторам были придуманы категории.
  Категории содержат объекты и стрелки, для стрелок есть
  операция композиции. Также для каждого объекта есть
  тождественная стрелка. Функторы являются стрелками 
  в категории, в которой объектами являются другие категории.
  А естественные преобразования являются стрелками в категории,
  в которой объектами являются функторы. Получается такая иерархия
  структур.
  
  
  ## Монады
  
  \Structs{монады}
  *Монадой* называют эндофунктор $T:\CatA \Ra \CatA$, для 
  которого определены два естественных преобразования $\eta : I \Ra T$ и
  $\mu : TT \Ra T$ и выполнены два свойства:
  
  
  *   $T \eta_A \Co \mu_{A} \ =\ id_{TA}$
  
  *   $T \mu_A \Co \mu_{A} = \mu_{TA} \Co \mu_A$ 
  
  
  Преобразование $\eta$ -- это функция `return`, а 
  преобразование $\mu$ -- это функция `join`. В теории 
  категорий в классе `Monad` другие методы. Перепишем эти
  свойства в виде функций Haskell:
  
  ~~~
  join . fmap return   = id
  join . fmap join     = join . join
  ~~~
  
  Порядок следования аргументов изменился, потому что мы
  пользуемся обычной композицией (через точку). 
  Выражение $T \eta_A$ означает применение функтора 
  $T$ к стрелке $\eta_A$. Ведь преобразование это семейство
  стрелок, которые параметризованы объектами категории. 
  На языке Haskell это означает применить `fmap` к
  полиморфной функции (функции с параметром).
  
  Также эти свойства можно изобразить графически:
  
  <#tikz_ monad1>
  <#tikz_ monad2>
  
  ### Категория Клейсли
  
  Если у нас есть монада $T$, определённая в категории $\CatA$,
  то мы можем построить в этой категории категорию специальных
  стрелок вида $A \Ra TB$. Эту категорию называют категорией Клейсли.
  
  
  *   Объекты категории Клейсли $\CatA_T$ -- это объекты 
      исходной категории $\CatA$.
  
  *   Стрелки в $\CatA_T$ это стрелки из $\CatA$ вида $A \Ra TB$,
          мы будем обозначать их $A \Ra_T B$
  
  *   Композиция стрелок $f : A \Ra_T B$ и $g : B \Ra_T C$ определена
      с помощью естественных преобразований монады $T$:
  
      $$f \CoT g = f \Co Tg \Co \mu$$
  
      Значок $\CoT$ указывает на то, что слева от равно композиция в $\CatA_T$.
      Справа от знака равно используется композиция в исходной категории $\CatA$.
  
  *   Тождественная стрелка -- это естественное преобразование $\eta$.
  
  Можно показать, что категория Клейсли действительно является
  категорией и свойства операций композиции и тождества 
  выполнены.
  
  ## Дуальность 
  
  Интересно, что если в категории $\CatA$ перевернуть все
  стрелки, то снова получится категория. Попробуйте нарисовать
  граф со стрелками, и затем мысленно переверните направление 
  всех стрелок. Все пути исходного графа перейдут в перевёрнутые
  пути нового графа. При этом пути будут проходить через те же
  точки. Сохранятся композиции стрелок, только все они будут
  перевёрнуты. Такую категорию обозначают $\CatA^{op}$. 
  Но оказывается, что переворачивать мы можем не только
  категории но и свойства категорий, или утверждения о
  категориях, эту операцию называют *дуализацией*. 
  Определим её:
  
  <#html
  -------------------     ----------------------      --------                ---------       -------------------------------
  $dual\ A$                  $\quad = \quad$          $A$                     $\qquad$        если $A$ является объектом
  $dual\ x$                  $\quad = \quad$          $x$                                     если $x$ обозначает стрелку
  $dual\ (f : A \Ra B)$      $\quad = \quad$          $dual\ f : B \Ra A$                     $A$ и $B$ поменялись местами
  $dual\ (f \Co g)$          $\quad = \quad$          $dual\ g \Co dual\ f$                   $f$ и $g$ поменялись местами
  $dual\ (id_A)$             $\quad = \quad$          $id_A$
  -------------------     ----------------------      --------                                -------------------------------
  >
  
  <#tex
  \begin{equation*}\begin{array}{l@{\quad = \quad}l@{\qquad}l}
  dual\ A & A  &  \text{если } A \text{ является объектом} \\
  dual\ x & x  &  \text{если } x \text{ обозначает стрелку} \\
  dual\ (f : A \Ra B) & dual\ f : B \Ra A 
                      & \text{$A$ и $B$ поменялись местами} \\
  dual\ (f \Co g) & dual\ g \Co dual\ f 
                      & \text{$f$ и $g$ поменялись местами} \\
  dual\ (id_A) & id_A & \\
  \end{array}\end{equation*}
  >
  
  Есть такое свойство: если в исходной категории $\CatA$
  выполняется какое-то утверждение, то в перевёрнутой категории
  $\CatA^{op}$ выполняется перевёрнутое (дуальное) свойство.
  Часто в теории категорий из одних понятий получают другие
  дуализацией. При этом мы можем не проверять свойства для
  нового понятия - они будут выполняться автоматически.
  К дуальным понятиям обычно добавляют приставку "ко".
  Приведём пример, получим понятие комонады.
  
  Для начала вспомним определение монады. Монада -- это 
  эндофунктор (функтор, у которого совпадают начало и конец
  или домен и кодомен) $T : \CatA \Ra \CatA$ и два естественных
  преобразования $\eta : I \Ra T$ и $\mu : TT \Ra T$,
  такие что выполняются свойства:
  
  *   $T \eta \Co \mu = id$
  
  *   $T \mu \Co \mu = \mu \Co \mu$
  
  
  Дуализируем это определение. Комонада -- это эндофунктор
  $T : \CatA \Ra \CatA$ и два естественных преобразования
  $\eta : T \Ra I$ и $\mu : T \Ra TT$, такие, что  выполняются
  свойства
  
  *   $\mu \Co T \eta = id$
  
  *   $\mu \Co T \mu = \mu \Co \mu$
  
  
  Мы просто переворачиваем домены и кодомены в стрелках и
  меняем порядок в композиции. Проверьте, сошлись ли типы. 
  Попробуйте нарисовать графическую схему свойств комонады 
  и сравните со схемой для монады. 
  
  Можно также определить и категорию коКлейсли.
  В категории коКлейсли все стрелки имеют вид $TA \Ra B$. 
  Теперь дуализируем композицию из категории Клейсли:
  
  $$f \CoT g = f \Co Tg \Co \mu$$
  
  Теперь получим композицию в категории коКлейсли:
  
  $$g \CoT f = \mu \Co Tg \Co f$$
  
  Мы перевернули цепочки композиций слева и справа от знака
  равно. Проверьте, сошлись ли типы. Не забывайте, что в
  этом определении $\eta$ и $\mu$ естественные преобразования
  для комонады. Нам не нужно проверять, является ли
  категория коКлейсли действительно категорией. Нам
  не нужно опять проверять свойства стрелки тождества и 
  ассоциативности композиции, если мы уже проверили их для монады.
  Следовательно, перевёрнутое утверждение будет выполняться
  в перевёрнутой категории коКлейсли. В этом основное 
  преимущество определения через дуализацию. 
  
  Этим приёмом мы можем воспользоваться и в 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
  ~~~
  
  ## Начальный и конечный объекты
  
  ### Начальный объект
  
  Представим, что в нашей категории есть такой объект $0$, который
  соединён со всеми объектами, причём стрелка начинается из 
  этого объекта, и для каждого объекта может быть только одна стрелка,
  которая соединят данный объект с $0$. Графически эту ситуацию
  можно изобразить так:
  
  <#tikz_ init1>
  
  \Structs{начальный объект}
  Такой объект называют *начальным* (initial object).
  Его принято обозначать нулём, словно это начало отсчёта.
  Для любого объекта $A$ из категории $\CatA$ с начальным 
  объектом $0$ существует и только одна стрелка \mbox{$f : 0 \Ra B$}.
  Можно сказать, что начальный объект определяет функцию,
  которая переводит объекты $A$ в стрелки $f : 0 \Ra A$.
  Эту функцию обозначают специальными скобками $\cata{\cdot}$,
  она называется \Structs{катаморфизм} \Structs{свёртка}
  *катаморфизмом* (catamorphism).
  
  $$\cata{A} = f : 0 \Ra A$$
  
  У начального объекта есть несколько важных свойств.
  Они очень часто встречаются в разных вариациях, 
  в понятиях, которые определяются через понятие
  начального объекта:
  
  <#html
  --------------------    -----------     ------------------------------  ------------    -------------------------
  $\cata{0} = id_0$                                                       $\qquad$        $\text{тождество}$
  $f, g : 0 \Ra A$            $\RA$       $f = g$                                         $\text{уникальность}$
  $f: A \Ra B$                $\RA$       $\cata{A} \Co f = \cata{B}$                     $\text{слияние (fusion)}$
  --------------------    -----------     ------------------------------  ------------    -------------------------
  >
  
  <#tex
  \begin{equation*}\begin{array}{l@{\quad}l@{\quad}l@{\qquad\qquad}l} 
  \cata{0} = id_0 &   &                           & \text{тождество}  \\
  f, g : 0 \Ra A &\RA& f = g                      & \text{уникальность}     \\
  f: A \Ra B     &\RA& \cata{A} \Co f = \cata{B}  & \text{слияние (fusion)} \\
  \end{array}\end{equation*}
  >
  
  Эти свойства следуют из определения начального объекта. 
  Свойство тождества говорит о том, что стрелка, ведущая из
  начального объекта в начальный, является тождественной стрелкой.
  В самом деле, по определению начального объекта для каждого
  объекта может быть только одна стрелка, которая начинается в $0$
  и заканчивается в этом объекте. Стрелка $\cata{0}$ начинается
  в $0$ и заканчивается в $0$, но у нас уже есть одна такая стрелка -
  по определению категории для каждого объекта определена 
  тождественная стрелка - значит эта стрелка является единственной.
  
  Второе свойство следует из единственности стрелки, ведущей
  из начального объекта в данный. Третье свойство лучше
  изобразить графически:
  
  <#tikz_ init2>
  
  Поскольку стрелки $\cata{A}$ и $f$ можно соединить,
  то должна быть определена стрелка $\cata{A} \Co f : 0 \Ra B$,
  но поскольку в категории с начальным объектом из 
  начального объекта $0$ в объект $B$ может вести лишь 
  одна стрелка, то стрелка $\cata{A} \Co f$ должна совпадать
  с $\cata{B}$.
  
  ### Конечный объект
  
  Дуализируем понятие начального объекта. Пусть в категории
  $\CatA$ есть объект $1$, такой что для любого объекта
  $A$ существует и только одна стрелка, которая начинается
  из этого объекта и заканчивается в объекте $1$. Такой
  объект называют 
  \Structs{конечный объект}
  *конечным* (terminal object):
  
  <#tikz_ final1>
  
  Конечный объект определяет в категории функцию,
  которая ставит в соответствие объектам стрелки,
  которые начинаются из данного объекта и заканчиваются
  в конечном объекте. Такую функцию называют 
  \Structs{анаморфизм} \Structs{развёртка} *анаморфизмом*
  (anamorphism), и обозначают специальными скобками $\ana{\cdot}$, 
  которые похожи на перевёрнутые скобки для катаморфизма:
  
  $$\ana{A} = f : A \Ra  1$$
  
  Можно дуализировать и свойства:
  
  <#html
  --------------------    -----------     ------------------------------  ------------    -------------------------
  $\ana{1} = id_1$                                                        $\qquad$        тождество
  $f, g : A \Ra 1$            $\RA$       $f = g$                                         уникальность
  $f: A \Ra B$                $\RA$       $f \Co \ana{B}  = \ana{A}$                      слияние (fusion)
  --------------------    -----------     ------------------------------  ------------    -------------------------
  >
  
  <#tex
  \begin{equation*}\begin{array}{l@{\quad}l@{\quad}l@{\qquad\qquad}l} 
  \ana{1} = id_1 &   &                           & \text{тождество}  \\
  f, g : A \Ra 1 &\RA& f = g                      & \text{уникальность}     \\
  f: A \Ra B     &\RA&  f \Co \ana{B}  = \ana{A}  & \text{слияние (fusion)} \\
  \end{array}\end{equation*}
  >
  
  Приведём иллюстрацию для свойства слияния:
  
  <#tikz_ final2>
  
  
  ## Сумма и произведение
  
  
  Давным-давно, когда мы ещё говорили о типах, мы
  говорили, что типы конструируются с помощью двух базовых
  операций: суммы и произведения. Сумма говорит о
  том, что значение может быть либо одним значением, либо другим.
  А произведение обозначает сразу несколько значений. 
  В Haskell есть два типа, которые представляют собой сумму и 
  произведение в общем случае. Тип для суммы
  это `Either`:
  
  ~~~
  data Either a b = Left a | Right b
  ~~~
  
  Произведение в самом общем виде представлено кортежами:
  
  ~~~
  data (a, b) = (a, b)
  ~~~
  
  В теории категорий  сумма и произведение определяются 
  как начальный и конечный объекты в специальных категориях.
  Теория категорий изучает объекты по тому, как они
  взаимодействуют с остальными объектами. Взаимодействие
  обозначается с помощью стрелок. Специальные свойства
  стрелок определяют объект. 
  
  Например, представим, что мы не можем заглядывать внутрь
  суммы типов. Как бы мы могли взаимодействовать с объектом,
  который представляет собой сумму двух типов $A+B$? 
  Нам необходимо уметь создавать объект типа $A+B$ 
  из объектов $A$ и $B$ и извлекать их из суммы. Создание объектов происходит
  с помощью двух специальных конструкторов:
  
  $$inl : A \Ra A+B$$
  
  $$inr : B \Ra A+B$$
  
  Также нам хочется как-то извлекать значения.
  По смыслу внутри суммы $A+B$ хранится либо объект $A$,  
  либо объект $B$, и мы не можем заранее знать какой
  из них, поскольку внутреннее содержание $A+B$ от
  нас скрыто, но мы знаем, что это только $A$ 
  или $B$. Это говорит о том, что если у нас есть две 
  стрелки $A \Ra C$ и $B \Ra C$, то мы как-то можем построить
  $A+B \Ra C$. У нас есть операция:
  
  $$out(f,g) : A+B \Ra C \qquad f : A \Ra C,\ g : B \Ra C$$
  
  При этом для того, чтобы стрелки $inl$, $inr$ и $out$
  были согласованы необходимо, чтобы выполнялись свойства:
  
  $$inl \Co out(f,g)\ =\ f$$
  
  $$inr \Co out(f,g)\ =\ g$$
  
  для любых функций $f$ и $g$. Графически это свойство
  можно изобразить так:
  
  <#tikz_ sum1>
  
  
  Итак, суммой двух объектов $A$ и $B$ называется объект
  $A+B$ и две стрелки $inl : A \Ra A+B$ и $inr : B \Ra A+B$ 
  такие, что для любых двух стрелок $f : A \Ra C$ и $g : B \Ra C$
  определена одна и только одна стрелка $h : A+B \Ra C$ 
  такая, что выполнены свойства:
  
  $$inl \Co h = f$$
  $$inr \Co h = g$$
  
  В этом определении объект $A+B$ вместе со стрелками $inl$
  и $inr$, определяет функцию, которая по некоторому
  объекту $C$ и двум стрелкам $f$ и $g$ строит стрелку $h$,
  которая ведёт *из* объекта $A+B$ в объект $C$.
  Этот процесс определения стрелки по объекту напоминает
  определение начального элемента. Построим 
  специальную категорию, в которой объект $A+B$ будет
  начальным. Тогда функция $out$ будет катаморфизмом.
  
  Функция $out$ принимает две стрелки и возвращает 
  третью. Посмотрим на типы:
  
  $$f : A \Ra C  \qquad\qquad inl : A \Ra A+B$$
  
  $$g : B \Ra C  \qquad\qquad inr : B \Ra A+B$$
  
  Каждая из пар стрелок в столбцах указывают на один и тот же
  объект, а начинаются они из двух разных объектов $A$ и $B$. 
  Определим категорию, в которой объектами являются пары
  стрелок $(a_1, a_2)$, которые начинаются из объектов $A$ и $B$ 
  и заканчиваются в некотором общем объекте $D$. Эту категорию
  ещё называют клином. Стрелками в этой категории будут
  такие стрелки $f : (d_1, d_2) \Ra (e_1, e_2)$, что стрелки
  в следующей диаграмме коммутируют (не важно по какому пути
  идти из двух разных точек).
  
  <#tikz_ sum2>
  
  Композиция стрелок -- это обычная композиция в исходной категории, 
  в которой определены объекты $A$ и $B$, а тождественная
  стрелка для каждого объекта -- это тождественная стрелка для 
  того объекта, в котором сходятся обе стрелки. Можно проверить,
  что это действительно категория.
  
  Если в этой категории есть начальный объект, то мы
  будем называть его суммой объектов $A$ и $B$. Две
  стрелки, которые содержит этот объект мы будем называть
  $inl$ и $inr$, а общий объект, в котором эти стрелки сходятся,
  будем называть $A+B$. Теперь если мы выпишем определение
  для начального объекта, но вместо произвольных стрелок и
  объектов подставим наш конкретный случай, то мы получим
  как раз исходное определение суммы.
  
  Начальный объект $(inl : A \Ra A+B,\ inr : B \Ra A+B)$ ставит 
  в соответствие любому объекту $(f : A \Ra C,\ g : B \Ra C)$ 
  стрелку $h : A+B \Ra C$ такую, что выполняются свойства:
  
  <#tikz_ sum3>
  
  А как на счёт произведения? Оказывается, что произведение
  является дуальным понятием по отношению к сумме. Его иногда
  называют косуммой, или сумму называют копроизведением. 
  Дуализируем категорию, которую мы строили для суммы.
  
  У нас есть категория $\CatA$ и в ней выделено два объекта
  $A$ и $B$. Объектами новой категории будут пары стрелок $(a_1,a_2)$,
  которые *начинаются* в общем объекте $C$, а заканчиваются
  в объектах $A$ и $B$. Стрелками в этой категории будут
  стрелки исходной категории $h : (e_1,e_2) \Ra (d_1,d_2)$ такие, что следующая
  диаграмма коммутирует:
  
  <#tikz_ prod1>
  
  
  Композиция и тождественные стрелки позаимствованы
  из исходной категории $\CatA$. Если в этой категории
  существует *конечный* объект, то мы будем
  называть его произведением объектов $A$ и $B$.
  Две стрелки этого объекта обозначаются как $(exl,exr)$,
  а общий объект из которого они начинаются мы назовём
  $A\times B$. Теперь распишем определение конечного объекта
  для нашей категории пар стрелок с общим началом.
  
  Конечный объект $(exl : A \times B \Ra A, \ exr : A \times B \Ra B)$ 
  ставит в соответствие любому объекту категории
  $(f : C \Ra A,\ g : C \Ra B)$ стрелку $h : C \Ra A \times B$.
  При этом выполняются свойства:
  
  <#tikz_ prod2>
  
  Итак, мы определили сумму, а затем на автомате, перевернув
  все утверждения, получили определение произведения. 
  Но что это такое? Соответствует ли оно интуитивному
  понятию произведения? 
  
  Так же как и в случае суммы в теории категорий мы 
  определяем понятие через то, как мы можем с ним 
  взаимодействовать. Посмотрим, что нам досталось от 
  абстрактного определения. У нас есть обозначение произведения
  типов $A \times B$. Две стрелки $exl$ и $exr$. Также у нас есть
  способ получить по двум функциям $f : C \Ra A$ и $g : C \Ra B$
  стрелку $h : C \Ra A \times B$. Для начала посмотрим на типы стрелок 
  конечного объекта:
  
  $$exl : A \times B \Ra A$$
  
  $$exr : A \times B \Ra B$$
  
  По типам видно, что эти стрелки разбивают пару на составляющие.
  По смыслу произведения мы точно знаем, что у нас есть в $A\times B$ 
  и объект $A$ и объект $B$. Эти стрелки позволяют нам извлекать 
  компоненты пары. Теперь посмотрим на анаморфизм:
  
  $$\ana{f,g} : C \Ra A \times B \qquad f : C \Ra A,\ g : C \Ra B$$
  
  Эта функция позволяет строить пару по двум функциям и начальному
  значению. Но, поскольку здесь мы ничего не вычисляем, а лишь связываем
  объекты, мы можем по паре стрелок, которые начинаются из общего
  источника связать источник с парой конечных точек $A \times B$.
  
  При этом выполняются свойства:
  
  $$\ana{f,g} \Co exl = f$$
  
  $$\ana{f,g} \Co exr = g$$
  
  Эти свойства говорят о том, что функции построения пары
  и извлечения элементов из пары согласованы.
  Если мы положим значение в первый элемент пары и тут же
  извлечём его, то это тоже само если бы мы не
  использовали пару совсем. То же самое и со вторым элементом.
  
  ## Экспонента
  
  Если представить, что стрелки это функции, то может
  показаться, что все наши функции являются функциями
  одного аргумента. Ведь у стрелки есть только один
  источник. Как быть если мы хотим определить функцию
  нескольких аргументов, что она связывает? Если в 
  нашей категории определено произведение объектов,
  то мы можем представить функцию двух аргументов,
  как стрелку, которая начинается из произведения:
  
  $$(+) : Num \times Num \Ra Num$$
  
  Но в лямбда-исчислении нам были доступны более гибкие
  функции, функции могли принимать на вход функции и
  возвращать функции. Как с этим обстоят дела в теории категорий?
  Если перевести определение функций высшего порядка на
  язык теории категорий, то мы получим стрелки, которые
  могут связывать другие стрелки. Категория с функциями
  высшего порядка может содержать свои стрелки в качестве 
  объектов. Стрелки как объекты обозначаются с помощью степени,
  так запись $B^A$ означает стрелку $A \Ra B$. При этом
  нам необходимо уметь интерпретировать стрелку,
  мы хотим уметь подставлять значения. Если у нас
  есть объект $B^A$, то должна быть стрелка
  
  $$eval : B^A \times A \Ra B$$
  
  На языке функций можно сказать, что стрелка $eval$ принимает
  функцию высшего порядка $A \Ra B$ и значение типа $A$, а
  возвращает значение типа $B$. Объект $B^A$ называют 
  экспонентой. Теперь дадим формальное определение.
  
  Пусть в категории $\CatA$ определено произведение.
  \Structs{экспонента}
  *Экспонента* -- это объект $B^A$ вместе со стрелкой
  $eval : B^A \times A \Ra B$ такой, что для любой стрелки
  $f : C \times A \Ra B$ определена стрелка $curry(f):C \Ra B^A$ 
  при этом следующая диаграмма коммутирует:
  
  <#tikz_ exponent1>
  
  
  Давайте разберёмся, что это всё означает. По смыслу 
  стрелка $curry(f)$ это каррированная функция двух аргументов.
  Вспомните о функции `curry` из Haskell. Диаграмма говорит
  о том, что если мы каррированием функции двух аргументов 
  получим функцию высшего порядка $C \Ra B^A$, а затем с 
  помощью функции $eval$ получим значение, то это всё равно, 
  что подставить два значения в исходную функцию. Запись 
  $(curry(f), id)$ означает параллельное применение двух 
  стрелок внутри пары:
  
  $$(f, g) : A \times A' \Ra B \times B' 
              , \qquad f : A\Ra B , \ g : A' \Ra B'$$
  
  Так применив стрелки $curry(f) : C \Ra B^A$  и $id : A \Ra A$ к паре
  $C \times A$, мы получим пару $B^A \times A$. Применение
  здесь условное мы подразумеваем применение в функциональной аналогии,
  в теории категорий происходит связывание пар объектов
  с помощью стрелки $(f, g)$.
  
  Интересно, что и экспоненту можно получить как конечный
  объект в специальной категории. Пусть есть категория $\CatA$
  и в ней определено произведение объектов $A$ и $B$. Построим
  категорию, в которой объектами являются стрелки вида:
  
  $$C \times A \Ra B$$
  
  \noindent где $C$ -- это произвольный объект исходной категории.
  Стрелкой между объектами $c : C \times A \Ra B$ и $d : D \times A \Ra B$
  в этой категории будет стрелка $f : C \Ra D$ из исходной категории,
  такая, что следующая диаграмма коммутирует: 
  
  <#tikz_ exponent2>
  
  Если в этой категории существует конечный объект,
  то он является экспонентой. А функция $curry$
  является анаморфизмом для экспоненты.
  
  ## Краткое содержание
  
  Теория категорий изучает понятия
  через то, как эти понятия взаимодействуют друг с другом.
  Мы забываем о том, как эти понятия реализованы, а смотрим
  лишь на свойства связей. 
  
  Мы узнали, что такое категория. Категория это структура с
  объектами и стрелками. Стрелки связывают объекты. 
  Причём связи могут соединятся. Также считается, что
  объект всегда связан сам с собой. Мы узнали, что 
  есть такие категории, в которых сами объекты являются
  категориями, а стрелки в таких категориях мы назвали функторами.
  Также мы узнали, что сами функторы могут стать объектами
  в некоторой категории, тогда стрелки в этой категории мы 
  назвали естественными преобразованиями. 
  
  Мы узнали, что такое начальный и конечный объект и как
  с помощью этих понятий можно определить сумму и произведение
  типов. Также мы узнали как в теории категорий описываются
  функции высших порядков.
  
  ## Упражнения
  
  
  
  *   Проверьте аксиомы категории (ассоциативность и тождество)
      для категории функторов и категории естественных преобразований.
  
  *   Изоморфизмом называют такие стрелки $f:A \Ra B$ и $g : B \Ra A$, для 
      которых выполнено свойство:
  
      $$f \Co g = id_A$$
      $$g \Co f = id_B$$
  
      Объекты $A$ и $B$ называют изоморфными, если они связаны
      изоморфизмом, это обозначают так: $A \cong B$. 
      Докажите, что все начальные и конечные элементы 
      изоморфны. 
  
  *   Поскольку сумма и произведение типов являются 
      начальным и конечным объектами в специальных категориях
      для них также выполняются свойства тождества, уникальности и слияния.
      Выпишите эти свойства для суммы и произведения. 
  
  *   Подумайте как можно определить экземпляр класса `Comonad`
      для потоков:
  
      ~~~
      data Stream a = a :& Stream a
      ~~~
  
      Можно ли придумать экземпляр для класса `Monad`?
  
  *   Дуальную категорию для категории $\CatA$ обозначают $\CatA^{op}$.
      Если $F$ является функтором в категории $\CatA^{op}$, то
      в исходной категории его называют *контравариантным*
      функтором. Выпишите определение функтора в $\CatA^{op}$,
      а затем с помощью дуализации получите свойства контравариантного
      функтора в исходной категории $\CatA$.
  
  
  