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

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

1. Hom-типы

2. Функторы

3. Естественные преобразования

4. Монады (данная публикация)

Содержание

• Монада — это «разматрёшивание»!

• Методы для монады

• Моноид в категории эндофункторов

• Зоопарк монад

• Композирование монад

• Распределительный закон для монад

• Аппликативный функтор

• Комонада

• Дополнительная литература

• Промежуточный итог

Мотивация

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

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

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

Для статически типизированного функционального программирования характерны такие требования к алгоритмам:

• перенос проверки корректности программы на этап компиляции, что обеспечивается максимальным использованием системы типов языка;

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

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

Всё это приводит тому, что во многих языках программирования асинхронность так или иначе (через «синтаксический сахар») реализуется посредством контейнерных типов F[_]. В экземплярах F[A] инкапсулирован контекст вычисления целевого значения типа A. Например, есть специальные контейнерные типы, обеспечивающие асинхронность вычислений последовательности функций вида A => F[B].

Но, кроме того, есть ещё и другие полезные контейнеры F[_], например, списки и опциональные значения. Отличаются они лишь тем самым пресловутым контекстом вычисления, «эффектом». Копая глубже, можно обнаружить, что и любые другие обобщённые типы специализированы на обработке каких-то своих полезных эффектов. И оказывается, что методы комбинирования вычислений у всех таких контейнеров очень похожи.

На передний план выходит сама техника работы с абстрактными контейнерными типами. И прежде всего, техника композиции вычислений, производимых как в одном и том же контейнере, так и в разных. Ранее мы уже рассмотрели один из важных элементов этой техники — преобразования, предоставляемые эндофукнторами в категории типов. В данной части мы уделим внимание другому элементу этой техники — «разматрёшиванию» эффектов.

Монада — это «разматрёшивание»!

Нам нужно научится композировать «эффективные функции», например f: A => F[B] и g: B => F[C]. Если у нас есть экземпляр Functor[F], то можем попробовать сделать так:

def compose[F[_]: Funcor, A, B, C](f: A => F[B], g: B =>; F[C]): A => F[F[C]] =
  f andThen g.lift[F]

Сразу видна проблема — искомый результат «заматрёшился» в (F ∘ F)[C], тогда как нам хотелось бы получить просто F[C]. Значит для F[_] требуется возможность «разматрёшивания», то есть, функция вида (F ∘ F)[C] => F[C] , универсально работающая для любого C. Очевидно, что речь идёт о естественном преобразовании

type Flatten[F[_]] = F ∘ F ~> F

def flatten[F[_]: Flatten] = summon[Flatten[F]]

def compose[F[_] : {Functor, Flatten}, A, B, C](g: B => F[C], f: A => F[B]): A => F[C] =
  f andThen lift(g) andThen flatten[F][C]

Преобразование Flatten[F] должно быть естественным для Functor[F]. И вроде, можно было бы поискать такой способ композиции, который не использует естественные преобразования, и не задействует функтор вообще. Но из высказанных ранее требований предсказуемости поведения (и многих полезных следствий из этого), любые реализации такой композиции обязаны быть эквивалентными представленной выше.

Теперь может показаться, что естественного преобразования Flatten[_[_]] должно быть достаточно для решения задачи композиции «эффективных функций». Однако, не всё так просто. Необходимость предсказуемости композиции накладывает дополнительные ограничения.

Например, когда мы композируем три функции f, g и h, то сделать это можно уже двумя разными способами: compose(f, compose(g, h)) или compose(compose(f, g), h). Меняется не порядок вычисления функций, а лишь порядок композиции. Мы (все, я уверен в этом) ожидаем, результат не должен меняться от этого порядка. И данное требование ассоциативности композиции перекладывается на преобразование Flatten[F].

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

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

Для эндофункторов в категории типов это правило говорит нам, что неважно, «разматрёшиваем» ли мы сперва внешнюю композицию F ∘ F, а потом то, что осталось, или же мы начнём внутри внешнего F, пользуясь его функториальностью. То есть, получается ещё одно правило, помимо естественности, связывающее преобразование Flatten[F] с эндофунктором Functor[F].

Но и это ещё не всё!

Преобразование Flatten требуется для композиции эффективных функций вида A => F[B], возвращающими «запакованные» значения. Но как же происходит эта самая «запаковка»? Пожалуй, самая простая отвечающая за это функция, будет преобразованием:

type Pure[F[_]] = Id ~> F

def pure[F[_]: Pure] = summon[Pure[F]]

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

А теперь посмотрите на этот фрагмент кода:

val a: A         = ??? // какое-то значение
val f: A => F[B] = ??? // какая-то функция

val fb1: F[B] = f(a)
val fb2: F[B] = pure[F](a).flatMap(f)

Как считаете, должны ли значения fb1 и fb2 совпадать для любых A, B, F[_], f и a? Требование предсказуемости обязывает нас обеспечить это. Нам нужно гарантировать, что такая диаграмма будет коммутативна:

Алгебры монады

С монадой бывает полезно согласовать и «распаковку». Только законы такого согласования накладываются уже на последнюю, и называется она «алгеброй монады» (F[A] => A для выбранного объекта A). Такие алгебры образуют собственную категорию типов с интересными, а главное, полезными структурами в ней. С категорией монадных алгебр мы ещё встретимся в продолжении обзора.

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

Монада определяется как пара естественных преобразований для некоего значения эндофунктора :

удовлетворяющая законам:

• закон ассоциативности, который формально можно выразить равенством ;

• преобразования согласуются друг с другом: .

В программировании часто можно встретить определения, похожие на такое:

type Monad[F[_]] = (
  lift   : Functor[F],
  pure   : Pure   [F], // Id    ~> F
  flatten: Flatten[F], // F ∘ F ~> F
)

В других источниках можно встретить следующие формулировки:

• «монада — это эндофунктор с парой естественных преобразований, удовлетворяющих…», или

• «монада — тройка, состоящая из эндофунктора и пары естественных преобразований…»

Так или иначе, все эти определения буквально закрепляют утверждение, что «монада — это эндофунктор». А эндофункторы, в свою очередь, прочно ассоциируется у программистов с ковариантными обобщёнными типами… Отсюда и появляются фразы, вроде, «F[+_] — это монада».

Тяжёлое наследие математики.

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

А вы знали, что с точки зрения математики, автомобиль — это четыре колеса, к которым присоединена рама со всеми остальными элементами? Ведь если нет четырёх колёс, то это уже будет что-то другое… Да, «автомобиль» способен «двигаться сам», но это где ближе к концу его определения. Для математиков же гораздо важнее колёса!

И на таких колёсах они сидят уже не первый век.

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

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

А монада — это прежде всего преобразование «разматрёшивания» эндофунктора. Именно эта возможность определяет новое понятие, саму необходимость его введения. А все остальные слова определения вторичны, они лишь уточняют эту самую возможность.

Явное использование «запаковки» Pure встречается редко и обычно подсвечивает места, где стоило бы поискать, как можно улучшить алгоритм, избавившись от явного вызова pure. А вот функториальность для «разматрёшивания» оказывается важнее, чем для других естественных преобразований. Дело в том, что мы изобретали монаду для решения задачи композиции F-эффективных функций, которое неизбежно задействует и функториальность F[_] и, собственно, наше «разматрёшивание». Давайте посмотрим, какие монадные возможности используются на практике.

Методы для монады

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

given  funcorFromMonad: [F[_]: Monad as F] => Functor[F] = F.lift
given    pureFromMonad: [F[_]: Monad as F] => Pure   [F] = F.pure
given flattenFromMonad: [F[_]: Monad as F] => Flatten[F] = F.flatten

Теперь, если у нас в контексте будет монада Monad[F], значит сразу будут доступны как фукториальный метод lift, так и оба преобразования pure и flatten, введённые ранее.

На практике функториальность и «разматрёшивание» часто используются вместе в таких методах:

extension [F[_]: Monad, A](fa: F[A])
  def flatMap[B](afb: A => F[B]) = fa.map(afb).flatten
  
extension [F[_]: Monad, A, B](afb: A => F[B])
  infix def andThenF[C](bfc: B => F[C]) = afb andThen lift[F](bfc) andThen flatten

ООПшно-имепративный метод flatMap привычен большинству scala-программистов. Есть также вспомогательные методы, основанные на flatMap:

extension [F[_]: Monad, A](fa: F[A])
  def flatTap [B](fab: A => F[B]) = fa.flatMap(a => fab(a).map(_ => a))
  
  def product [B](fb: F[B]) = fa.flatMap(a => fb.map(a -> _))
  def productL[B](fb: F[B]) = fa.flatMap(a => fb.map(_ => a))
  def productR[B](fb: F[B]) = fa.flatMap(_ => fb            )

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

В различных языках программирования часто встречается специальный синтаксис, позволяющий не упоминать этот метод явно, а компоновать вычисления в привычном императивном стиле стековых вычислений. В Haskell это do-нотация, в C# — Linq, а в Scala используются for-выражения. Ещё, в разных языках встречается и альтернативный подход, вроде «direct style» в Scala. Многие считают такой синтаксический сахар преимуществом языка, подслащающим работу с «трудноперевариваемыми» монадами. Я же вижу в этом огромный шаг назад, так как императивно-стековый стиль плохо сочетается со стабильностью и качеством алгоритмов и влечёт к типичным ошибкам, которые регулярно просачиваются через заслоны тестирования. Проблемы заложены в саму концепцию этого стиля, от их появления не возможно радикально защититься, оставаясь в его рамках.

С другой стороны, чисто ФП-шный комбинатор andThenF (и дуальный composeF) знаком, возможно, не всем. А ведь, это наиболее надёжный, лаконичный и выразительный способ комбинирования эффективных функций:

val getPackage:         PackageKey     => IO[Package]
val handlePackage:      Package        => IO[HandlingResult]
val sendNotification:   HandlingResult => IO[Unit]

val greatBusinessLogic: PackageKey     => IO[Unit] =
  getPackage       andThenF
  handlePackage    andThenF
  sendNotification

Здесь мы сталкиваемся с ещё одними F-подкатегориями типов, называемыми категориями Клейсли. Объектами в них являются всё те же типы, а вот морфизмы — «F-эффективные» функции A => F[B]. Комбинатор andThenF играет роль оператора композиции Клейсли. В библиотеке Cats у него также есть символический псевдоним >=> — изобретённый хаскелистами оператор «рыбка» (аналогично, <=< для composeF).

В Scala чаще всего используются монады, реализующие класс типов Monad[F], схожим образом описанный в библиотеках Cats и Scalaz.

Моноид в категории эндофункторов

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

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

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

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

Монада — это моноид в категории эндофункторов.

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

Зоопарк монад

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

Монады строятся для эндофункторов, которые, в свою очередь, опираются на ковариантные конструкторы типов. Функториальность и «разматрёшивание» таких контейнерных типов используют и преобразуют контекст «хранения» значения, что и определяет связанный с ними «эффект». Поэтому, «зоопарк» монад мы представим как сопоставление конструкторов типов с его эффектом.

Самые простые конструкторы типов — это алгебраические операции — сумма, произведение и экспоненциал типов. Именно так и образуются «базисные» монады в программировании. Для наглядности многопараметрические конструкторы типов записаны не в привычном, а в каррированном виде, что не меняет их сути.

Частным случаем эффекта альтернативного результата является просто его отсутствие. За это отвечает контейнер Option = [X] =>> 1 + X ≅ Either[Unit].

Из базисных конструкторов типов собираются составные, для которых также можно вывести монады. Например, монада состояния, когда значение в контейнере преобразуется с использованием и изменением некоего состояния:

type State[S] = Reader[S] ∘ Writer[S] // S => S × X

Но не все составные монады собираются из ковариантных конструкторов типов. Хороший контрпример — монада продолжения:

type Cont[A] = [X] =>> (X => A) => A

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

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

case class Fix[F[_]](unfix: F[Fix[F]]) // неподвижная точка конструктора типов

type OptCell[A] = [X] =>> Option[(A, X)]     // 1 + A × X
type List[A] = Fix[OptCell[A]]               // 1 + A × List[A]

type OptCell2[A] = [X] =>> Option[(A, X, X)] // 1 + A × X × X
type Tree[A] = Fix[OptCell2[A]]              // 1 + A × Tree[A] × Tree[A]

Рекурсивные структуры данных считают носителями эффекта недетерминированности (неопределённости) — при преобразованиях контейнера меняются сразу все его элементы, так как за ранее не определено, какой (какие) из них пригодится в итоге.

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

enum Lazy[A]:
  case Pure   [X](x: X)                           extends Lazy[X]
  case FlatMap[X, Y](y: Lazy[Y], f: Y => Lazy[X]) extends Lazy[X]

По сути, это список преобразований, приводящий к значению целевого типа Lazy[X]. Но у каждого такого преобразования тип зависит от его позиции в этом списке. Обратите внимание на параметр y: Lazy[Y] — он как бы «спрятан» за родительским Lazy[X], но каждом шагу Y скорее всего будет отличаться от X. Эффект, соответствующий этому контейнеру — это ленивая композиция вычислений. Удобство контейнера Lazy в том, что вычисления накапливаются чисто, без непосредственного выполнения функций, которые могут содержать побочные эффекты.

На этом принципе основан контейнер IO из библиотеки Cats. Например, вся «асинхронщина» там срабатывает лишь в самом конце, «под капотом», в момент интерпретации ленивой композиции эффективных функций. А в библиотеке ZIO представлен одноимённый контейнер, который очень упрощённо можно себе представить, как немного усложнённый IO:

type IO = Lazy
type ZIO[R, E, X] = (Reader[R] ∘ Either[E] ∘ IO)[X] // R => (E + Lazy[X])

В Scala есть встроенные «недомонады» Try и Future. У них также есть методы map и flatMap со стандартными сигнатурами, но они оказываются не достаточно «законопослушными». Основная проблема заключается в том, что функции преобразования для них срабатывают не внутри, но снаружи контейнера, то есть «грязно», что ломает ссылочную прозрачность и предсказуемость поведения. А значения Future так и вовсе зависят от времени. Поэтому для обеспечения надёжности кода вместо этих контейнеров рекомендуется использовать именно ленивые IO/ZIO.

Ленивые монады можно считать частным случаем свободных монад Free[F, A]. Они позволят лениво комбинировать вычисления с эффектом произвольного контейнера F[_]. «Свобода» заключается в том, что мы никак не зависим от наличия монадных и даже функториальных возможностей для F[_]. Более того, они не обязательны даже на этапе непосредственно выполнения «ленивой» программы! Свободные монады являются основой специальной техники функционального программирования, когда бизнес-эффекты описываются как абстрактные обобщённые типы, без реализации логики, затем из них строится ленивая программа, которая в конце интерпретируется уже в другой контейнер, например cats.effect.IO[_]. Само собой, все эти преобразования между контейнерами осуществляются посредством естественных преобразований.

Стоит отметить ещё одну важную разновидность монад — монадные трансформеры. Дело в том, что функторов у нас большое множество, а их комбинаций и того большое. Описать отдельные монады для каждой такой комбинации — неблагодарная работа, а автоматический вывод заблокирован фразой «монады не композируются»)). Но оказывается, что для многих конкретных функторов можно описать монаду его композиции с любыми другими функторами, монады которых известны. То есть можно трансформировать монаду любого функтора в монаду его композиции с фиксированным, выбранным заранее.

А именно, существуют такие F[_], что для любого G[_] и известной Moand[G] можно получить Monad[G ∘ F]. В библиотеке Cats методы таких композитных монад реализуются по ООП-шному в специальных классах-трансформерах, связанных с фиксированным F[_]. Их названия традиционно совпадают с названием их исходных контейнеров, но в конце добавляется буква T: ReaderT, StateT, ContT. Например, для Option получается что-то вроде такого:

class OptionT[F[_] : Monad as F, A](val fOptA: F[Option[A]]): // класс-носитель монадных возможностей F ∘ Option
  def flatMap[B](f: A => OptionT[F, B]): OptionT[F, B] =
    OptionT(fOptA.flatMap(_.fold[F[Option[B]]](F.pure(None))(f andThen {_.fOptA})))
  def map[B](f: A => B): OptionT[F, B] = flatMap(f andThen OptionT.pure[F][B])

object OptionT:
  def pure[F[_]: Monad as F] =  [A] => (a: A) => OptionT(F.pure(Some(a)))

На самом деле постоянное «поднятие» значений и функций в «мир трансформеров» может оказаться весьма утомительным. На практике мне встречались только конструкции вида EitherT[IO, BusinessError, A], и работа с ними не вызывала большого восторга…

Композирование монад

Представленные выше монадные трансформеры являются одним из инструментов для композирования монад. А именно, они дают возможность построить монаду для KnownFT[AnyG] ≅ AnyG ∘ KnownF, где KnownF[_] известен, а AnyG[_] — произвольный контейнер, но для него есть Monad[AnyG]. И здравый смыл, и практика подсказывают, что подобный трансформер при желании можно реализовать для каждого контейнера KnownF[_], который может вам потребоваться.

И всё же, можно ли закрыть вопрос для абсолютного любого AnyF[_], для которого также известен Monad[AnyF]? В предыдущей части был представлен compositeFunctor — он из эндофункторов Functor[F] и Functor[G] автоматически выводит Functor[G ∘ F]. Можно ли подобный трюк провернуть и для получения Monad[G ∘ F]?

Итак, мы ищем следующую функцию

def composeMonads[F[_]: Monad, G[_]: Monad]: Monad[G ∘ F]

Основную сложность представляет вывод Flatten[G ∘ F] = (G ∘ F) ∘ (G ∘ F) ~> (G ∘ F). Раскрыв скобки, слева мы получим конструкцию G ∘ F ∘ G ∘ F, которую какими-то средствами нужно свести к G ∘ F.

Программисты исследовали вопрос композиции монад ещё в прошлом тысячелетии. В частности, классической работой о комбинировании монад является статья 1992 года Combining monads (документ в формате PostScript несложно сконвертировать в PDF). Предложенные там идеи развивает работа Composing monads (Марк Джонс и Люк Дюпоншель, 1993). Основным их результатом являются способы построения композиции монад с использованием одного из трёх естественных преобразований:

type Prod[F[_], G[_]] = (G ∘ F ∘ G) ~> (F ∘ G)
type Dorp[F[_], G[_]] = (F ∘ G ∘ F) ~> (G ∘ F) // prod наоборот))
type Swap[F[_], G[_]] = (F ∘ G)     ~> (G ∘ F) // будет рассмотрен ниже

В статье также говорится, что большие сложности представляют монады композиций с рекурсивными конструкторами типов, например, со списком. Обеспечение ассоциативности для таких монад оказалось непреодолимым препятствием для реализации трансформера ListT в библиотеке Cats. В свою очередь, в библиотеке Scalaz реализовали-таки ListT, просто проигнорировав закон ассоциативности. Джонс с Дюпоншелем в своей статье рекомендуют программистам смириться с подобным беззаконием)).

Остаётся не ясным, является ли исчерпывающим список преобразований, представленный в их работе. Могут ли быть такие композитные монады, которые не получится построить из составляющих с помощью этих преобразований? (ИИ-чаты утверждают, что могут быть, но их мнение не вызывает доверия. Если знаете ответ, пожалуйста, напишите в комментариях.)

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

Вопрос композиции монад оказывается непростым даже «на пальцах». Есть мнение, что, что композиция не всех монад может дать новую монаду… И всё же, нет сомнений, что для любых ковариантных F[+_] и G[+_] всегда найдётся законопослушная реализация Monad[G ∘ F]. Вот только собрать её из Monad[F] и Monad[G]… не просто)).

Сейчас же мы посмотрим, как в композировании монад помогает естественное преобразование Swap из списка, предложенного Вадлером и продолжателями.

Распределительный закон для монад

В левой части преобразования Flatten[G ∘ F] мы хотим получить F ∘ F и G ∘ G, чтобы было к чему применять Flatten[F] и Flatten[G]. Для этого надо переставить F и Gместами в середине выражения. То есть, нам нужно преобразование

type Swap[F[_], G[_]] = (F ∘ G) ~> (G ∘ F)

Подставим его в composeFlatten, и получим (G ∘ G) ∘ (F ∘ F), которое уже легко сворачивается до G ∘ F.

Подстановка в естественных преобразованиях

Если есть естественное преобразование A ~> B, то можно получить преобразование F ∘ A ∘ G ~> F ∘ B ∘ G (просто вспомните про функториальность F). То есть, мы можем подставить B вместо A также, как мы привыкли это делать в уравнениях обычной алгебры. Только если равенство позволило бы и A подставлять вместо B, то со стрелками ~> такое уже не прокатит. Да и не нужно)).

В итоге получаем

def composeFlatten[
  F[_]: {Functor as liftF, Flatten as flattenF}, // liftF в данной реализации не используется
  G[_]: {Functor as liftG, Flatten as flattenG}
](using Swap[F, G] as swap): Flatten[G ∘ F] = // обратите внимание на порядок F и G!
  [A] => (gfgfa: G[F[G[F[A]]]]) =>
    (liftG(swap) andThen flattenG andThen liftG[flattenF])(gfgfa)

Для того, чтобы результат вычисления composeFlatten[G ∘ F] был основой для полноценной монады необходимо, чтобы Swap[F, G] удовлетворял дополнительным законам, сохраняющим свойства монады G ∘ F. В этом случае естественное преобразование F ∘ G ~> G ∘ F называется распределительным (дистрибутивным) законом.

Наличие распределительного закона Swap[F, G] достаточно, чтобы монады для F и G композировались. Для многих конкретных F[_] существуют более или менее естественные реализации Swap[F, _[_]], единообразно работающие для любого G[_]. Но в общем случае оказывается, что

Рассмотрим композиции Reader и State:

type Reader[A] = R =>     A  // для удобства фиксируем R
type State [A] = S => (S, A) // для удобства фиксируем S

Преобразование в одну сторону достаточно простое:

val swapSR: (State ∘ Reader) ~> (Reader ∘ State) =
  [A] => (sra: S => (S, R => A)) =>
    (r: R) => (s1: S) =>
      val (s2, ra) = sra(s1)
      s2 -> ra(r)

Это вполне себе дистрибутивный закон, который посредством composeFlatten можно положить в основу законопослушной Monad[Reader ∘ State].

А вот обратное преобразование Reader ∘ State ~> State ∘ Reader не получится реализовать без потерь. Например,

val swapRS: (Reader ∘ State) ~> (State ∘ Reader) =
  [A] => (rsa: R => S => (S, A)) =>
    (s: S) =>
      val ra2 = (r: R) => rsa(r)(s)._2
      s -> ra2

уже не будет дистрибутивным законом, так как оно не согласуется с монадами композиций конструкторов типов. Дело в том, что контейнер State обслуживает эффект изменения состояния S. Но наша реализация буквально забывает новое состояние, каждый раз возвращая исходное. Очевидно, что с использованием такого преобразования composeFlatten вернёт неправильное «разматрёшивание», неудовлетворяющее законам монады.

Тем не менее, законопослушный Flatten[Reader ∘ State] вполне себе существует:

given stateReaderFlatten: Flatten[State ∘ Reader] =
  [A] => (srsra: (State ∘ Reader ∘ State ∘ Reader)[A]) =>
    (s1: S) =>
      val (s2, sra) = srsra(s1)
      val ra = (r: R) => sra(r)(s2)._2(r)
      s2 -> ra

На его основе строится честная монада для Reader ∘ State.

Значит, если есть монада, то вовсе не обязательно, что она реализуется через некоторый Swap!

С точки зрения теории категорий, естественные преобразования, согласующиеся с монадной структурой, формируют категорию монад. В частности, дистрибутивный закон F ∘ G ~> G ∘ F определяет морфизм между монадами для F ∘ G и G ∘ F. Но в этой категории вовсе не обязательно должны существовать морфизмы между любыми двумя монадам!

Тем не менее, преобразование Swap обладает самостоятельной ценностью в программировании, безотносительно идеи «разматрёшивания». Переставлять контейнерные типы приходится достаточно часто. Наверняка вы не раз встречались с необходимостью перестановки своего глобального контейнера эффектов с Option, или List. Например:

val urls: List[Url] = ??? // какие-то адреса
def getStringFromUrl(url: URL): IO[String] = ??? // метод загрузки контента

val tasks: List[IO[String]] = urls.map(getStringFromUrl)

Получить одну задачу на список из списка задач нам поможет преобразование sequense: List ∘ IO ~> IO ∘ List:

val contents: IO[List[String]] = sequense(tasks)

Перестановка контейнеров, аналогичных спискам, предоставляется классом типов Traversable[F[_]]. Подробнее мы рассмотрим его в продолжении обзора.

А сейчас разберём ещё одну перестановку, определяющую такое понятие, как

Аппликативный функтор

Переставлять полезно не только обычные функторы, но и бифункторы. Соответствующие преобразования выглядят так:

type Swap2[Bi[_, _], F[_]] = [A, B] => Bi[F[A], F[B]] => F[Bi[A, B]]

В программировании чаще всего востребована перестановка с бифунктором-произведением:

infix type × = [A, B] => (A, B)

type Tupled[F[_]] = Swap2[×, F] // [A, B] => (F[A], F[B]) => F[(A, B)]

Для этого класса типов характерны такие методы расширений:

extension [F[_]: Tupled, A, B](fafb: (F[A], F[B]))
  def tupled = summon[Tupled[F]](fafb)
  
extension [F[_]: Tupled, A](fa: F[A])
  infix def zip[B](fb: F[B]) = (fa, fb).tupled

Метод zip как застёжка-молния сшивает пару последовательностей Seq[_] в одну последовательность пар. Иногда он встречается под другими названиями, например, IO.both в Cats.

Данные методы расширения не редко используются самостоятельно, но чаще его совмещают с функториальностью:

extension [F[_]: {Functor, Tupled}, A, B](fafb: (F[A], F[B]))
  def map2[C](abc: (A, B) => C): F[C] = fafb.tupled.map(abc.tupled)

В библиотеке Cats представлен метод mapN, работающий не только для пар, но для кортежей разных размеров. Только там этот метод требует вместо двух классов типов один Apply[F[_]], наследующий Functor[F[_]] и реализующий метод ap:

trait Apply[F[_]] extends cats.Functor[F]:
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B] // (ff, fa).map2(_ apply _)

Не сказал, бы, что на практике этот метод используется часто, но именно через него принято реализовать основные возможности, характерные для Tupled[F[_]]. Сам же ap считается ещё одним способом «преобразований в контейнере». Чтобы прочувствовать эту идею, просто сравните чуть изменённые сигнатуры функций:

  def map     [A, B]: (  A  =>   B ) => F[A] => F[B]
  def flatMap [A, B]: (  A  => F[B]) => F[A] => F[B]
  def ap      [A, B]: (F[A  =>   B]) => F[A] => F[B]
//def identity[A, B]: (F[A] => F[B]) => F[A] => F[B]

В то время, как flatMap отвечает за последовательное вычисление эффектов, когда следующий зависит от предыдущего, преобразование tupled обеспечивает независимое вычисление. С точки зрения математики, начало и окончание такого вычисления обоих эффектов вообще не привязано ко времени, но в программировании все вычисления проходят через узкое место — исполнитель, поэтому для обеспечения предсказуемости эффекты вычисляются в строгом порядке — сначала «левый», а потом «правый». Да, есть способы запускать вычисления и параллельно, но для этого используются хоть и похожие по сигнатуре, но уже другие возможности и это совсем другая история.

Следующий фрагмент кода демонстрирует различие последовательных и независимых вычислений:

import cats.effect.IO

val io1: IO[Unit] = IO.println("первый эффект!") >> IO.raiseError(Exception("Ошибка!"))
val io2: IO[Unit] = IO.println("второй эффект!")

val path1 = io1  >>  io2 // синоним flatMap { _ => ...}
val path2 = io1 both io2 // возможности Tupled

import cats.effect.unsafe.implicits.global

path1.attempt.unsafeRunSync()
println("-------------")
path2.attempt.unsafeRunSync()

// ВЫВОД В КОНСОЛЬ:
// первый эффект
// -------------
// первый эффект
// второй эффект

В первом случае второй эффект не сработает, так как для задействованного там метода flatMap не найдётся значения Unit внутри вычисленного IO[Unit] (потому что вместо Unit там альтернативный «несчастливый» результат — исключение). А во втором случае второй эффект срабатывает независимо от того, чем завершилось вычисление первого эффекта .

Так как метод Apply.ap отвечает за комбинирование эффектов, то по тем же причинам, что и для монад, вместе с ним очень полезно иметь под рукой и преобразование «запаковки» значений pure. Поэтому в Cats предоставлен также такой класс типов:

trait Applicative[F[_]] extends Apply[F]:
  def pure[A](a: A): F[A]

Это и называется аппликативным функтором в программировании — ковариантный эндофунктор Functor[F], обогащённый естественными преобразованиями pure: Id ~> F и tupled: × ∘ F ~> F ∘ ×.

Но разработчики scala-библиотек идут ещё дальше, и добавляют к Applicative, «разматрёшивание», называя всё это «монадой»:

trait Monad[F[_]] extends Applicative[F]:
  def flatten[A](ffa: F[F[A]]): F[A] // вообще-то, тут обычно flatMap, но это не принципиально

В итоге получается типичная scala-монада:

type TypicalScalaMonad[F[_]] = (
  lift:    Functor[F], // (A => B) => (F[A] => F[B])
  pure:    Pure   [F], //    Id ~> F
  flatten: Flatten[F], // F ∘ F ~> F
  tupled:  Tupled [F], // × ∘ F ~> F ∘ ×
)

Все остальные возможности реализуются через эти три естественные преобразования и функториальность.

Многим ФП-программистам не нравится, что к относительно простому устройству монады подмешиваются ещё возможности «аппликативного функтор». Притом, что такого понятия даже нет в теории категорий. Но всё же, данный подход считается наиболее оптимальным.

Комонада

Монада используется для «чистого разматрёшивания» посредством flatten таких эффектов, которые собираются из «эффективных» функций A => F[B], напрямую или косвенно использующих «запаковку» pure. Разматрёшивание обычно производится на лету, сразу после комбинирования эффектов, но иногда его полезно откладывать в самый конец. В этом помогает свободная монада — реализация Monad для свободного контейнера Free[F][_] (см. мой предыдущий обзор). Результатом композиции функций вида A => Free[F][B] будет сложная рекурсивная структура данных, которую в итоге нужно будет свернуть с помощью Monad[F].

И хотя техники программирования, основанные на «жадном» и «ленивом» «разматрёшивании» отличаются, концептуально они опираются на одну и ту же идею. Сперва вручную из элементов A => F[B] собирается структура данных со вложенными друг в друга F[_], которая (сразу или потом) сворачивается в единое эффективное действие. Просто во втором случае появляется промежуточное состояние — «программа-как-данные», значение рекурсивного типа. В первом же случае процесс порождения как бы уже содержит в себе финальную свёртку — он сразу «жадно» потребляет новую структуру, как только та усложняется, без промежуточного накопления рекурсивной программы.

Отсылка к рекурсии не случайна. Ведь монада является моноидом, который представляет собой ни что иное как инструмент для свёртки списка. И в данном случае исходный список составляют эффективные функции A => F[B].

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

Законы для комонады формулируются аналогично (дуально) монадным.

На Scala это можно записать так:

type Extract  [F[_]] = F ~> Id
type Coflatten[F[_]] = F ~> F ∘ F

type Comonad[F[_]] = (
  lift     : Functor [F],
  extract  : Extract [F]
  coflatten: Colatten[F],
)

extension [F[_]: Comonad as F, A](fa: F[A])
  def coflatMap[B](fab: F[A] => B): F[B] =
    (F.lift(fab) compose F.coflatten[A])(fa)

Преобразование coflatten согласуется с extract и lift.

«Заматрёшивание» надстраивает F[_] над существующей структурой, порождая более сложную конструкцию, чем была прежде. В то же время при извлечении доступна вся структура данных целиком, со всеми иерархическими вложениями F[_]. Поэтому комонады часто предоставляются для рекурсивных контейнеров, вроде непустого списка:

case class Nel[+A](head: A, tailOpt: Option[Nel[A]]): // nonempty list - непустой спиок
	def map[B](f: A => B): Nel[B] = Nel(f(head), tailOpt.map(_.map(f)))
	def extract = head
	def coflatten: Nel[Nel[A]] = Nel(this, tailOpt.map(_.coflatten))
	
	override def toString: String = "(" + head.toString + ")" + tailOpt.fold("")(", " + _.toString)
end Nel

val list = Nel(1, Some(Nel(2, Some(Nel(3, None)))))

println("непустой список: " + lst)           // (1), (2), (3)
println("его хвосты: "      + lst.coflatten) // ((1), (2), (3)), ((2), (3)), ((3))

Для деревьев «заматрёшивание» заменит все узлы исходного дерева на поддеревья, растущие из этого узла.

Но и для нерекурсивных контейнеров бывают полезны возможности комонады. Например:

type Writer[L] = [A] =>> L × A

given writerComonad: [L] => Comonad[Writer[L]] = (
  lift      = [A, B] => (f: A => B) => (wa: Writer[L][A]) => wa._1 -> f(wa._2),
  extract   = [A]    =>                (wa: Writer[L][A]) => wa._2,
  coflatten = [A]    =>                (wa: Writer[L][A]) => wa._1 -> wa,
)

val w : Writer[String][Int] =              "зависимость" -> 31
val ww: Writer[String][Int] =
  w.coflatMap(x => x._1.length + x._2)  // "зависимость" -> 42

Обратите внимание, мы снабдили комонадными возможностями контейнер Writer, для которого обычно предоставляют методы монады. Вот только с новыми возможности меняется и смысл контейнера! Если ранее он позволял манипулировать контекстом при преобразованиях его значений (например, добавлять записи в журнал), то теперь это скорее носитель зависимостей, необходимых для дальнейших преобразований!

Другие примеры использования комонад можно увидеть в моём предыдущем обзоре, где обсуждались схемы рекурсий.

Возможности комонады свойственны далеко не всем ковариантным конструкторам типов. Например, их не получится реализовать, если для некоторых значений F[A] не существует универсальной распаковки, как, например, для случаев None = Option[Nothing], или Nil = List[Nothing]. Обычно получается так, что если конструктору типов не подходит комонада, то стоит примерить к нему дуальные монадные возможности.

Дуализм понятий «монада» и «комонада» буквально означает, что для их эндофункторов существует взаимно-однозначное соответствие. Например, дуальными с такой позиции будут следующие конструкторы типов:

type State[S] = [A] =>> S =>> (S, A) // Reader[S] ∘ Writer[S]
type Store[S] = [A] =>> (S, S =>> A) // Writer[S] ∘ Reader[S]

Для State можно построить монаду, но вот распаковку Extract реализовать не получится. С другой стороны, мы всегда можем извлечь значение из Store и реализовать для него комонаду, но не понятно, как запаковать чистое значение посредством Pure. В этом конкретном случае заметна перестановка композиции составляющих контейнеров, но что если сами контейнеры будут простыми, а не композитными? Этот весьма нетривиальный вопрос мы разберём в следующей части обзора.

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

Дополнительная литература

• О монадах:

  • Из блога Бартоша Милевски:

    • Monads: Programmer’s Definition.

    • Monads and Effects.

  • Хабр-переводы иллюстрированных публикаций Адитьи Бхаргавы:

    • Функторы, аппликативные функторы и монады в картинках.

    • Тройка полезных монад.

  • Подборки ссылок:

    • Здесь хорошая подборка статей о монадах «лямбдамена» Филиппа Вадлера.

    • Ссылки на различные публикации о монадах с ресурса Scalabook.ru.

• Distributive law between monads статья о распределительном законе для монад в Википедии.

• О комонадах:

  • Комонада, она как монада, только комонада — статья на Хабре.

  • Comonads — глава книги Бартоша Милевски.

  • Comonad в докуементации библиотеки cats.

Промежуточный итог

Оказывается, что собрать из двух монад новую действительно не просто. Но нужно и помнить о более общей задаче, решить которую мы пытались композируя монады — автоматический вывод Monad[F] для абсолютно любого F[+_].

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

Но монады строятся лишь на ковариантных F[+_], которые, в свою очередь, могут быть композицией и контравариантных конструкторов типов, для которых не существует монад. То есть, даже если мы научимся композировать произвольные монады, это не решит более общую задачу.

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