Категории типов. Часть 5½. Сопряжения из монады / Хабр

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

Изначально планировал начать с этой темы шестую часть обзора, посвящённую расширениям Кана, но формально она имеет большее отношение к теме предыдущей публикации, сопряжённым функторам. В итоге материала набралось достаточно на самостоятельную публикацию с промежуточным номером)).

Оглавление обзора

Hom-типы
Функторы
Естественные преобразования
Монады
Пределы и сопряжения функторов
5½. Сопряжения из монады (данная публикация)

Содержание

Забывающе-свободные сопряжения
Категория сопряжений монады
Сопряжение Клейсли
Сопряжение Эйленберга-Мура
Переключение сопряжений
Option с фокусом на фильтрацию
Тезисы

Забывающе-свободные сопряжения

Функциональные отношения могут быть инъективными — разным объектам из области определения инъективной функции ставятся в соответствие разные объекты в её образе. В этом случае информация не теряется, и по любому объекту из образа всегда можно восстановить исходный объект. Однако очень часто функция оказывается не инъективной и её образ оказывается меньше области определения, когда некоторые разные исходные объекты приводят в один и тот же. Такая функция забывает часть исходной информации, она оказывается необратимой.

Функторы — это по сути те же функции, преобразующие морфизмы одной категории в морфизмы другой. И, так же как и функции, в общем случае, функторы имеют «забывающую природу».

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

Рассмотрим сопряжение $L \dashv R$ функторов $R: \mathcal{C} \rightarrow \mathcal{D}$ и $L: \mathcal{D} \rightarrow \mathcal{C}$ . Такие обозначения выбраны не случайно — функтор (left) сопряжён слева и на диаграмме действует «влево», тогда как (right) сопряжён справа и действует «вправо». Каждый из них пытается «восстановить» информацию, теряемую другим функтором, но делают они это по-разному.

Коединица сопряжения помогает свободному функтору «восстановить» данные, потерянные забывающим функтором.

Правый функтор забывает различие объектов $a, b: \mathcal{C}$ , сводя их в один $Ra=Rb: \mathcal{D}$ , тогда как левый функтор восстанавливает свободный (Free) объект $LRa=LRb: \mathcal{C}$ , максимально соответствующий обоим исходным объектам.

Роли сопряжённых функторов для комонады

Если бы нас больше интересовала комонада $L \circ R$ в категории $\mathcal{C}$ , то роли сопряжённых функторов симметрично поменялись бы. Правосопряжённый функтор тогда отображал бы объекты из $\mathcal{C}$ в косвободные объекты категории $\mathcal{D}$ , тогда как левосопряжённый «козабывал» контекст категории $\mathcal{C}$ ради упрощения в $\mathcal{D}$ .

Часто выделяют особый класс забывающих функторов, объединённых одной идеей. Пусть левая категория $\mathcal{C}$ состоит из тех же объектов, что и $\mathcal{D}$ , но морфизмов в ней меньше — hom-объекты в $\mathcal{C}$ ограничены дополнительными условиями. Типичный пример: справа у нас категория множеств $\mathrm{Set}$ со всеми возможными функциями, а слева — категория моноидов над множествами $\mathrm{Mon}(\mathrm{Set})$ . Объекты в ней являются такой конструкцией $(a \in \mathrm{Set},\,mon:\; a \otimes a + 1 \rightarrow a,\, \text{законы моноида})$ . Допустимы лишь те морфизмы, что переводят одни моноиды в другие, то есть коммутируют с операцией , сохраняя законы ассоциативности композиции и нейтрального элемента. Нас тут интересует функтор $U:\; \mathrm{Mon(Set)} \rightarrow \mathrm{Set}$ , сопоставляющий каждому моноиду его множество.

Морфизмы моноидов теряются среди прочих после отображения забывающим функтором.

В категории $\mathrm{Set}$ между любыми объектами есть морфизмы, которых нет в $\mathrm{Mon(Set)}$ . Функтор забывает ограничения $\mathrm{Mon(Set)}$ — «особенные» морфизмы, сохраняющие моноиды, буквально теряются в $\mathrm{Set}$ среди прочих морфизмов. Функторы, отображающие hom-множества инъективно, но не сюръективно, называют «забывающими».

Underlying functor

Буква , повсеместно используемая для обозначения забывающих функторов — это сокращение от английского слова Underlying (лежащий в основе). Забывающий функтор обычно «стирает» дополнительную структуру (например, операцию умножения в группе или топологию в пространстве), оставляя только underlying set — «лежащее в основе множество».

За восстановление потерянных данных отвечает функтор , сопряжённый к слева: $F \dashv U$ .

Для любого множества функтор подбирает такой моноид , чтобы каждому морфизму моноидов $Fa \rightarrow m$ взаимно однозначно соответствовал морфизм множеств $a \rightarrow Um$ . Очевидно, что общем случае $UFa \ncong a$ , то есть функтор приводит к моноиду, у которого основное множество будет отличаться от исходного. Объект представляет собой наиболее общий моноид для множества , такой, что для него существует столько же способов получить произвольный моноид , сколько и обычных функций от к множеству . Бинарная операция для должна быть максимально обобщённой, свободной от привязки к другим бинарным операциям и позволяющей получить любую из них. Такой объект называется свободным моноидом для множества . Функторы, сопряженные к забывающим слева, называют свободными функторами.

Понятия «забывающего» и «свободного» функторов не являются строго математическими. Это скорее роли функторов в конкретном сопряжении:

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

Такие роли функторов важны для лучшего понимания анатомии монады, которая может быть построена из целой совокупности различных сопряжений. Анализу этих сопряжений и посвящена данная часть обзора.

Категория сопряжений монады

Монада эндофунктора $T:\mathcal{C}\to\mathcal{C}$ может быть построена как композиция $T = F \circ U$ сопряжённых функторов $F \dashv U$ , проходящих через промежуточную категорию: $\mathcal{C} \overset{F}{\to} \mathcal{D} \overset{U}{\to} \mathcal{C}$ . Категория $\mathcal{D}$ несёт в себе отпечаток исходной, но она также «обогащена ограничениями», отражающими действие монады . Функтор «свободно» сопоставляет объекты из $\mathcal{C}$ в «наиболее общие» в $\mathcal{D}$ , тогда как забывающий функтор , как правило, отбрасывает всё лишнее, снова возвращая в $\mathcal{С}$ . Но даже при фиксированной промежуточной категории могут существовать различные пары порождающие ту же самую монаду.

Ввиду свободно-забывчивой природы сопряжённых функторов, промежуточная категория содержит всю информацию не только об исходной, но и об «эффекте» монады . Причём эта информация содержится не столько в объектах категории, но, прежде всего, в её морфизмах. Свободный функтор даже может «слепить» все объекты исходной категории в единственный $d:\mathcal{D}$ , если только забывающий обладает достаточной «различающей мощностью» на морфизмах, чтобы из $\mathrm{Hom}(d,d)$ восстановить всё богатство исходной категории (точнее образ функтора ).

Различные промежуточные категории $\mathcal{D}$ вместе с парами функторов и позволяют изучить монаду во всей её многогранности.

Из совокупности всех возможных сопряжений, порождающих монаду , можно построить категорию $\mathcal{Adj}_T$ . Её объектами будут тройки $(\mathcal{D},\, F:\mathcal{C} \to \mathcal{D},\, U: \mathcal{D} \to \mathcal{C})$ , функторы которой образуют сопряжение, дающее $T = U \circ F$ . Морфизмами между $(\mathcal{D}, F, U)$ и $(\mathcal{D}', F', U')$ будут такие функторы $K:\mathcal{D}\to\mathcal{D'}$ , что $K \circ F = F'$ и $U' \circ K = U$ .

Чем же может помочь столь сложно устроенная категория $\mathcal{Adj}_T$ ? Дело в том, что в её морфизмах зашифрованы взаимоотношения всех возможных реализаций монады . И самым замечательным фактом является то, что в ней существуют два полярных сопряжения — начальный и терминальный объекты. Эти сопряжения характер��зуют всю категорию и демонстрируют две противоположные стороны монады.

Начальное и терминальное разложение монады T на сопряжённые функторы. — Начальное и терминальное разложение монады `T` на сопряжённые функторы.

Начальный объект этой категории называется сопряжением Клейсли, а терминальный — сопряжением Эйленберга-Мура. Давайте рассмотрим их подробнее.

Сопряжение Клейсли

Пусть $(\mathcal{Kl}_T,F_{kl},U_{kl})$ — начальный объект категории $\mathcal{Adj}_T$ . Универсальное свойство начального объекта гласит, что для любого другого сопряжения $(\mathcal{D},F,U)$ существует единственный функтор $K:\mathcal{Kl}_T\rightarrow \mathcal{D}$ такой, что:

$K\circ F_{kl}=F,\hspace{2cm}U\circ K=U_{kl}.$

Функтор , как и любое другое отображение, способен лишь терять информацию (в лучшем случае, сохранять). И так как он ведёт из начального объекта в любой другой, то категория $\mathcal{Kl}_T$ обязана быть самой минимальной среди всех прочих объектов $\mathcal{Adj}_T$ .

С другой стороны, оказывается, что в $\mathcal{Adj}_T$ всегда найдётся такое сопряжение, где функтор будет сопоставлять объекты $\mathcal{C}$ и $\mathcal{D}$ инъективно, не «схлопывая» разные объекты в один, продолжая «различать» объекты исходной категории. На данный момент, это совсем не очевидный факт, но одним из его примеров будет терминальный объект в $\mathcal{Adj}_T$ , который мы рассмотрим чуть далее. Очевидно, что такие различающие сопряжения всегда окажутся полнее, «начальнее» любого забывающего. Значит, свободный функтор $F_{kl}$ начального сопряжения также обязан быть инъективным на объектах, сопоставлять каждому объекту из $\mathcal{C}$ ровно один объект в $\mathcal{Kl}_T$ .

Учитывая необходимость минимальности $\mathcal{Kl}_T$ и «различимость» $F_{kl}$ получаем, что объекты начальной промежуточной категории взаимно однозначно соответсmвуют объектам исходной: $\mathrm{Obj}(\mathcal{Kl}_T) \cong \mathrm{Obj}(\mathcal{C})$ !

Теперь разберёмся с морфизмами в $\mathcal{Kl}_T$ . Безо всяких обиняков будем считать объекты $X, Y: \mathcal{C}$ одновременно объектами в $\mathcal{Kl}_T$ , значит $\mathrm{Hom}_{\mathcal{Kl}_T}(F_{kl}X, F_{kl}Y) \equiv \mathrm{Hom}_{\mathcal{Kl}_T}(X, Y)$ . Кроме того, из сопряжения имеем $\mathrm{Hom}_{\mathcal{Kl}_T}(F_{kl}X, F_{kl}Y) \cong \mathrm{Hom}_{\mathcal{C}}(X, U_{kl}F_{kl}Y)$ . По условию задачи композиция этих функторов даёт монаду $U_{kl} \circ F_{kl}=T$ , так что в итоге получаем

$\mathrm{Hom}_{\mathcal{Kl}_T}(X, Y) \cong \mathrm{Hom}_{\mathcal{C}}(X, TY).$

То есть, каждый морфизм категории $\mathcal{Kl}_T$ — это по сути морфизм $X \to TY$ в исходной категории $\mathcal{C}$ ! Законы категории опираются на возможности монады $(T, \mu, \eta)$ :

для морфизмов $f: \mathrm{Hom}_{\mathcal{Kl}_T}(X,Y)$ и $g: \mathrm{Hom}_{\mathcal{Kl}_T}(Y,Z)$ имеем композицию $U_{kl}\,g \circ f = \mu_Z \circ Tg \circ f: \mathrm{Hom}_{\mathcal{Kl}_T}(X,Z)$ ,
а единица монады задаёт тождественный морфизм $\eta_X: \mathrm{Hom}_{\mathcal{Kl}_T}(X,X)$ .

Полученная категория называется категорией Клейсли.

Свободный функтор $F_{kl}$ преобразует морфизмы $f: \mathrm{Hom}_{\mathcal{C}}(X, Y)$ в $F_{kl}\,f=\eta_Y \circ f: \mathrm{Hom}_{\mathcal{Kl}_T}(X, Y)$ . В свою очередь, забывающий функтор $U_{kl}$ действует на $f: \mathrm{Hom}_{\mathcal{Kl}_T}(X, Y)$ следующим образом: $U_{kl}\,f = \mu_Y \circ Tf$ , а объекты он просто «запаковывает» в монаду: $X \overset{U_{kl}}{\to} TX$ . Эти функторы образуют так называемое сопряжение Клейсли.

Категория Клейсли трактует монаду как минимальный интерфейс — это просто возможность выстраивать целые пути из шагов-морфизмов вида $A \to TB$ . Мы не знаем, как «распаковывается» функтор , какой «эффект» несёт в себе, но зато мы точно умеем комбинировать «T-эффективные» морфизмы. Все другие сопряжения, дающие ту же самую монаду, будут устроены сложнее, чем начальное сопряжение Клейсли.

В Scala в библиотеке Cats морфизмы категории Клейсли (для монады T в категории типов) представлены классами примерно такого вида:

case class Kleisli[T[_]: Monad, A, B](run: A => T[B]):
  def compose[C](f: Kleisli[T, C, A]): Kleisli[T, C, B] =
    Kleisli(forget `compose` f.run) // μ ∘ T(run) ∘ f.run
  def andThen[C](f: Kleisli[T, B, C]): Kleisli[T, A, C] =
    f `compose` this
  def forget: T[A] => T[B] = // аналогичного метода нет в Cats
    flatten[T][B] `compose` fmap[T](run) // μ ∘ T(run) или (_: T[A]).flatMap(run)
  
object Kleisli:
  def fromFunction[T[_]: Monad as T] =
    [A, B] => (f: A => B) => T.pure[B] `compose` f // η ∘ f

По сути, это «T-эффективная» функция run, а также прямая и обратная композиции. Кроме того, здесь представлены методы fromFunction и forget, играющие роль свободного и забывающего функторов. Работает композиция Клейсли так:

val stringToInt = Kleisli((_: String).toIntOption)  
val signOfInt   = Kleisli((i: Int) => Option.when(i != 0)(  
  if i > 0 then "плюс" else "минус"  
))
  
val signOfStringNumber = signOfInt `compose` stringToInt
signOfStringNumber.run("42") // Some("плюс")

Возможности, предоставляемые Kleisli из Cats, значительно шире показанных здесь, но всё же с ними не очень-то удобно работать на практике, из-за необходимости постоянного обёртывания функций с помощью конструктора класса. К счастью, в библиотеке определены комбинаторы andThenF и composeF, работающие и для обычных функций:

import cats.syntax.all.*

val stringToInt: String => Option[Int]     = _.toIntOption
val signOfInt:   Int    => Option[Boolean] = i => Option.when(i != 0)(if i > 0 then "плюс" else "минус")

val isPositiveNumber = signOfInt `composeF` stringToInt
isPositiveNumber("42") // Some("плюс")

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

Итак, сопряжение Клейсли раскрывает монаду как интерфейс для комбинирования -эффективных вычислений. Давайте теперь посмотрим на противоположную сторону мон~~еты~~ады.

Сопряжение Эйленберга-Мура

Ни на что не намекая)), обозначим терминальное сопряжение как $(\mathcal{Alg}_T, F_{Alg}, U_{Alg})$ . Его универсальное свойство утверждает, что для любого сопряжения $(\mathcal{D}, F, U)$ , порождающего , существует единственный функтор $K:\mathcal{D}\rightarrow \mathcal{Alg}_T$ , называемый функтором сравнения, такой, что:

$U_{Alg}\circ K=U, \hspace{2cm} K \circ F=F_{Alg}.$

Этот универсальный функтор, как и любой другой морфизм в категории сопряжений, обязан сохранять сопряжения. Он действует между промежуточными категориями $\mathcal{D}$ , среди морфизмов которых точно есть все компоненты коединицы сопряжения $\varepsilon: F \circ U \rightsquigarrow Id_{\mathcal{D}}$ :

$\forall d:\mathcal{D},\; \varepsilon_d: \mathrm{Hom}_{\mathcal{D}}(FUd, d).$

Функтор сравнения обязан сохранять эти морфизмы именно как коединицы:

$K\varepsilon_{d} = \varepsilon _{Kd}^{Alg}.$

Чтобы соотнести данное правило с исходной категорией, подействуем на обе его стороны забывающим функтором $U_{Alg}: \mathcal{Alg}_T \to \mathcal{C}$ . Получим

$U_{Alg} K \varepsilon_d = U \varepsilon_d = U_{Alg} \varepsilon^{Alg}_{Kd}.$

В каждом сопряжении забывающий функтор переводит коединицу в морфизмы исходной категории $Id_U \circ \varepsilon: U \circ F \circ U \rightsquigarrow U$ . Так как $U \circ F = T$ , получаем, что $U \varepsilon_d: T(Ud) \to Ud$ — это «распаковка» эндофунктора для объектов образа , согласованая с законами монады.

Каждому объекту терминальной категории $a: \mathcal{Alg}_T$ взаимно однозначно соответствует компонента коединицы $\varepsilon^{Alg}_a$ , отвечающая за -распаковку объектов исходной категории $U_{Alg}a: \mathcal{C}$ . С другой стороны, в $\mathcal{Alg}_T$ нас приводят универсальные функторы из всех других сопряжений, у которых будут отличаться коединицы. Значит, объекты $a: \mathcal{Alg}_T$ будут отличаться для $\varepsilon_d$ разных сопряжений, даже если $d:\mathcal{D}$ для них будет общий. Другими словами, объекты $a: \mathcal{Alg}_T$ обязаны «помнить» каждый способ распаковки $U \varepsilon_d: T(Ud) \to Ud$ от каждого сопряжения $(\mathcal{D}, F, U)$ .

Для каждого $с: \mathcal{C}$ найдутся такое сопряжение $(\mathcal{D}, F, U)$ и такой объект $d: \mathcal{D}$ , что . Впитывая в себя все прочие сопряжения, терминальная категория не может потерять информацию об исходной и образ забывающего функтора $U_{Alg}$ должен покрывать всю исходную категорию $\mathcal{C}$ (совпадать с ней).

Собирая всё воедино, получаем, что объекты терминальной категории должны быть зависимой парой $(c: \mathcal{C},\, h: Tc \to c): \mathcal{Alg}_T$ , причём «распаковка» согласована с монадными «запаковкой» и «разматрёшиванием». Такие пары называются алгебрами монады , а промежуточная категория — это категория алгебр Эйленберга-Мура. То же название носит и само терминальное сопряжение.

Морфизмы между объектами и — это такие функции $f: a \to b$ , что выполняется равенство:

$f \circ h_a = h_b \circ Tf.$

Это гомоморфизмы алгебр для монады .

Забывающий функтор $U_{Alg}$ просто выбрасывает из объекта распаковку $U_{Alg}(a, h_a) = a$ , а на морфизмы он действует тривиально $U_{Alg}f = f$ . Свободный же функтор $F_{Alg}$ несколько хитрее. Над произвольным объектом $c: \mathcal{C}$ он строит свободную алгебру $F_{Alg}c = (Tc,\, \mu_c: TTc \to Tc): \mathcal{Alg}_T$ , где естественное преобразование $\mu$ — это то самое монадное «разматрёшивание» для . Действие же свободного функтора на морфизмы аналогично действию исходного функтора: $F_{Alg}f = Tf$ .

Замечательный факт — монада структурно эквивалентна своей категории алгебр! Сопряжение Эйленберга-Мура показывает, что любая цепочка монадических вычислений в конечном итоге находит своё завершение в алгебре. Именно алгебра определяет семантику редукции: она диктует, как именно накопленная структура эффектов будет «схлопнута» в конкретное значение базовой категории.

Эндофунктор $T:\mathcal{C} \to \mathcal{C}$ переводит вычисления из $\mathcal{C}$ в подкатегорию $T\mathcal{C}$ , что в общем случае не будет решением задачи. Выбор алгебры (способа распаковки!) помогает вернуться обратно из $T\mathcal{C}$ . Если у нас есть программа с T-эффектами $f: \mathrm{Hom}_{\mathcal{C}}(a,\, Tb)$ , то это буквально означает морфизм в категории Клейсли $f: \mathrm{Hom}_{\mathcal{Kl}_T}(a,\, b)$ . Тогда получить реальную программу $prog: \mathrm{Hom}_{\mathcal{C}}(a,\, b)$ можно с помощью функтора сравнения $K: \mathcal{Kl}_T \to \mathcal{Alg}_T$ и компонент единицы и коединицы сопряжения Эйленберга-Мура для конкретной алгебры $(b, h: \mathrm{Hom}_{\mathcal{C}}(Tb, b))$ :

$prog = \varepsilon^{Alg}_{(b, h)} \circ K(f) \circ \eta_a.$

Давайте посмотрим, как это всё выглядит в программном коде на Scala. Сперва мы построим композицию вычислений в терминах сопряжения Клейсли (мы это уже делали раньше), затем посредством функтора сравнения перейдём к категории Эйленберга-Мура и, наконец, выполним вычисления, используя коединицу терминального сопряжения и выбранную нами алгебру.

Функтор сравнения преобразует стрелки Клейсли в гомоморфизм свободных алгебр:

type ComparisonFunctor[F[_]] = [A, B] => Kleisli[F, A, B] => (F[A] => F[B])  

val optionCompFunctor: ComparisonFunctor[Option] =  
  [A, B] => (kl: Kleisli[Option, A, B]) => (optA: Option[A]) =>  
    optA.flatMap(kl.run)

Да, гомоморфизм свободных T-алгебр типов A и B — это функция T[A] => T[B], причём гомоморфность «распаковок» h: T[T[X]] => T[X] гарантируется реализацией функтора сравнения, в которой используется T-«разматрёшивание».

Метод получения реального вычисления из -программы будет таким:

type Algebra[F[_]] = [A] =>> F[A] => A

def eval[T[_] : Monad as T, A, B](f: Kleisli[T, A, B]) = (h: Algebra[T][B]) =>  
  h `compose` compFunctor(f) `compose` T.pure[A]

В данном случае компонента коединицы сопряжения Эйлеберга-Мура $\varepsilon^{Alg}_{(b, h)}$ просто отдаёт функцию «распаковки» h.

Чтобы вычислить определённую ранее программу isPositiveNumber: Kleisli[Option, String, String] достаточно выбрать одну из возможных Option-алгебр для String:

val algebra: Algebra[Option][String] = _.getOrElse("эээ...") // Option[String] => String

val realProgram: String => String = eval(isPositiveNumber)(algebra)

realProgram("сорок два") // эээ...

T-алгебра выступает в роли интерпретатора эффекта T. В данном случае мы выбрали, как именно будет обрабатываться ситуация отсутствия искомого значения. Сопряжение Эйленберга-Мура представляет монаду как обещание завершения вычислений, когда будет фиксирована конкретная алгебра.

Переключение сопряжений

Программисты больше всего имеют дело с монадами в представлении сопряжения Клейсли. Отдельные функции с эффектами ввода-вывода, спрятанным в контейнерах вроде IO или ZIO, композируются посредством монадической композиции, гарантированной изначальной изначальным свойством любой монады. А терминальная интерпретация такой программы обычно скрывается в библиотечных инструментах, которые рассматривают монаду уже в представлении Эйленберга-Мура и подставляют свои универсальные алгебры для распаковки контейнеров.

Иногда возникает необходимость и в ручной распаковке контейнеров, таких как List, Option, Either, Reader и т.п. В таком случае программистам приходится обращаться к коединице сопряжения Эйленберга-Мура, которая чаще всего представлена методом свёртки fold (его специализированные версии часто прячутся под псевдонимами). Компонента коединицы фиксируется, когда в метод свёртки передаются параметры, соответствующие выбранной алгебре контейнера.

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

Обычно промежуточная категория богаче исходной. Категория Клейсли обогащена специальными морфизмами, а в категории Эйленберга-Мура каждому объекту исходной категории сопоставляется целая совокупность объектов-алгебр. В рассмотренном в предыдущей части обзора разложении State = Reader ∘ Writer в промежуточной категории объекты являются парами (A, S), то есть каждый объект «обогащается состоянием».

Реже встречаются ситуации, когда выбранную монаду оказывается удобнее подменить на изоморфную, или просто похожую. Замена сопряжения зачастую позволяет тем или иным образом оптимизировать вычисления, например

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

Наиболее интересны из них те, что проходят через категорию алгебр функтора монады (отличается от категории алгебр монады!), или же через категорию, дуальную исходной. В первом случае речь идёт о свободной монаде, а во втором — о монаде продолжения. Будучи по сути надстройками, обе они изоморфны исходной монаде и обладают как определёнными преимуществами, так и недостатками. Мы рассмотрим эти монады подробнее в продолжении обзора.

Option с фокусом на фильтрацию

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

case class Filterable[A](
  opt: Option[A],
  predicate: A => Boolean = _ => true
)

Удобство такой конструкции заключается в том, что это «ленивая» фильтрация, сохраняющая исходное значение даже при фиксированном предикате. Своеобразная «фильтрация без потерь». Мы в любой момент можем модифицировать предикат, или подсмотреть, какое именно значение не прошло заданное условие.

Конструктор типов Filterable определяет собственную подкатегорию типов, через которую можно проложить сопряжение, порождающие всё ту же монаду Option. Свободный функтор F — это эндофунктор в категории типов. По сути это ничто иное, как Functor[Filterable]. Но забывающий U несколько хитрее, так как он преобразует только функции вида Filterable[A] => Filterable[B]. Он не будет привычным эндофунктором в категории типов, и для него неприменим определённый в обзоре класс типов Functor и многие другие. Но нам подойдут hom-объекты в категории подкатегорий типов, и в итоге мы вполне можем собрать эндофунктор для Option из свободного и забывающего:

val fFunctor: Hom[Id, Filterable] = [A, B] => (f: A => B) =>  
  (fa: Filterable[A]) => Filterable(fa.opt.map(f), _ => fa.opt.exists(fa.predicate))  
  
val uFunctor: Hom[Filterable, Option] = [A, B] => (f: Filterable[A] => Filterable[B]) =>  
  (oa: Option[A]) => f(Filterable(oa)).opt  
  
// Option ≅ U ∘ F
val optionFunctor: Hom[Id, Option] = [A, B] => (f: A => B) =>  
  uFunctor[A, B] compose fFunctor[A, B] apply f

Для реализации сопряжения нам понадобятся такие естественные преобразования:

val fObj: Id         ~> Filterable = [A] => (a: A)              => Filterable(Some(a))  
val uObj: Filterable ~> Option     = [A] => (fa: Filterable[A]) => fa.opt.filter(fa.predicate)

Сама конструкция естественных преобразований была у нас сформулирована только для обычных эндофункторов, но забывающий U не является таковым. К счастью, обычно он используется только в комбинации со свободным, что позволяет нам воспользоваться соотношением Option ≅ U ∘ F. Тогда единицу сопряжения мы получаем в виде вертикальной композиции преобразований fObj и uObj, а вместо чистой коединицы у нас будет горизонтальная композиция $\varepsilon \circ Id_F$ . Благо именно такая структура нам и нужна для вывода преобразования «разматрёшивания» монады:

val η:  Id                  ~> Option     = uObj ⋅ fObj // ≅ Some.apply  
val εF: Filterable ∘ Option ~> Filterable = [A] => (foa: Filterable[Option[A]]) =>
  Filterable(foa.opt.flatten, foa.predicate compose Some.apply)

val μ: Option ∘ Option ~> Option = [A] => (ooa: Option[Option[A]]) => uObj(εF(Filterable(ooa)))

Таким образом, мы убедились, что сопряжение наших функторов $F \dashv U$ порождает знакомую монаду Option.

Так же, как это было с сопряжением Клейсли, здесь мы получаем дополнительные возможности в промежуточной категории. Посмотрите на такой код:

case class CreditCard(limit: Int, active: Boolean)  
  
val filteringCard: Filterable[CreditCard] = fObj(CreditCard(1000, false))  
val validFilteringCard: Filterable[CreditCard] = filteringCard.copy(predicate = _.active)  
  
val validCardOpt: Option[CreditCard] = uObj(validFilteringCard)
if validCardOpt.isEmpty
  then println("Валидация не пройдена для " + validFilteringCard.opt)

Сперва мы объявили объект filteringCard в промежуточной категории. Затем преобразовали его в validFilteringCard, заменив предикат. Применив забывающее преобразование, мы получили validCardOpt, в котором уже не осталось данных о кредитной карте, не прошедшей валидацию. Но эта информация всё ещё сохраняется в промежуточной категории в объекте validFilteringCard! Более того, мы можем снова модифицировать предикат. Например, давайте его инвертируем, чтобы продолжить работу только с неактивированной кредитной картой:

val invalidFilteringCard = validFilteringCard.copy(predicate = !validFilteringCard.predicate(_))  

val invalidCardOpt: Option[CreditCard] = uObj(invalidFilteringCard)  
  
invalidCardOpt.foreach(card => println("Неподходящая карточка: " + card))

Тезисы

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

Левосопряжённый функтор сопоставляет объектам исходной категории «наиболее свободные» объекты промежуточной. Обычно дальнейшие вычисления производятся именно в этой категории, с использованием её богатой структуры. Затем правосопряжённый функтор возвращает вычисления в исходную (под)категорию, «забывая» всё лишнее.

Сопряжения, порождающие монаду, образуют целую категорию, в которой есть начальный и терминальный объекты — сопряжения Клейсли и Эйленберга-Мура. Промежуточная категория Клейсли раскрывает монаду как интерфейс для композиции эффективных вычислений, тогда как категория алгебр Эйленберга-Мура акцентирована на результате вычислений — финальной «распаковке» монады. Программисты привыкли работать с монадами прежде всего именно в представлении Клейсли, благо забывающий функтор этого сопряжения тривиален. Представление Эйленберга-Мура обычно используется библиотечными методами для финальной «распаковки» монады, воплощающей её эффекты. Но иногда программистам и самим приходится выбирать нужные объекты в категории алгебр для распаковки (свёртки, fold) контейнеров вроде Option или List.

Начальное сопряжение Клейсли порождает «свободу»: мы можем написать что угодно, но не можем это закончить.
Терминальное сопряжение Эйленберга-Мура порождает «необходимость»: чтобы закончить, мы обязаны подчиниться структуре конкретной алгебры.
Если категория Клейсли — это пространство чистых программных путей, то категория Эйленберга-Мура — это пространство финальных интерпретаций.

Также иногда бывает полезным представить монаду в виде какого-то специального сопряжения. Его строят через категорию, обогащённую дополнительной структурой, позволяющей упростить какие-либо промежуточные вычисления.

В следующей части обзора мы будем получать монады для заданного функтора, путём его декомпозиции на сопряжённые.