Теория категорий

Теория категорий — раздел математики, изучающий свойства отношений между математическими объектами, не зависящие от внутренней структуры объектов.

Категория C — это:

• класс объектов \(Ob_{C}\)
• для каждой пары объектов A, B задано множество морфизмов (или стрелок) \(Hom_{C}(A,B)\), причём каждому морфизму соответствуют единственные A и B
• для пары морфизмов \(f \in Hom(A,B)\) и \(g \in Hom(B,C)\) определена композиция \(g \circ f \in Hom(A,C)\)
• для каждого объекта A задан тождественный морфизм \(id_{A} \in Hom(A,A)\) (стрелка от объекта к самому себе)

причём выполняются две аксиомы:

• операция композиции ассоциативна: если есть три морфизма, f, g и h, которые могут быть скомпонованы (то есть, их типы согласованы друг с другом), то порядок компоновки не имеет значения: \(h \circ (g \circ f) = (h \circ g) \circ f\)
• тождественный морфизм действует тривиально: \(f \circ id_{A} = id_{B} \circ f = f\) для \(f \in Hom(A,B)\)

В Scala это определение можно выразить так:

def compose[A, B, C](f: A => B, g: B => C): A => C = f andThen g
def id[A]: A => A = a => a

А соответствующие законы вот так (если задана операция assert, способная проверять функции на равенство, например, на какой-то выборке):

trait Laws[A, B, C, D]:
  def associativityLaw(f: A => B, g: B => C, h: C => D): Unit =
    assert(compose(compose(f, g), h), compose(f, compose(g, h)))

  def identityLaw(f: A => B): Unit =
    assert(compose(f, id), f)
    assert(compose(id, f), f)

Краткий итог

Категория состоит из объектов и стрелок (морфизмов). Стрелки могут быть скомпонованы, их композиция ассоциативна. Каждый объект имеет единичную стрелку, которая служит в качестве единицы композиции.

Инициальный и терминальный объекты

Инициальный объект — это объект, от которого к любому объекту категории исходит ровно один морфизм.

Двойственным образом определяется терминальный или универсально притягивающий объект — это такой объект, в который из любого объекта категории существует единственный морфизм.

Рассмотрим пример:

Если представить, что класс объектов \(Ob_{C}\) - это Scala тип Byte, а морфизм - это отношение "меньше" (<), то в такой категории инициальным объектом будет -128 (инициальный объект "меньше" всех остальных объектов - исходит стрелка), а терминальным будет 127 (из каждого объекта существует стрелка "меньше" в этот объект).

Назовем упорядоченной категорией категорию, где объект a предшествует объекту b, если существует стрелка (морфизм) от a к b. Инициальный объект в частично упорядоченном множестве — это его наименьший элемент. Некоторые частично упорядоченные множества, такие как все целые числа (и положительные, и отрицательные), не имеют инициального объекта.

Рассмотрим ещё один пример:

Если представить, что класс объектов \(Ob_{T}\) - это система типов Scala, а морфизм - это отношение "наследует" (A extends B или \(A \mapsto B\)), то в такой категории инициальным объектом будет Nothing (от него к любому объекту категории исходит ровно один морфизм или Nothing наследует от любого типа в Scala), а терминальным - Any (из каждого объекта существует стрелка "наследует" в этот объект).

Глобальный элемент

В теории категорий говорят, что x является глобальным элементом для a, если он является стрелкой \(1 \overset{x}{\rightarrow} a\), где 1 - терминальный объект.

В теории типов, x: A означает, что x является типом A.

Система типов Scala различает x: A и x: () => A. Однако, в категорной семантике они обозначают одно и то же. В дальнейшем глобальный элемент будем обозначать как x: A.

Поскольку стрелок от любого другого объекта к инициальному объекту нет, то нет и стрелок от терминального объекта к нему. Поэтому инициальный объект не имеет элементов. И в Scala нет типа для инициального объекта. Терминальный объект имеет только один элемент, так как от него к самому себе идет единственная стрелка, 1 → 1; поэтому иногда его называют синглетоном. В Scala терминальный объект - это Unit с единственным элементом - ().

Двойственность

Для категории C можно определить двойственную категорию \({\mathcal {C}}^{{op}}\), в которой:

• объекты совпадают с объектами исходной категории;
• морфизмы получаются «обращением стрелок»: \({\mathrm {Hom}}_{{{\mathcal {C}}^{{op}}}}(B,A) \) \(\simeq {\mathrm {Hom}}_{{{\mathcal {C}}}}(A,B)\)

Двойственная категория автоматически удовлетворяет определению категории, если мы одновременно с обращением стрелок переопределим композицию. Если композицией исходных морфизмов \(f \in Hom(A,B)\) и \(g \in Hom(B,C)\) был морфизм \(h \in Hom(A,C)\) с \(h = g \circ f\), то композицией обращенных морфизмов \(f^{op} \in Hom(B,A)\) и \(g^{op} \in Hom(C,B)\) будет морфизм \(h^{op} \in Hom(C,A)\) с \(h^{op} = f^{op} \circ g^{op}\). Отметим, что обращение тождественной стрелки совпадает с ней самой.

В Scala это определение можно выразить так:

def cocompose[A, B, C](f: B => A, g: C => B): C => A = g andThen f

Принцип двойственности гласит, что для любого утверждения теории категорий можно сформулировать двойственное утверждение с помощью обращения стрелок, при этом истинность утверждения не изменится. Часто двойственное понятие обозначается тем же термином с приставкой ко-.

Терминальный объект — это инициальный объект в двойственной категории.

Композиция, пост-композиция, пред-композиция

Композиция

Имея стрелку f от a к b и стрелку g от b к c, их композиция представляет собой стрелку, идущую непосредственно от a к c. Другими словами, если имеются две стрелки, цель одной из которых совпадает с источником другой, то всегда можно скомпоновать их, чтобы получить третью стрелку. Обозначается как: \(h = g \circ f\)

Ассоциативность

Предположим, что удалось разложить g на \(j \circ k\). Тогда \(h = (j \circ k) \circ f\) Желательно, чтобы это разложение было таким же, как и \(h = j \circ (k \circ f)\). При этом должна существовать возможность заявить, что h была декомпозирована на три более простые функции \(h = j \circ k \circ f\) и не нужно отслеживать, какая декомпозиция была первой. Это свойство называется ассоциативностью композиции.

Пост-композиция

Композиция является источником двух отображений стрелок, называемых пред-композицией и пост-композицией. Когда стрелка f является пост-компонуемой со стрелкой h, получается стрелка \(f \circ h\). Конечно, f можно пост-компоновать только со стрелками, целью которых является источник для f. Пост-композиция посредством f записывается как \(f \circ -\), оставляя пустоту для h. Таким образом, стрелка f : a → b индуцирует отображение стрелок \(f \circ -\), которое отображает стрелки, идущие к a, в стрелки, идущие к b.

Пост-композиция позволяет смещать фокус с одного объекта на другой.

Пред-композиция

Двойственным образом, можно пред-композировать f, или применить \(- \circ f\) к стрелкам, исходящим из b, сопоставляя их со стрелками, исходящими из a. Пред-композиция позволяет смещать перспективу от одного наблюдателя к другому.

В программировании, исходящая стрелка интерпретируется как извлечение данных из источника. Входящая стрелка интерпретируется как создание цели. Исходящие стрелки определяют интерфейс, входящие стрелки определяют конструкторы.

На Scala пред- и пост-композиции можно изобразить так:

trait Arrow[A, B]:
  extension(f: A => B)
    def postCompose[X](g: X => A): X => B = x => f(g(x))

    def preCompose[X](g: B => X): A => X = a => g(f(a))

Применение функции и тождественность

Применение функции

Рассмотрим стрелку от терминального объекта 1 к (типу) a. Это какой-то элемент x типа a. Можно записать это как \(1 \overset{x}{\rightarrow} a\). Рассмотрим стрелку от a к b: \(a \overset{f}{\rightarrow} b\). Эти две стрелки являются компонуемыми (они соприкасаются на объекте a), и их композиция — это стрелка y от 1 к b. Другими словами, y является элементом из b. Можно записать это так: \(y = f \circ x\). Мы используем f для отображения элемента из a к элементу из b. Такое действие называется применение функции f к x:

trait Arrow[A, B]:
  extension(f: A => B)
    def apply(a: A): B = f(a)

Тождественность

Каждый объект имеет специальную стрелку, называемую тождественной (или тождественностью), которая оставляет объект неизменным. Это означает, что когда вы компонуете тождественную стрелку с любой другой стрелкой, входящей или исходящей, то получаете ту же стрелку. Тождественная стрелка ничего не делает с другой стрелкой.

Тождественная стрелка на объекте a обозначается как \(id_{a}\). Так что, если имеется стрелка \(f : a \to b\), то можно скомпоновать ее с тождественностями с обеих сторон: \(id_{b} \circ f = f = f \circ id_{a}\)

trait Arrow[A, B]:
  def identity(a: A): A = a

Возьмем элемент \(x : 1 \to a\) и скомпонуем его с \(id_{a}\). Результат \(id_{a} \circ x = x\) означает, что тождественность оставляет элементы неизменными.

Изоморфизм, эндоморфизм, автоморфизм

Изоморфизм

Морфизм \(f \in Hom(A,B)\) называется изоморфизмом, если существует такой морфизм \(g \in Hom(B,A)\), что \({\displaystyle g \circ f = \mathrm {id}_{A}}\) и \({\displaystyle f \circ g = \mathrm {id}_{B}}\). Это отношение записывается как \(g = f^{−1}\) (произносится, как обратная к f). Стрелка \(f^{−1}\), другими словами, отменяет результат действия стрелки f. Два объекта, между которыми существует изоморфизм, называются изоморфными (записывется \(a \cong b\)). В частности, тождественный морфизм является изоморфизмом, поэтому любой объект изоморфен сам себе.

В программировании, два изоморфных типа имеют одинаковое внешнее поведение. Один тип может быть реализован через другой, и наоборот. Одно можно заменить другим без изменения поведения системы (за исключением, возможно, производительности). Например, многие коллекции в Scala изоморфны друг другу, скажем, List и Vector.

Когда мы говорим, что инициальный (или терминальный) объект единственен с точностью до изоморфизма, то имеется в виду, что любые два инициальные (или терминальные) объекты изоморфны. Это легко продемонстрировать. Предположим, что \(i_{1}\) и \(i_{2}\) — инициальные объекты в одной и той же категории. Поскольку \(i_{1}\) инициальный, то существует единственный морфизм f от \(i_{1}\) к \(i_{2}\). Аналогично, поскольку \(i_{2}\) инициальный, то существует единственный морфизм g от \(i_{2}\) к \(i_{1}\). Что можно сказать о композиции этих морфизмов? Композиция \(g \circ f\) должна быть морфизмом от \(i_{1}\) к \(i_{1}\). Но \(i_{1}\) является инициальным объектом, так что существует ровно один морфизм от \(i_{1}\) к \(i_{1}\) и, поскольку начало и конец стрелки совпадают, эта вакансия уже занята тождественным морфизмом. Следовательно, они должны совпадать: морфизм \(g \circ f\) является тождественным. Аналогично, морфизм \(f \circ g\) также совпадает с тождественным, поскольку может быть всего один морфизм от \(i_{2}\) к \(i_{2}\). Таким образом, f и g взаимнообратны, а два инициальных объекта изоморфны.

Естественность

Изменение точки зрения сохраняет взаимную поддержку, установленную изоморфизмом. Если две стрелки были напарниками с точки зрения x, они по-прежнему остаются напарниками и с точки зрения y. Т.е. не имеет значения, делаете ли вы сначала пред-композицию с помощью g (переключение точки зрения), а затем пост-композицию с помощью f (переключение фокуса), или сначала пост-композицию с помощью f, а затем пред-композицию с g. Символически это записывается так: \((− \circ g) \circ (f \circ −) = (f \circ −) \circ (− \circ g)\) - это называется условием естественности. Смысл этого равенства раскрывается, если применить его к морфизму \(h : x \to a\). Обе стороны оцениваются как \(f \circ h \circ g\): \(y \overset{g}{\rightarrow} x \overset{h}{\rightarrow} a \overset{f}{\rightarrow} b\)

С точки зрения изоморфной пары условие естественности выглядит так: \((− \circ f^{−1}) \circ (g \circ −) = (g \circ −) \circ (− \circ f^{−1})\). Что сводится к \(b \overset{f^{-1}}{\rightarrow} a \overset{h}{\rightarrow} x \overset{g}{\rightarrow} y\).

Эндоморфизм

Морфизмы, в которых начало и конец совпадают, называют эндоморфизмами. Множество эндоморфизмов \({\displaystyle \mathrm {End}(A) = \mathrm {Hom}(A,A)}\) является моноидом относительно операции композиции с единичным элементом \({\displaystyle \mathrm {id}_{A}}\).

Автоморфизм

Эндоморфизмы, которые одновременно являются изоморфизмами, называются автоморфизмами. Автоморфизмы любого объекта образуют группу автоморфизмов \({\displaystyle \mathrm {Aut} (A)}\) по композиции.

Мономорфизм, эпиморфизм, биморфизм

Мономорфизм — это морфизм \(f \in {\mathrm {Hom}}(A,B)\) такой, что для любых \(g_{1}, g_{2} \in {\mathrm {Hom}}(X,A)\) из \(f \circ g_{1} = f \circ g_{2}\) следует, что \(g_{1} = g_{2}\). Композиция мономорфизмов есть мономорфизм.

Эпиморфизм — это такой морфизм \(f \in {\mathrm {Hom}}(A,B)\), что для любых \(g_{1}, g_{2} \in {\mathrm {Hom}}(B,X)\) из \(g_{1} \circ f = g_{2} \circ f\) следует, что \(g_{1} = g_{2}\). Композиция эпиморфизмов есть эпиморфизм.

Биморфизм — это морфизм, являющийся одновременно мономорфизмом и эпиморфизмом. Любой изоморфизм есть биморфизм, но не любой биморфизм есть изоморфизм.

Произведение и сумма объектов

Произведение

Произведение (пары) объектов A и B — это объект \(A \times B\) с морфизмами \(p_{1}:A \times B \to A\) и \(p_{2}:A \times B \to B\) такими, что для любого объекта C с морфизмами \(f_{1}: C \to A\) и \(f_{2}: C \to B\) существует единственный морфизм \(g: C \to A \times B\) такой, что диаграмма, изображённая ниже, коммутативна.

Морфизмы \(p_{1}: A \times B \to A\) и \(p_{2}: A \times B \to B\) называются проекциями.

Коммутативность, объединители, ассоциативность и функториальность

Произведение удовлетворяет правилу коммутативности с точностью до изоморфизма: \(a \times b \cong b \times a\).

Обратимая стрелка, свидетельствующая об изоморфизме между \(1 \times a\) и a, называется левым объединителем (или унитором, unitor): \(\lambda : 1 \times a \to a\). Аналогично определяется правый объединитель: \(\rho : a \times 1 \to a\). Ассоциатором называется изоморфизм: \(\alpha : (a \times b) \times c \to a \times (b \times c)\).

Предположим, что имеются стрелки, которые отображают a и b к некоторым \(\acute{a}\) и \(\acute{b}\): \(f: a \to \acute{a}, g: b \to \acute{b}\). Композицию этих стрелок с проекциями \(p_{1}\) и \(p_{2}\), соответственно, можно использовать для определения отображения между произведениями: \(a \times b \overset{f \times g}{\rightarrow} \acute{a} \times \acute{b}\). Это свойство произведения называется функториальностью. Оно позволяет трансформировать два объекта внутри произведения, чтобы получить новое произведение.

Произведение удовлетворяет следующим свойствам:

• \(1 \times a \cong a\)
• \(a \times b \cong b \times a\)
• \((a \times b) \times c \cong a \times (b \times c)\)

и оно функториально. Категория с таким типом операции называется симметричной моноидальной.

Пример

В Scala примером произведений могут служить кортежи:

val product: (String, Int) = ("product", 42)
val (str, num) = product

Коммутативность:

def swap[A, B](product: (A, B)): (B, A) = (product._2, product._1)

Ассоциативность:

def assoc[A, B, C](product: ((A, B), C)): (A, (B, C)) = (product._1._1, (product._1._2, product._2))

Функториальность:

def functoriality[A, B, C, D](ab: (A, B), f: A => C, g: B => D): (C, D) =
  (f(ab._1), g(ab._2))

Копроизведение (Тип-сумма)

Двойственно определяется сумма или копроизведение A + B объектов A и B. Соответствующие морфизмы \(\imath_{A}: A \to A + B\) и \(\imath_{B}: B \to A + B\) называются вложениями. Несмотря на своё название, в общем случае они могут и не быть мономорфизмами.

Рассмотрим на примере тип-суммы Bool:

enum Bool:
  case True, False

val x: Bool = Bool.True

Функции True и False, которые использованы в определении Bool, называются конструкторами данных. Их можно использовать для создания конкретных термов, как в примере выше.

Рассмотрим отображение из типа-суммы. Каждая функция Bool -> A производит пару элементов типа A.

def apply[A](f: Bool => A): (A, A) =
  (f(Bool.True), f(Bool.False))

Любая функция от Bool к A не только производит, но и эквивалентна паре элементов из A. Другими словами, пара элементов однозначно определяет функцию от Bool:

def f[A](b: Bool, x: A, y: A): A =
  b match
    case Bool.True  => x
    case Bool.False => y

Тип-сумму можно расширить не большее количество объектов, используя перечисления.

Коммутативность, ассоциативность и функториальность

Тип-сумма удовлетворяет правилу коммутативности с точностью до изоморфизма: \(a + b \cong b + a\).

А также ассоциативности: \(a + (b + c) \cong (a + b) + c\).

Предположим, что имеются стрелки, которые отображают a и b к некоторым \(\acute{a}\) и \(\acute{b}\): \(f: a \to \acute{a}, g: b \to \acute{b}\). Композицию этих стрелок с конструкторами Left и Right, соответственно, можно использовать для определения отображения между суммами. Пара стрелок, \((Left \circ f, Right \circ g)\) однозначно определяет стрелку \(h: a + b → \acute{a} + \acute{b}\). Это свойство суммы называется функториальностью. Можно представлять себе, что это позволяет преобразовывать два объекта внутри суммы и получить новую сумму. Мы также говорим, что функториальность позволяет нам поднять пару стрелок, чтобы оперировать суммами.

Очевидно, что из-за ассоциативности функториальность распространяется на тип-суммы большей размерности.

Тип-сумма удовлетворяет следующим свойствам:

• \(a + 0 \cong a\)
• \(a + b \cong b + a\)
• \((a + b) + c \cong a + (b + c)\)

и она функториальна. Категория с таким типом операции называется симметричной моноидальной.

Пример

В Scala примером копроизведений (тип сумм) могут служить такие структуры, как: Option, Either и List.

enum Option[+A]:
  case Some(get: A)
  case None

enum Either[+E, +A]:
  case Left(value: E)
  case Right(value: A)
  
enum List[+A]:
  case Nil
  case Cons(head: A, tail: List[A])

Данные типы изоморфны друг другу, например:

enum List[+A]:
  self =>

  case Nil
  case Cons(head: A, tail: List[A])

  val toOption: Option[List[A]] =
    self match
      case Nil => Option.None
      case _   => Option.Some(self)

  val toEither: Either[Unit, List[A]] =
    self match
      case Nil => Either.Left(())
      case _   => Either.Right(self)

Законы коммутативности и ассоциативности на примере Either:

// Коммутативность
def f[A, B](either: Either[A, B]): Either[B, A] =
  either match
    case Left(a)  => Right(a)
    case Right(b) => Left(b)

def fReverse = f

// Ассоциативность
def g[A, B, C](either: Either[Either[A, B], C]): Either[A, Either[B, C]] =
  either match
    case Left(Left(a))  => Left(a)
    case Left(Right(b)) => Right(Left(b))
    case Right(c)       => Right(Right(c))

def gReverse[A, B, C](
    either: Either[A, Either[B, C]]
): Either[Either[A, B], C] =
  either match
    case Left(a)         => Left(Left(a))
    case Right(Left(b))  => Left(Right(b))
    case Right(Right(c)) => Right(c)

Функториальность Either:

def map[A, B, C, D](either: Either[A, B], f: A => C, g: B => D): Either[C, D] =
  either match
    case Left(a)  => Left(f(a))
    case Right(b) => Right(g(b))

Примеры в различных категориях

Если произведение и копроизведение существуют, то они определяются однозначно с точностью до изоморфизма.

• Пример: В категории Set произведение A и B — это прямое произведение в смысле теории множеств \(A \times B\), а сумма — дизъюнктное объединение \(A \sqcup B\).
• Пример: В категории колец Ring сумма — это тензорное произведение \(A \otimes B\), а произведение — прямая сумма колец \(A \oplus B\).
• Пример: В категории VectK (конечные) произведение и сумма изоморфны — это прямая сумма векторных пространств \(A \oplus B\).

Алгебра типов

Для произведения и ко-произведения выполняется дистибутивный закон a * (b + c) = a * b + a * c с точностью до изоморфизма:

val leftside: (A, Either[B, C]) = ???
val rightside: Either[(A, B), (A, C)] =
  leftside match
    case (a, Left(b))  => Left((a, b))
    case (a, Right(c)) => Right((a, c))

rightside match
  case Left((a, b))  => (a, Left(b))
  case Right((a, c)) => (a, Right(c))

Ссылки:

• Category Theory for Programmers - Bartosz Milewski:
  • Теория категорий для программистов
  • Category Theory for Programmers, Category: The Essence of Composition
  • Category Theory for Programmers, Products and Coproducts
  • Category Theory for Programmers, Simple Algebraic Data Types
• The Dao of Functional Programming - Bartosz Milewski:
  • Дао функционального программирования
  • The Dao of Functional Programming