Категории типов. Часть 8.1. Вертикальная композиция эффектов

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

Обзор проблемы

Функторы в программировании ассоциируются с «эффектами»:

• «забывание» значений,

• отслеживание «несчастливого пути» вычислений,

• параллельное накопление дополнительных данных,

• зависимость от внешних данных,

• хранение множества значений (не детерминировано, какие из них потребуются при распаковке),

• а также различные комбинации перечисленного выше.

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

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

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

Чтобы этого добиться, нам нужно два контекста вычисления эффекта схлопнуть в один, причём такая операция обязана быть ассоциативной и «уважающей нейтральный контекст». Давайте рассмотрим, пожалуй, самый наглядный пример, когда контекст буквально хранится рядом со значениями — функтор . Тогда вложенный контейнер можно записать как . Очевидно, что чтобы получить предсказуемое «разматрёшивание», s обязан быть моноидом. Но если контекст не моноидален — монады не получится! Эта зависимость явно видна в известной монаде cats.Writer[S, A]. Не всякий функтор может стать монадой даже теоретически.

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

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

type Writer[S] = [A] =>> S × A  type M = Writer[String] ∘ List // [A] =>> (String, List[A])  def flatMap[A, B](fa: M[A])(f: A => M[B]): M[B] = {    val (log, list) = fa    val results = list.map(f) // List[(String, List[B])]    val combinedLog = results.foldLeft(log)(_ + _._1) // конкатенация не коммутативна!  val combinedValues = results.flatMap(_._2)    combinedLog -> combinedValues  }

def f(x: Int): M[Int] = (s" f($x) ", List(x * 10))  def g(y: Int): M[Int] = (s" g($y) ", List(y * 10))    val m = ("start", List(1, 2))    flatMap(flatMap(m)(     f  ))(g)  // ("start f(1)  f(2)  g(10)  g(20) ", List(100, 200))flatMap(m)(x => flatMap(f(x))(g)) // ("start f(1)  g(10)  f(2)  g(20) ", List(100, 200)) //               ↑↑↑↑↑↑↑↑↑↑↑

Монадные трансформеры

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

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

Для некоторых монад удаётся реализовать честный дистрибутивный закон с любой монадой . Вот как это работает для Option:

type OptionT[F[_]] = [A] =>> F[Option[A]]type Swap[F[_], G[_]] = (F ∘ G) ~> (G ∘ F) // дистрибутивное преобразованиеgiven optionMonad: Monad[Option] = (    fmap = [A, B] => (f: A => B) => (_: Option[A]).map(f),    pure = [A] => (a: A) => Some(a),    flatten = [A] => (ooa: Option[Option[A]]) => ooa.flatten,  )// дистрибутивный закон для Option с прочими монадамиgiven swapOptionT[F[_]: Monad as F]: Swap[Option, F] =    [A] => _.fold(F.pure(None))(F.fmap(optionMonad.pure[A]))

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

given composeMonads: [F[_]: Monad as F, G[_]: Monad as G] => ((swap: Swap[G, F]) ?=> Monad[F ∘ G]) = (    fmap = compFunctor[F, G],    pure = [A] => (a: A) => F.pure(G.pure(a)), // F.pure ∘ G.pure  flatten = [A] => (fgfga: F[G[F[G[A]]]]) => // (F.flatten ∘ G.flatten) ⋅ (id[F] ∘ swap ∘ id[G])    (F.fmap(G.flatten[A]) compose F.flatten[G[G[A]]] compose F.fmap(swap[G[A]]))(fgfga))

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

case class MonadTransformer[F[_]: Monad as F, G[_]: Monad as G, A](value: F[G[A]])(using swap: Swap[G, F]):    def flatMap[B](f: A => MonadTransformer[F, G, B]): MonadTransformer[F, G, B] =      MonadTransformer(value        .flatMap(F.fmap(G.flatten[B]) compose swap[G[B]] compose G.fmap(f andThen {_.value}))      )      def map[B](f: A => B): MonadTransformer[F, G, B] =      flatMap(f `andThen` G.pure[B] `andThen` F.pure[G[B]] `andThen` MonadTransformer.apply) end MonadTransformer  type MonadT[G[_]] = [F[_]] =>> [A] =>> MonadTransformer[F, G, A]

type OptionT = MonadT[Option]

// наша реализация монады для «кошачьего» IOgiven ioMonad: Monad[IO] = (    fmap = [A, B] => (f: A => B) => (_: IO[A]).map(f),    pure = [A] => (a: A) => IO.pure(a), //.pure(a),    flatten = [A] => (iia: IO[IO[A]]) => iia.flatten,  )  val findUserId:   UserName => OptionT[IO][UserId]      = _ => MonadTransformer(IO.pure(Some(42)))  val findCustomer: UserId   => OptionT[IO][Customer]    = _ => MonadTransformer(IO.pure(Some("кустомер")))  val findPhone:    Customer => OptionT[IO][PhoneNumber] = _ => MonadTransformer(IO.pure(Some("03")))val userPhone =    for      userId   <- findUserId("Юзверь")      customer <- findCustomer(userId)      phone    <- findPhone(customer)    yield phoneuserPhone.value.unsafeRunSync() // Some(03)

В пакете cats.data представлены такие трансформеры:

• OptionT,

• EitherT,

• ReaderT,

• WriterT,

• StateT и некоторые его обобщения.

Библиотека Scalaz предлагает также трансформер ListT, вот только он нарушает законы монады. Оказывается, что для List теоретически невозможно реализовать честное дистрибутивное преобразование, поэтому авторы Cats вообще решили не связываться с ним.

Вертикальная композиция эффектов посредством монадных трансформеров приводит к монструозным контейнерам вида

type TotalEffect[A] = ReaderT[EitherT[StateT[IO, S, *], E, *], R, A]

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

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

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

Свой компромисс предлагает библиотека ZIO — её одноимённый контейнер можно интерпретировать как трансформированный ленивый контейнер асинхронных эффектов IO:

// (ReaderT[R] ∘ EitherT[E] ∘ IO)[A] ≅ R => IO[E `Either` A]type ZIO[R, E, A] = ReaderT[EitherT[IO, E, *], R, A]

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

Distributive

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

type Distributive[G[_]] = [F[_], A] => (F ∘ G)[A] => (G ∘ F)[A] // (F ∘ G) ~> (G ∘ F)// или swap))def flip[F[_]: Functor, G[_]: Distributive as distribute]: (F ∘ G) ~> (G ∘ F) = [A] => distribute(_)extension [F[_], G[_]: Distributive as swap, A](fga: F[G[A]])    def cosequence: G[F[A]] = swap(fga)    extension [F[_]: Functor, A](fa: F[A])    def distribute[G[_]: Distributive, B](agb: A => G[B]): G[F[B]] = fa.map(agb).cosequence

Самой важной дистрибутивной монадой является Читатель:

type Reader[R] = [A] =>> R => Agiven distributiveReader: [R] => Distributive[Reader[R]] =    [F[_]: Functor, A] => (fga: F[Reader[R][A]]) => r => fga.map(_(r))

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

case class DistributiveT[F[_]: {Monad, Distributive}, G[_]: Monad, A](value: (F ∘ G)[A])  type DistrT[F[_], G[_]] = [A] =>> DistributiveT[F, G, A]    given distrTMonad: [F[_]: {Monad as F, Distributive}, G[_]: Monad as G] => Monad[DistrT[F, G]] = (    fmap = [A, B] => (f: A => B) => (fga: DistrT[F, G][A]) => DistributiveT(compFunctor[F, G](f)(fga.value)),    pure = [A] => (a: A) => DistributiveT(F.pure(G.pure(a))),    flatten = [A] => (fgfga: DistrT[F, G][DistrT[F, G][A]]) => DistributiveT(    (F.fmap(G.flatten[A]) compose F.flatten[G[G[A]]] compose F.fmap(flip[G, F][G[A]]))(        fmap[F ∘ G]((_: DistrT[F, G][A]).value)(fgfga.value)     )  // здесь задействуется distributiveReader, определённый ранее  )  )

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

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

Это позволяет определить класс представимых контейнеров RepresentableR следующим образом:

infix type ≅≅[F[_], G[_]] = ( // изоморфизм контейнеров  right: F ~> G,    left : G ~> F  )  type RepresentableR[R] = [G[_]] =>> G ≅≅ Reader[R]def tabulate[R, G[_]: RepresentableR[R] as rep]: Reader[R] ~> G = rep.left    extension [R, G[_]: RepresentableR[R] as rep, A](ga: G[A])    def index: R => A = rep.right(ga)

Тип-параметр R «представляет» весь контейнер — его значения являются своеобразными индексами расположения хранимых значений. Функция tabulate создаёт экземпляр контейнера из табличного представления, которое задаёт значения для каждого индекса. В свою очередь, index извлекает из контейнера значение по ключу типа R.

Используя лемму Йонеды, выводим, что представляющий объект всегда можно выразить в виде параметризованной совокупности всех «распаковок» функтора:

Это не что иное как естественное преобразование «распаковки»:

type Rep[G[_]] = G ~> Id // представитель контейнера  type Representable[G[_]] = RepresentableR[Rep[G]][G]

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

Давайте запишем дистрибутивный закон представимого функтора в виде композиции естественных преобразований. Воспользуемся небольшой оптимизацией горизонтальной композиции over для частного случая тождественного преобразования:

extension[F1[_], F2[_]] (α: F1 ~> F2) // не требует функториальности F2 !!    def over[G[_]]: (F1 ∘ G) ~> (F2 ∘ G) = [A] => α(_) // α ∘ id[G]  given distributiveFromRepresentable: [R, G[_]: RepresentableR[R] as rep] => Distributive[G] =    [F[_]: Functor, A] =>      (tabulate.over[F] ⋅ flip[F, Reader[R]] ⋅ (id[F] ∘ rep.right))(_)

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

type Pair[A] = A × Agiven representablePair: Representable[Pair] = (    right = [A] => (pair: Pair[A]) => (_: Rep[Pair])(pair),    left  = [A] => (rr: Reader[Rep[Pair]][A]) => rr([B] => _._1) -> rr([B] => _._2)  )

Канонический «представитель» пары, преобразование Rep[Pair], изоморфен типу Boolean, допускающему лишь два значения — индексы позиций в кортеже. Значит, можно записать альтернативное представление:

val repPairIso: Rep[Pair] ≅ Boolean = ( // просто доказательство, для справки  right = _(true -> false),    left  = b => [A] => pair => if b then pair._1 else pair._2  )given representableRPair: RepresentableR[Boolean][Pair] = (    right = [A] => (pair: Pair[A]) => (b: Boolean) => if b then pair._1 else pair._2,    left  = [A] => (rr: Reader[Boolean][A]) => rr(true) -> rr(false)  )

Этого достаточно, чтобы производить вычисления в композитных контейнерах на основе монады Pair.

given pairMonad: Monad[Pair] = (    fmap    = [A, B] => (f: A => B) => (p: Pair[A]) => f(p._1) -> f(p._2),    pure    = [A] => (a: A) => a -> a,    flatten = [A] => (ppa: Pair[Pair[A]]) => ppa._1._1 -> ppa._2._2  )val optPair = DistributiveT[Pair, Option, Int](Some(1) -> Some(2))  def modifyInOptionsPair(i: Int) = DistributiveT[Pair, Option, Int](Some(i * 100) -> Some(i + 40))optPair.flatMap(modifyInOptionsPair)// DistributiveT((Some(100),Some(42)))

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

enum Nat: // натуральные числа  case Z    case S(prev: Nat)    case class Stream[A](value: A, cons: () => Stream[A]):    def map[B](f: A => B): Stream[B] =      Stream(f(value), () => cons().map(f))      def index: Nat => A =      case Nat.Z    => value      case Nat.S(p) => cons().index(p)  end Stream  def nats: Stream[Nat] = Stream(Nat.Z, () => nats.map(n => Nat.S(n)))    // канонический представитель изоморфен натуральным числамval repStreamIso: Rep[Stream] ≅ Nat = (  right = _(nats),    left  = n => [_] => _.index(n)  )  end repStreamIso    val stream =  Stream(4,  // 0 ≅     Z        () => Stream(2,  // 1 ≅   S(Z)        () => Stream(42, // 2 ≅ S(S(Z))        () => ???)))    import Nat.*  val two = S(S(Z))stream.index(two) // 42

Traversable

Класс типов Distributive отвечает за «вытаскивание» определённого вложенного контейнера наружу композиции с любым другим контейнером. К такому классу относятся лишь представимые функторы. Что же можно сказать про функторы, которые, наоборот, можно «вложить» в любой другой?

Итак, нам нужна конструкция такого вида:

type Codistributive[F[_]] = [G[_], A] => (F ∘ G)[A] => (G ∘ F)[A] // Swap[F, G]def flap[F[_]: Codistributive as codistributive, G[_]: Applicative]: (F ∘ G) ~> (G ∘ F) =  [A] => codistributive(_)    extension [F[_]: Codistributive as codistributive, G[_]: Applicative, A](fga: F[G[A]])    def sequence: G[F[A]] = codistributive(fga)

Очень похоже на Distributive, но не сводится к нему, так как теперь определяется класс для уже «внешнего» контейнера F[_].

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

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

В категории типов каждое слагаемое этого ряда представляет собой фиксированный список из n элементов типа a. Действительно, как уже говорилось ранее, для полиномиальных коллекций всегда можно выбрать способ «пробежаться» (traverse) по ним. Коллекции можно декомпозировать на форму и значения:

type ShapedCollection[F[_]] = [A] =>> (shape: F[Unit], values: List[A])    type Listable[F[_]] = ( // это не изоморфизм!    decompose: F ~> ShapedCollection[F],    recompose: ShapedCollection[F] ~> F,  )

Класс типов Listable[F[_]] похож на изоморфизм, но не является им. С одной стороны, мы должны удовлетворить условию recompose ∘ decompose = id[F], но вот обратная композиция не даст тождества: decompose ∘ recompose ≠ id[ShapedCollection[F]]. Дело в том, что такая ShapedCollection[F] гораздо больше исходной F — в идеале мы должны были гарантировать одинаковый размер формы и списка значений, но сейчас мы не будем в это углубляться.

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

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

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

Класс типов аппликативного функтора собирается так:

type Applicative[F[_]] = (    fmap:  Functor[F],    tupled: Tupled[F],    pure:     Pure[F],  )  def fmap2[F[_]: Applicative as F, A, B, C](abc: (A, B) => C): ((F[A], F[B])) => F[C] =    F.tupled(_, _).map(abc.tupled)    extension [F[_]: Applicative as F, A, B](fafb: (F[A], F[B]))    def map2[C](abc: (A, B) => C): F[C] = fmap2(abc)(fafb)

given applicative: [F[_]] => (Functor[F] ?=> Pure[F] ?=> Tupled[F] ?=> Applicative[F]) = (  fmap   = summon[Functor[F]],    tupled = summon[ Tupled[F]],    pure   = summon[   Pure[F]]  )given functorFromApplicative: [F[_]: Applicative as F] => Functor[F] = F.fmapgiven applicativeFromMonad: [F[_]: Monad as F] => Applicative[F] = (    fmap   = F.fmap,    tupled = [A, B] => (fafb: (F[A], F[B])) => fafb._1.flatMap(a => fafb._2.map(a -> _)),    pure   = F.pure  )

Если контейнер представим в виде списка, то дистрибутивный закон для него реализуется так:

given codistributive: [F[_]: Listable as listable] => Codistributive[F] =    [G[_]: Applicative as G, A] => (fga: (F ∘ G)[A]) =>      val (shape, listGA) = listable.decompose(fga)  // (F[Unit], List[G[A]])      listGA        .foldRight[G[List[A]]](G.pure(Nil))((ga, la) => G.tupled(ga, la).map(_ +: _))        .map(listable.recompose(shape, _))

В библиотеке Cats за те же возможности отвечает класс типов Traverse.

Теперь мы можем реализовать монадный трансоформер:

case class TraversableT[F[_]: Monad, G[_]: {Monad, Codistributive}, A](value: (F ∘ G)[A])    type TravT[F[_], G[_]] = [A] =>> TraversableT[F, G, A]    given travTMonad: [F[_]: {Monad as F}, G[_]: {Monad as G, Codistributive}] => Monad[TravT[F, G]] = (    fmap = [A, B] => (f: A => B) => (fga: TravT[F, G][A]) => TraversableT(compFunctor[F, G](f)(fga.value)),    pure = [A] => (a: A) => TraversableT(F.pure(G.pure(a))),    flatten = [A] => (fgfga: TravT[F, G][TravT[F, G][A]]) => TraversableT(      (F.fmap(G.flatten[A]) compose F.flatten[G[G[A]]] compose F.fmap(flap[G, F][G[A]]))(        fmap[F ∘ G]((_: TravT[F, G][A]).value)(fgfga.value)      )    )  )

Монада обладает возможностями аппликативного функтора, что позволяет не указывать Applicative в сигнатуре travTMonad. Так что получается трансформер, отличающийся от distrTMonad лишь тем, что (ко)дистрибутивное преобразование присуще уже внутреннему контейнеру, а не внешнему.

type ReaderOfOptions = TravT[Reader[String], Option] // Reader[String] ∘ Option  given readerMonad: [R] => Monad[Reader[R]] = (    fmap = [A, B] => (f: A => B) => (ra: Reader[R][A]) => f `compose` ra,    pure = [A] => (a: A) => (_: R) => a,    flatten = [A] => (rra: Reader[R][Reader[R][A]]) => (r: R) => rra(r)(r)  )  given listableOption: Listable[Option] = (    decompose = [A] => (oa: Option[A]) => oa.map(_ => ()) -> oa.toList,    recompose = [A] => (sa: ShapedCollection[Option][A]) => sa.values.headOption, // форма тут не понадобилась  )  val optReader = TraversableT[Reader[String], Option, Int](_.toIntOption)  def modifyInOptionsReader(i: Int) =    TraversableT[Reader[String], Option, Int](str => Option.unless(str.isBlank)(i))optReader.flatMap(modifyInOptionsReader).value("42")// Some(42)

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

• Композиция монад

  • Публикации в научных журналах

    • Combining Monads оригинальная статья 1992 года Дэвида Кинга и Филипа Уодлера

    • Composing monads статья 1993 года Марка Джонса и Люка Дюпоншела

    • Applicative programming with effects статья 2005 года Конора Макбрайда и Росса Патерсона

  • Вопросы со Stack Overflow:

    • Why do monads not compose in scala .

    • Applicatives compose, monads don’t

• Distributive

  • Distributive law between monads Wikipedia

  • Representable Functors пост Сиау Янга в его блоге

  • Every Distributive is Representable пост Дэниела Млота в его блоге

  • What is Representable used for in Haskell? Stack Overflow

  • Representable Functors пост в Кафе программирования Бартоша Милевски

• Traversable

  • Scalabook.ru/Traverse

  • Cats.Traverse

  • Грокаем Traversable Хабр-перевод статьи Мэтта Торнтона про F#

  • Haskell/Traversable

  • I struggle to understand Traversable (Haskell)

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

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

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

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

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

Зато свободные монады полезны при горизонтальной композиции эффектов — эту тему мы раскроем в следующей части обзора.