Содержание третьей части:

• Свободный контейнер

• Более свободный контейнер

• Батуты

• Ко-свободный контейнер

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

Свободный контейнер

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

Неподвижная точка, принимая конструктор типов, возвращает простой тип – как бы «понижает арность». Если же «повысить арность» исходного контейнера, использовав его в выражении с дополнительным свободным параметром, то неподвижная точка как бы «восстановит арность», формируя тем самым преобразователь произвольного контейнерного типа в некий другой. Рассмотрим такой пример:

type CoEnv[E, F[_]] = [X] =>> E `Either` F[X]  // устоявшееся название

Конструктор типов CoEnv параметризирован помимо контейнерного F[_] ещё двумя простыми типами E и X. «Унарный» F[_] он превращает в «бинарный» ConEnv[_, F][_], неподвижной точной которого будет снова «унарный» контейнер:

type Free[F[_]] = [A] =>> μ[CoEnv[A, F]] // A + F[Free[F, A]]

Ввиду ковариантности F[_] и универсального свойства суммы типов, контейнер Free[F][_] можно представить в виде такой бесконечной суммы:

Не сложно убедиться, что рекурсивный контейнер Free[F][_] также является ковариантным:

given liftForCoenv[F[_]: Lift, A]: Lift[CoEnv[A, F]] =
  [X, Y] => (f: X => Y) => (fx: CoEnv[A, F][X]) => fx.map(_ map f)

def liftFreeAlg[F[_]: Lift, A, B](f: A => B): Algebra[CoEnv[A, F]][Free[F][B]] =
  _.left.map(f).pipe(inFix[μ, CoEnv[B, F]])
given liftForFree[F[_]: Lift]: Lift[Free[F]] = [A, B] => (f: A => B) =>
  foldFix[μ][CoEnv[A, F]](liftFreeAlg(f))

У нас есть два основных конструктора для Free:

def pureFree[F[_]: Lift] = [A] => ( a:           A  ) => inFix[μ, CoEnv[A, F]](Left ( a))
def bindFree[F[_]: Lift] = [A] => (fa: F[Free[F][A]]) => inFix[μ, CoEnv[A, F]](Right(fa))

Чистые значения можно «освободить» с помощью pureFree, а запакованные в F[_] – «поднять в свободный мир» посредством liftFree:

def liftFree[F[_]: Lift] = [A] => (fa: F[A]) => bindFree[F][A](fa map pureFree[F][A])

Распаковка свободного контейнера – это обычная свёртка:

def convertAlgebra[F[_]: Lift, A]: Algebra[F][A] => Algebra[CoEnv[A, F]][A] =
  alg => {_.fold(identity, alg)}

def goFree[F[_]: Lift, A]: Algebra[F][A] => Algebra[Free[F]][A] =
  convertAlgebra[F, A] andThen foldFix[μ][CoEnv[A, F]][A]

val freeVal: Free[Option][Int] = liftFree(Option(42))
goFree[Option, Int](_.get)(freeVal) // 42: Int

Самой же интересной возможностью Free[F] является «разматрёшивание» для любого ковариантного F[_]:

def flattenFree[F[_]: Lift, A]: Free[F][Free[F][A]] => Free[F][A] =
  foldFix[μ][CoEnv[Free[F][A], F]](_.fold(identity, bindFree[F][A]))

given freeMonad[F[_]: Lift]: Monad[Free[F]] = Monad[Free[F]](
  pure    = pureFree,
  flatten = [X] => (ffx: Free[F][Free[F][X]]) => flattenFree(ffx)
)

Таким образом, из «эффективных» функций вида A =>> F[B], всегда можно построить цепочку вычислений, даже если для F[_] не определено «разматрёшивание»! Достаточно на каждом шаге вычислений «поднимать» результат F[X] до Free[F][X], композировать вычисления, посредством liftFree и freeMonad (flatMap), в итоге получая результат Free[F][Result]. И только в самом конце, при распаковке, потребуется F-алгебра F[Result] =>> Result.

Более свободный контейнер

Для работы с контейнером Free[F][_] требуется доказательство ковариантности F[_], которое представляет собой реализацию метода map. Больше интересных возможностей даёт «более свободный» контейнер Freer[F][_] для которого ковариантность F[_] необязательна:

enum   Freer  [F[_], A]:
  case Pure   [F[_], A]   (a: A)                                   extends Freer[F, A]
  case Suspend[F[_], A]   (a: F[Freer[F, A]])                      extends Freer[F, A]
  case FlatMap[F[_], A, B](fb: Freer[F, B], afb: B => Freer[F, A]) extends Freer[F, A]

extension [F[_], A](ffa: Freer[F, A])
  def map    [B](f: A =>          B ): Freer[F, B] = Freer.FlatMap(ffa, f andThen Pure.apply)
  def flatMap[B](f: A => Freer[F, B]): Freer[F, B] = Freer.FlatMap(ffa, f                   )

Для композиции вычислений теперь вообще не требуются никакие возможности F[_]!

Представить Freer[F][_] в виде неподвижной точки какого-либо конструктора типов оказывается не так-то просто… Дело в том, что из-за FlatMap[F[_], A, B] этот контейнер представляет собой список преобразований, причём каждый элемент этого списка типизирован по-своему. Такой разнородный список относится к частному случаю зависимых типов, а эта тема выходит за рамки данной статьи.

Тем не менее, Freer[F][_] открывает замечательные возможности. С ним можно описать бизнес-эффекты как обобщённые алгебраические типы (GADT) вида SomeBuisenessEffect[_], и скомбинировать их посредством Freer, получая программу-как-данные – ту самую ленивую последовательность вычислений. Интерпретация такой программы производится в самом конце в любой удобный контейнер эффектов G[_], если для него предоставлены монадные возможности и «естественное преобразование» SomeBuisenessEffect ~> G:

extension [F[_], A](ffa: Freer[F, A])
  def foldMap[G[_]: Monad](interprete: F ~> G): G[A] = ffa match
    case Return(a)      => Monad[G].pure(a)
    case Suspend(ma)    => interprete(ma).flatMap(_ foldMap interprete)
    case FlatMap(fa, f) => fa.foldMap(interprete).flatMap(f(_) foldMap interprete)

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

«Более свободный» контейнер встречается, например, в библиотеках Cats и Scalaz в под именем Free. Построение на его основе программных продуктов требует перед исполнением (интерпретацией) «свободной» программы сперва собрать эту самую программу как некое значение. Этот «лишний шаг» влечёт не то чтобы большие, но системные издержки по производительности, поэтому такой подход используется редко. Но сама идея «ленивого списка преобразований» эксплуатируется достаточно часто, в том числе и для бесстековой обработки рекурсии, о которой расскажем далее.

Батуты

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

Первым примером послужит обобщённый контейнер TailRec из пакета TailCalls стандартной библиотеки Scala:

sealed abstract class TailRec[+A   ]{ ... }
protected case  class Call   [ A   ](rest: () => TailRec[A])            extends TailRec[A]
protected case  class Done   [ A   ](value: A)                          extends TailRec[A]
protected case  class Cont   [ A, B](a: TailRec[A], f: A => TailRec[B]) extends TailRec[B]

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

type TrampolineBase[A] = () => A // TrampolineBase[A] ≅ A¹ ≅ A
type Trampoline[A] = Freer[TrampolineBase, A]

«База» трамплина TrampolineBase[_] изоморфна тривиальному Id[A] = A, но отличается семантикой «ленивого вычисления». Это вычисление не обязательно вызывать сразу, его можно передать как аргумент в другую функцию и лишь там принять решение, запускать ли его, и сколько раз. Freer позволяет размещать список отложенных вычислений в куче, которая значительно больше чем стек. В дальнейшем этот список можно свернуть с помощью всё той же компиляторной оптимизации хвостовой рекурсии.

Трамплины удобны, в частности, для обслуживания косвенной рекурсии, которую компилятор не в состоянии оптимизировать автоматически. Вот пример использования TailRec:

import scala.util.control.TailCalls.*

val even: Int => TailRec[Boolean] =
  case 0 => done(true)
  case i => tailcall(odd(i - 1))

val odd: Int => TailRec[Boolean] =
  case 0 => done(false)
  case i => tailcall(even(i - 1))

even(1234567).result // true

При вычислении метода reult хвостовая рекурсия оптимизируется компилятором.

Чаще в качестве примера батута называют контейнер Eval[_] из библиотеки Cats. Он аналогичен TailRec, но дополнен эффектом «запоминания» (memoization), позволяющим вычислять «запакованное значение» лишь при первой распаковке контейнера, что нам сейчас не интересно в контексте изучения батутов. Вот как можно реализовать стекобезопасное вычисление чисел Фибоначчи посредством Eval:

def fib(n: Int, a: Long = 0, b: Long = 1): Eval[Long] =
  Eval.always(a + b)          // ленивое вычиление
    .flatMap { b2 =>          // аналог tailcall
      if (n > 0) fib(n - 1, b, b2)
      else       Eval.now(a)  // жадное вычисление константы))
    }

fib(10).value // 55

Может показаться, что вся магия оптимизации хвостовой рекурсии заключается здесь в наличии возможности flatMap. Но требуется не только наличие, но и «ленивость» конкретной реализации flatMap, которая, как правило, определяется структурой контейнерного типа.

Продемонстрируем это на примере такой функции:

import cats.Moand
import cats.syntax.all.*

def tailRecM[F[_]: Monad, A, B](f: A => F[Either[A, B]]): A => F[B]
  = (a: A) => f(a)
	.flatMap(_.fold(
	  tailRecM(f), // рекурсия
	  cats.Monad[F].pure
	))

Это типичный унаследованный от Haskell механизм реализации рекурсии с использованием монадических возможностей некого контейнера F[_]. Однако такая универсальная реализация подойдёт вовсе не для любого контейнера:

def evenBase: Int => Either[Int, Boolean] = 
  case        0   => true   .asRight
  case        1   => false  .asRight
  case        x   => (x - 2).asLeft

def evenId   = tailRecM[  Id, Int, Boolean](         evenBase   ) 
def evenEval = tailRecM[Eval, Int, Boolean](Eval now evenBase(_))

evenEval(1234567).value // false
evenId  (1234567)       // StackOverflowException

«Ленивый» Eval отрабатывает без проблем, тогда как «жадная» реализация flatMap для Id приводит к переполнению стека. Однако метод tailRecM из встроенной в Cats реализации класса типов Monad[Id] работает без ошибок:

Monad[Id].tailRecM(1234567)(evenBase) // false

Фокус в том, что tailRecM из cats.Monad[Id] реализован неуниверсально, а специфично для Id, через оптимизацию хвостовой рекурсии (и аннотацию @tailrec). Впрочем, в этой библиотеке аналогичным способом записаны tailRecM и для других стандартных контейнеров.

Стоит упомянуть ещё одну реализацию батута из библиотеки Cats.Effect – контейнер произвольных побочных эффектов IO. Секрет его универсальности как раз и заключается в том, что он по сути представляет собой рекурсивный свободный контейнер, «чисто» накапливающий в себе последовательность «эффективных преобразований». Контейнер IO[_] также аналогичен введённому ранее Trampoline[_], но дополнен многочисленными возможностями. В частности, в IO встроен механизм обработки ошибок, что делает его больше похожим на такой тип:

type IO[A] = Freer[[X] =>> () => Try[X], A]

Да, IO[_] – это самый настоящий свободный контейнер, который может быть интерпретирован в конце программы в любой другой: Id, Either, Future, ZIО… Его можно использовать в качестве батута по аналогии с Eval[_], обращаясь к методам flatMap и tailRecM, но пожалуй чаще всего в продуктовом коде используется метод foreverM:

extension [F[_]: Monad, A] (fa: F[A])
  def foreverM: F[Nothing] =
    Monad[F].tailRecM(())(_ => fa as Left(()))

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

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

• Зачем в Scala трамплины и как их использовать – статья на Habr;

• Tail Recursive Monads (FlatMap) – Юджин Йокота с его советам, как пасти котов;

• Taming Cats - Eval Филиппа Хози-Винчона укрощает тех же котов с помощью Eval;

• Stackless Scala With Free Monadspdf-статья Рунара Бьярнасона;

• Stack Safety for Free pdf-статья Фила Фримана.

Ко-свободный контейнер

Полезным оказывается тип, дуальный свободному контейнеру – ко-свободный контейнер. Дуальность проявляется в том, что вместо суммы типов теперь произведение, а вместо наименьшей неподвижной точки – наибольшая:

type CoFreeBase[F[_], A] = [X] =>> (A, F[X]) // A × F[X]
type Cofree[F[_]] = [A] =>> ?[CoFreeBase[F, A]]

Конструкция и деконструкция ко-свободного контейнера выполняется стандартными для неподвижных точек методами:

def unapplyCofree[F[_]: Lift, A] = outFix[?, CoFreeBase[F, A]]
def    pureCofree[F[_]: Lift, A] =  inFix[?, CoFreeBase[F, A]]

Деконструктор unapplyCofree разбирает Cofree на пару (A, F[Cofree[F][A]]). Соответственно, для создания экземпляра с помощью pureCofree потребуется, помимо значения A, другой ко-свободный контейнер, запакованный в F[_]. Это означает, что честно создать экземпляр возможно только в том случае, если для F[_] существует конструктор, не принимающий ни одного аргумента типа своего параметра; другими словами, если F[Nothing] ≠ Nothing. Типичным примером является Option с конструктором None. Это позволяет создавать типы деревьев и списков, которые могут быть пустыми (конечные структуры данных).

Дуально Free, ковариантность ко-свободного контейнера демонстрируется посредством развёртки – универсального свойства наибольшей неподвижной точки:

given liftCofreeBase[F[_]: Lift, X]: Lift[CoFreeBase[F, X]] = 
  [A, B] => (f: A => B) => ((current: X, previous: F[A]) => current -> previous.map(f)).tupled

def liftCofreeCoalg[F[_]: Lift, A, B](f: A => B): Coalgebra[CoFreeBase[F, B]][Cofree[F][A]] =
  unapplyCofree[F, A] andThen { (current, previous) => f(current) -> previous }

given liftForCofree[F[_]: Lift]: Lift[Cofree[F]] =
  [A, B] => (f: A => B) => unfoldFix[?][CoFreeBase[F, B]](liftCofreeCoalg(f))

В то время как свободный контейнер обладал замечательной возможностью «разматрёшивания», ко-свободный, наоборот, умеет «заматрёшиваться» (coFlatten), даже если этого не умеет F[_]:

given comonadCofree[F[_]: Lift]: Comonad[Cofree[F]] =
  def coflattenCoalg[A](cfa: Cofree[F][A]) = unapplyCofree(cfa).copy(_1 = cfa)
  Comonad(
    extract   = [A] => (cfa: Cofree[F][A]) => unapplyCofree(cfa)._1,
    coFlatten = [A] => (cfa: Cofree[F][A]) => unfoldFix[?][CoFreeBase[F, Cofree[F][A]]](coflattenCoalg[A])(cfa)
  )

Казалось бы, какая может быть польза от бесконечного роста? В следующей части данного обзора будет рассказано, как это свойство ко-свободного контейнера помогает «заглядывать в прошлое»!

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

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

• На практике полезнее бывает «более свободный» контейнер, который даёт те же возможности, но уже для произвольных конструкторов типов, чья ковариантность может быть и не доказана;

• Свободные контейнеры предоставляют решение проблемы переполнения стека в рекурсивных вычислениях.

• Продемонстрированы типичные примеры свободных контейнеров: типы TailRec, Eval, IO;

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