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

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

• Часть 1

  • Обобщённые типы

  • Конструкторы типов

  • Полиморфные типы

  • Типы высокого рода

• Часть 2 (данная публикация)

  • Классы типов

  • Типы-контейнеры

• Часть 3

  • Контейнеры как фундамент для разработки

  • Подкатегории типов (вместо заключения)

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

• Классы типов

  • Это не типы классов!

  • Экзистенциальные типы

  • Специальный полиморфизм

  • Классы типов в Scala

  • Моноид

  • Эксперименты с ООП

• Типы-контейнеры

  • Идея обобщённого контейнера

  • Классы типов для контейнеров

  • Эффекты

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

Классы типов

Это не типы классов!

Если “типы классов” – это, буквально, типы, ассоциированные с классами, то перестановка слов обладает совершенно иной семантикой. Давайте разберёмся, какой смысл имеет словосочетание “классы типов”.

Рассмотрим такой код:

case class Context[A](meta: String)  
def enrichWithMeta[A](a: A, context: Context[A]) = (a, context.meta)  
//                (1)   (?)            (2)  (3)  

val contextForInt = Context[Int]("целые числа")  
enrichWithMeta[Int](42, contextForInt) // (42, "целые числа")

Нет, никакой особой магии тут искать не нужно, сейчас важна лишь определённая трактовка элементов этого кода. Обобщённый метод enrichWithMeta параметризирован неким типом A, и в качестве одного из аргументов принимает значение Context[A], то есть, обобщённого типа, параметризированного тем же типом-параметром A. Ключевой вопрос тут – какие типы можно использовать при вызове метода enrichWithMeta? С первого взгляда кажется очевидным, что универсальный полиморфизм позволяет использовать любой тип в качестве параметра.

Однако, если рассматривать аргумент context: Context[A] как вспомогательный (в любом смысле!), то правильным может стать и такой ответ: при вызове метода enrichWithMeta можно использовать не любые типы, а только те SomeType, для которых существует значение типа Context[SomeType] (с тем, чтобы его передать в метод, как аргумент). Если же значение типа Context[SomeType] не доступно, то вызвать метод enrichWithMeta не получится.

Таким образом, само требование предоставления значения обобщённого типа, конкретизированного типом-параметром метода, накладывает ограничения на этот тип-параметр. Причём, важен не значение аргумента метода, а только его тип, связанные с ним возможности-функции. Более того, так как тип-параметр может быть любой, то за ограничение отвечает не простой тип Context[A], а конструктор типов Context. Во фрагменте кода выше ключевые моменты отмечены цифрами: тип-параметр метода (1), тип аргумента метода, полученный применением конструктора типа (2) к типу-параметру метода (3). Про это будет сказано далее, но пока предлагаю задуматься, можно ли считать схожим ограничением тип первого аргумента (?)?

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

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

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

Выше приведён пример очень простого обобщённого класса Context[A], предоставляющего единственный проектор типа String, и совсем не использующий параметр A. Ближе к концу раздела будут рассмотренные более полезные примеры классов типов, предоставляющие различные функции, задействующие тип-параметр. Пример Context[A] призван подчеркнуть, что классы типов могут быть описаны любыми обитаемыми обобщёнными типами.

Также далее будет рассказано, что именно предлагает Scala для работы с классами типов, но сперва стоит обратить внимание на использованную формулировку ограничения на тип-параметр enrichWithMeta[A]: существуют такие типы A, для которых доступно значение Context[A]. Такого рода логические утверждения при переносе в теорию типов соответствуют понятию “экзистенциальные типы”.

Экзистенциальные типы

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

def getLenght(l: List[_]) = l.lenght
//               ↑↑↑↑↑↑↑ вполне себе коррекное выражение в Scala

Тип элементов списка не важен, если нам требуется только его длинна. Однако, само существование такого типа предполагается, так как список элементов без типа попросту не возможен. Scala также позволяет указывать ограничения для неизвестного типа параметра, впрочем, ввиду ковариантности List, выражение l: List[_ <: SomeType] можно переписать проще: l: List[SomeType]. Но случается, что столь широкое ограничение на параметр конструктора типов оказывается не тем, что нужно. Давайте лучше попробуем подойти к экзистенциальным типам от универсальных, воспользовавшись их дуальностью.

Рассмотрим выражение A Either String, определяющее сумму типов A и String. Здесь A – свободная переменная, и для использования выражения эту переменную нужно связать каким-либо квантором. Ранее для мы пользовались только квантором (или аналогичным ), который можно читать как "для любого":

//   OrStringA = λA.     A   +    String
type OrStringA = [A] =>> A Either String

"Для любого типа A есть тип-сумма A и String".

Дуальным к утверждению "для любого A" является утверждение "существует такой A, что". В математике, в том числе и в теории типов, для таких случаев используется квантор (exists). Если этот квантор использовать с выражением из примера выше, то получится такой тип: .

Дуальность кванторов

Дуальность кванторов и в логике проявляется по отношению к отрицанию:

• утверждение “не для любого A верно B” равносильно “существует такое A, что не верно B”;

• утверждение “не существует такого A, что верно B” равносильно “для любого A не верно B”.

Что может быть значением такого типа? При трактовке типов как утверждений (изоморфизм Карри-Ховарда) доказательством корректности определения типа является его обитаемость, свидетельством которой является предоставление любого "значения" этого типа. Для полиморфного типа его "реализацией" является определение [A] =>> A Either String, отражающее "функциональный" характер квантора ("для любого") – при использовании этого типа мы сами должны предоставить простой тип, чтобы подстановкой его вместо A был построен новый тип. В случае типа некий простой тип уже должен быть предоставлен в качестве свидетельства его существования, и вместе с ним значение выражения типа, в котором свободный параметр заменён на "тот самый" тип (в нашем случае, Int Either String. То есть, в итоге получаем такой экзистенциальный тип:

trait OrStringE:
  type A
  val value: A Either String

Если универсальный тип OrStringA представлял собой функцию от любого типа A в тип значения, представленный выражением, то экзистенциальный тип OrStringE описывает пару из некого типа A и значения типа, представленного выражением. Ввиду этого, иногда используют альтернативное обозначение для экзистенциальных типов в виде пары , где ExprA – некое выражение, например, A Either Strig. Первый элемент такой пары называют скрытым типом-свидетелем, в том смысле, что его наличие нужно лишь чтобы “засвидетельствовать” существование подходящего типа. При использовании значений экзистенциального типа зачатую требуется обрабатывать не только само значение выражения, но и как-то учесть тип-свидетель.

Трейт OrStringE демонстрирует механизм зависимых (от пути) типов в Scala. Такие типы реализуют механизм позднего связывания, когда тип значения проверяется динамически, во время выполнения с использованием мета-информации, на которую ссылается это значение. На этапе компиляции не получится выяснить, какого типа будет выражение (a: OrStringE).value.

Но, учитывая, что элемент экзистенциального типа представляет собой пару из типа и значения, то можно применить кодирование по Чёрчу, допускающее статическую типизацию (раннее связывание). В случае обычного произведения типов кодирование Чёрча даёт . Соответственно, для экзистенциального типа, построенного на выражении Expr, получается такое альтернативное представление:

На Scala можно таким образом записать универсальный и экзистенциальный типы, построенные на одном и том же выражении Expr:

type Universal   = [Expr[_]] =>> [X] =>> Expr[X] // Universal[F] ≡ F
type Existential = [Expr[_]] =>> [Y] => ([X] => Expr[X] => Y) => Y

type ListU = [A] =>> Universal[List][A] // List[A]
type ListE = Existential[List] // [Y] => ([X] => List[X] => Y) => Y

val listUInt: ListU[Int] = List(4, 2)
val listEInt: ListE = // {*Int, List[Int]}: {∃X, List[X]}
	[Y] => (continuation: [X] => List[X] => Y) => continuation(listUInt)

listEInt[String]([X] => (_: List[X]).mkString("; ")) // "4; 2"

В коде Scala хорошо видны все “стрелочки” кодировки Чёрча. В таком представлении экзистенциальный тип представляет собой полиморфную функцию, принимающую в качестве аргумента другую полиморфную функцию-продолжение continuation. В определении значения listEInt этого типа в функцию-продолжение передаётся значение listUInt простого типа, полученного подстановкой в тип-выражение List[_] конкретного типа Int. Факт существования “подходящего” типа Int спрятан в использовании переменной listUInt: List[Int], в то время как результирующий тип переменной listEInt уже не содержит упоминания скрытого типа-свидетеля. Такое сокрытие осуществляется с помощью универсальной квантификации обобщённой функции continuation – если пользователь хочет обработать значение некого неизвестного типа, то он должен предоставить инструмент для работы с любыми типами.

Наконец, безотносительно кодировки Чёрча, универсальные типы сами по себе могут описывать “экзистентность” типов:

trait Number[A]:
  def zero: A
  def one: A
  def sum(x: A, y: A): A
  def mul(x: A, y: A): A

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

val boolAsNumber = new Number[Boolean]:
  def zero = false
  def one = true
  def sum = _ || _
  def mul = _ && _

Совокупность доступных значений типа Number[A] определяет те типы, для которых доступны возможности, описанные трейте. Таким образом, универсальный тип трактуется, как описание экзистенциального типа . При этом сам конструктор типов Number[A] при такой трактовке описывает класс типов.

В статье Бартоша Милевски Parametricity: Money for Nothing and Theorems for Free говорится о преимуществах использования универсальных типов (см. также оригинальную статью лямбда-мена Филиппа Водлера Theorems for free!). Но дуальные экзистенциальные типы, в свою очередь, не могут похвастать аналогичными свойствами – использование типов аналогичных представленному выше трейту OrStringE оказывается неудобным (требуют динамической валидации “существующего” типа во время выполнения). Поэтому ищутся различные способы избавится от явной экзистенциальности, свести её к универсальным типам. В математической логике такой стандартный алгоритм превращения экзистенциальных высказываний в универсальные известен под названием “сколемизация“.

Устаревший синтаксис Scala

В Scala 2 существовал специальный синтаксис для экзистенциальных типов (см. также Existential Types in Scala):
type F = SomeClass[A] forSome { type A }
Позднее такой синтаксис решили упразднить, ссылаясь на сложности поддержки компилятором и на то, что схожих результатов можно добиться с помощью других синтаксических конструкций.

Специальный полиморфизм

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

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

def add(a: Int,    b: Int)    = a + b      // перегрузка для Int
def add(a: String, b: String) = a concat b // перегрузка для String

add( 4,   2 )    // 6
add("4", "2")    // "42"
add(true, false) // ОШИБКА!!! Для Boolean нет перегрузки add

В трёх последних строках используется одно и то же имя функции add для значений разных типов, но при компиляции в последней строчке будет ошибка, так как существуют реализации add только для аргументов типа Int и String, но не для Boolean, или каких-либо других типов. На этом примере видно, почему такой полиморфизм называется специальным – он работает только для специально описанных случаев (также говорят ad hoc полиморфизм от латинской фразы “ad hoc” – “для данного случая”).

Другая разновидность специального полиморфизма – это полиморфизм приведения (не путать с ?!). Имеется в виду возможность создания пользовательских функций неявного приведения типов, существующая в разных языках программирования. В Scala 3 неявные преобразования рекомендуется реализовывать посредством предоставления неявных значений обобщённого типа Conversion:

given Conversion[Int,     String] = _.toString
given Conversion[Boolean, String] = _.toString

def palindrome(str: String) = str concat str.reverse

palindrome(42)    // "4224"
palindrome(true)  // "trueeurt"
palindrome(4.2)   // ОШИБКА! значения Double нельзя туда, где нужен String

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

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

trait Base  { def method(): Int }
class Child { def method() = 42; val i = 0 } // Нет наследования,
given Conversion[Child, Base] = child =>     // но есть неявное приведение!
  new Base { def method() = child.method() }

val child = new Child
def getInt(producer: Base) = producer.method()
getInt(child) // полиморфизм приведения!

То, что в случае отсутствия наследования при приведении типов приходится создавать в памяти новый экземпляр, не существенно, так как сейчас мы рассматриваем только верхнеуровневую семантику, не заморачиваясь с оптимизацией. Ещё одним отличием от наследования является то, что экземпляр Base “не помнит” о первоначальном типе Child. Это не позволит выполнить принудительное обратное приведение типов (например, при сопоставлении с шаблонами), как это работало с наследованием, и восстановить значение поля i.

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

В приведённых выше фрагментах кода при объявлении неявных преобразований используется ключевое слово given. С помощью этого слова в контекст добавляются неявные значения определённого типа, но это лишь малый элемент очень мощного механизма языка Scala, называемого “контекстные абстракции” (тут подробнее). Этот механизм уже реализован в языках “доказательства теорем”, вроде Coq или Agda, но и во некоторых популярных языках появляются предложения реализовать что-то похожее. Под “контекстом” в общем случае подразумевается область видимости в которой доступны некоторые объявленные ранее типы, функции и значения, а ключевой особенностью является возможность вывода термов – когда компилятор сам ищет значения нужного типа (например, неявные преобразования, как было выше). И, кстати, это ещё один способ путешествия из вселенной типов во вселенную значений ?.

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

def palindromeDouble(dob: Double)(using dobToStr: Conversion[Double, String]) =
    palindrome(dobToStr(dob))

given Conversion[Double, String] = _.toString // Это значение
palindromeDouble(4.2) // "4.22.4"             // сюда передаяётся неявно!

Здесь palindromeDouble принимает аргумент типа Double, а далее указан ещё один параметр с использованием ключевого слова using. Это позволяет не передавать в функцию значение типа Conversion[Double, String] явно – компилятор сам найдёт в контексте нужное значение и передаст в функцию, но только если значение этого типа существует в контексте, было помещено туда специально.

implicit vs given/using

В Scala 2 для работы с контекстом было только одно ключевое слово implicit, “неявно”. Оно использовалось и при объявлении неявных значений (методов/классов/объектов), и с аргументами метода, которые должны передаваться неявно. В Scala 3 сочли более идеоматичным использование двух ключевых слов given и using, но в актуальной версии “старый стиль” по-прежнему поддерживается.

Конечно же, не обязательно перед каждым использованием неявных значений требуется явно прописывать необходимые given. Их можно, например, импортировать из других пакетов, или пробрасывать внутрь метода с помощью using. Алгоритм поиска неявных значений хорошо раскрывается в этом ответе на вопрос Where does Scala look for implicits?.

Ремарка о логическом программировании

Вывод термов является одной из основ логического программирования. Компилятор, видя что из значения одного типа нужно получить значение другого, сам ищет способ достичь этого на основе встроенных и пользовательских правил (неявных значений в контексте). Аналогичным образом в логическом программировании строится вся цепочка вывода искомого результата на основе заданных правил. У Бартоша Милевски есть хорошие публикация в его блоге под общим названием Logic Programming in Scala: часть 1, часть 2.

Дополнительные материалы по работе с контекстными абстракциями в Scala:

• хабр-статья Implicits в Scala — неявные методы, функции, значения и особенности;

• ещё одна хабр-статья Как использовать implicit'ы в Scala и сохранить рассудок;

• статья у Юджина Баелдунга: Scala 3 Implicit Redesign;

• видео-обзор Scala Implicits Revisited от автора Scala Мартина Одерски.

Классы типов в Scala

Перепишем пример из начала обсуждения классов типов используя контекстные абстракции:

case class Context[A](meta: String)  
def enrichWithMeta[A](a: A)(using context: Context[A]) = (a, context.meta)  

given Context[Int]("целые числа")  

enrichWithMeta(4)   // (4, "целые числа")
enrichWithMeta("2") // Ошибка компиляции!

При вызове обобщённого метода enrichWithMeta требуется только один аргумент – значение, которое нужно “обогатить” строчкой. Но, не смотря на универсальную квантификацию метода, его использование ограничено только теми типами, для которых в текущем контексте существуют неявные значения обобщённого типа Context[_].

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

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

type Id = [A] =>> A
def enrichWithMeta[A: Context: Id] = (summon[A], summon[Context].meta)
//                  ↑↑↑↑↑↑↑↑↑↑↑↑↑	- "границы контекста"
given Int = 42 // Id[Int]
enrichWithMeta // (42, "целые числа")

При такой записи явно подчёркивается, что “любой” тип A на самом деле ограничен наличием в контексте вызова экземпляров типов Context[A] и Id[A] = A. Так же здесь виден утвердительный ответ на вопрос, заданный в начале раздела – “можно ли считать значение a: A ограничением, накладываемым на тип A?“ При этом Id[A] = A

Встроенный в язык метод summon[_] позволяет “призвать” значение нужного типа, неявно размещённое в контексте, ведь имя неявного значения здесь нигде не указывается. Впрочем, на практике призывы обычно выносятся в инструментальный код, определяющий язык предметной области (DSL), на котором будет описана вся бизнес-логика.

Обобщённые типы как типы типов?

Ещё один очень любопытный момент. В коде A: Context обобщённый тип Context вида ⋆ → ⋆ выступает в роли типа для A просто вида ⋆! В этом смысле, все типы высокого ранга вида k → ⋆ могут считаться типами для типов вида k, следовательно, они образуют ещё одну мультивселенную типов, независимую от иерархии (видов) типов, описанной ранее!

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

В Scala 3 появилось ключевое слово derives, которое при определении нового типа автоматически добавляет (в объект-компаньон) неявные значения экземпляров классов типов, указанных после derives:

import cats.Show, cats.derived.*
enum IntTree derives Show: // ключевыое слово derives!
  case Branch(left: IntTree, right: IntTree)
  case Leaf(elem: Int)
  
// использование derives Show приводит к генерированию примерно такого кода:
//object IntTree:
//  given Show[IntTree] = Show.derived // макрос!

В данном примере мы просим компилятор автоматически предоставить экземпляр класса типов Show, импортированного из широко используемой библиотеки Cats ? . Ключевое слово derives – это просто синтаксический сахар для хитрого добавления последней строчки. При добавлении неявного значения в объект-компаньон, компилятор сможет найти его при любом использовании типа IntTree без каких-либо дополнительных импортов. Сгенерированный код (последняя закомментированная строчка) подразумевает, что в одноименном с классом типа объекте-компаньоне Show должно быть определено значение (или метод без параметров) derived. Почему-то в “Кошках” для классов типов не определены derived, но нас выручит дочерняя библиотека Kittens ? – оттуда импортируется пакет cats.derived.*, в котором есть подходящий метод расширения для объекта Show и прочих. Воспользоваться выведенным экземпляром класса типа Show можно с помощью метода-расширения show, неявно требующего этот экземпляр:

import IntTree.*
val myTree = Branch(Leaf(4), Leaf(2))

import cats.syntax.all.*
myTree.show // неявно используется "выведенный" экземпляр Show[IntTree]

Мы можем потребовать сгенерировать реализацию класса типа для любого типа, вместо того, чтобы писать её вручную! Но необходимо, чтобы этот класс типа поддерживал derived. А вот там уже происходит настоящая “зазеркальная магия”, основанная на том, что любой тип представляется в виде алгебраического выражения, построенного из сумм, произведений и экспоненциалов. Реализация класса типа конструируется на базе синтаксического дерева алгебраического выражения указанного типа. И всё это происходит (макросы выручают) на этапе компиляции!

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

• Хабр-статьи

  • Type classes в Scala;

  • Классы типов в Scala (с небольшим обзором библиотеки cats);

  • Что такое класс типов?

• Статья от авторов Scala Type Classes as Objects and Implicits.

• Статья на ScalaJobs Typeclassery — A sure way of making generic programs context aware.

• Статья о классах типов в библиотеке Cats.

• Фрагмент документации Scala Implementing Type classes.

• Глава 12: Классы типов из переведённой серии Путеводитель неофита по Scala Даниеля Вестсайда.

• Статья Generic Type Class Derivation in Scala 3.

• Замечательная статья Лео Чунга Ad-hoc Polymorphism In Scala в которой к классам типов приходят от F-ограниченного полиморфизма, упоминавшегося ранее в данной статье.

Моноид

Опять этот неприветливый математический термин… Впрочем, он уже упоминался не раз, а в предыдущей статье был раскрыт с помощью картинок. Моноид – это конструкция, которая позволяет “сворачивать” списки до единственного значения, это всё, что необходимо, для построения функции List[A] => A. С помощью моноида можно пробежать список, накапливая в неком “аккумуляторе” результирующее значение. Это значит, что моноид должен предоставить, во-первых, “начальное значение” для случая пустого списка, а во-вторых бинарную операцию, принимающую аккумулятор и элемента списка, а возвращающую новое значение аккумулятора.

trait Monoid[A]:
  val neutral: A
  val combine: (A, A) => A

def imperativeFold[A](list: List[A])(using mon: Monoid[A]) =
  // реализация может быть разной
  var accum = mon.neutral // не ФП-шно, но наглядно
  for (a <- list)
    accum = mon.combine(accum, a)
  accum

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

given inSumMonoid: Monoid[Int] = new:
  val neutral = 0
  val combine = _ + _

val inProdMonoid: Monoid[Int] = new:
  val neutral = 1
  val combine = _ * _

val lst = List(4, 2)
imperativeFold(lst)                     // 6
imperativeFold(lst)(using inProdMonoid) // 8

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

Данный сценарий, типичен для применения классов типов. То, что полиморфный метод imperativeFold[A] принимает параметр Monoid[A], ограничивает его использование только классом таких типов, для которых предоставлен неявный экземпляр Monoid[A].

Законы моноида

Для того, чтобы “сворачивание” списка можно было проводить в любом порядке, в том числе и по частям, необходимо, чтобы бинарная операция была ассоциативной, а начальное значение – нейтральным элементом этой операции. Именно эти законы и определяют математическое понятие “моноид”. Технически, Scala позволяет учесть такие законы явно, но мы не станем так заморачиваться (популярные библиотеки также не особо следят за соблюдением законов своих классов типов).

Эксперименты с ООП

Возьмём, к примеру такой сервис:

trait StorageOop:
  def getVal(key: Int): Option[String]
  def setVal(key: Int, value: String): Unit
  def combine(other: StorageOop): Unit

И вроде тут описано всё, что мы можем получить, имея терм типа StorageOop, но

• это не все функции, связанные с типом, например, тут нет конструктора;

• метод combine выглядит неуместным – его реализация может переопределяться в наследниках, в то время как, по сути, он однозначно должен определяться двумя другими функциями; он не должен “принадлежать значению” типа StorageOop.

Перепишем этот трейт в виде универсального представления экзистенциального типа:

trait StorageTC[Storage]:
  def empty: Storage
  def getVal (storage: Storage)(key: Int): Option[String]
  def setVal (storage: Storage)(key: Int, value: String): Storage
  def combine(first: Storage, other: Storage): Storage

“Существует такой Storage, для которого определены эти функции”. Здесь

• явно присутствует один “конструктор” empty для типа Storage,

• функции getVal и setVal принимают первым параметром “хранилище” типа Storage,

• причём setVal и combine также возвращает новое, изменённое хранилище (ведь про тип Storage неизвестно ничего, он может быть неизменяемым),

• функция combine приняла законченный вид – это бинарная операция на значениях одного и того же типа.

Введём термины предметной области (DSL)

extension [Storage](storage: Storage)(using tools: StorageTC[Storage])
  def extract(key: Int)			    = tools.getVal(storage)(key)
  def keep(pair: (Int, String))	= tools.setVal(storage).tupled(pair)
  def mergeWith(other: Storage)	= tools.combine(storage, other)
object Storage:
  def empty[Storage: StorageTC] = summon[StorageTC[Storage]].empty

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

def businessLogic[Storage: StorageTC](storage1: Storage, storage2: Storage) =
  storage1 mergeWith storage2 keep (42 -> "ответ") extract 42

Чтобы вызвать бизнес-логику с хранилищем какого-то типа, необходимо предоставить “свидетельство” существования StorageTC для этого типа:

type Storage = Int => Option[String]

given StorageTC[Storage] = new:
  def empty = _ => None
  def getVal (storage: Storage)(key: Int) = storage(key)
  def setVal (storage: Storage)(key: Int, value: String) =
    k => Option.when(k == key)(value) orElse storage(k)
  def combine(first: Storage, other: Storage): Storage =
    first combine other

По сути, это реализация интерфейса.

Вот теперь мы можем вызвать бизнес-логику для двух разных (ну, типа ?) хранилищ Storage:

val emptyStorage = Storage.empty[Storage]
businessLogic(emptyStorage, emptyStorage) // Some("ответ")

Подводя итоги эксперимента можно сказать, что

• классы типов позволяют полностью покрыть возможности ООП-шных решений;

• слой “синтаксического сахара” – терминов предметной области – необязателен, но зачастую он позволяет писать очень выразительный код;

• решение задачи через традиционное ООП и через классы типов по объему примерно одинаковы;

• классы типов позволяют описывать требуемое поведение для любых существующих типов, в том числе и закрытых для дальнейшего наследования (final class);

• пример метода combine демонстрирует недостатки ООП подхода, когда “наследование” и “переопределение методов” может сделать код плохо предсказуемым; да и, в целом, инкапсуляция, “владение методов данными” не всегда удачно предметную область.

В дополнение парочка статей на ту же тему:

• вики-страница Haskell OOP vs type classes;

• пост из блога Александру Недельку OOP vs Type Classes, Part 1: Ideology;

• сказка О тяжёлой судьбе глаголов в Королевстве Существительных.

Типы-контейнеры

Обобщённые типы (generics) появились в программировании, когда в функциональном (по большей части) языке ML реализовали элементы системы F. То были простые конструкторы типов вида , основа предикативного полиморфизма, и другие виды тогда не поддерживались. Позднее такие обобщённые типы появились и в более популярных языках: C++, Delphi, Java, C# и т.п. Изначально ФП-шная “математическая” абстракция стала повсеместной (впрочем, таким же образом зародилось и развивается всё программирование), и возникла необходимость донести её до широкой публики. В качестве удобной аллегории для обобщённых типов вида , призванной “визуализировать” в воображении читателей некоторые ключевые соотношения, часто привлекается идея “контейнера”. Ей и посвящён этот раздел.

Идея обобщённого контейнера

Опять же, начнём с конкретного примера:

case class WithLog[A](a: A, log: String)

val intWithLog = WithLog(42, "создали значение;")
val stringWithLog = WithLog(
  intWithLog.a.toString,
  intWithLog.log + " преобразовали его в строку;"
)

stringWithLog.a // "42"

Трактовка WithLog[A] как “контейнера” для значения некого типа A весьма очевидна:

• вызывая конструктор WithLog[A], мы “запаковываем” значение пресловутого типа A в контейнер;

• в дополнительном поле log обобщённого класса WithLog мы можем накапливать журнал операций, производимых со значениями поля a;

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

Но, пожалуй, самым популярным примером контейнера является обобщённый список, имеющийся практически во всех статически-типизированных языках программирования:

val list: List[Int] = List(4, 2)
val emptyList = list.filter(_ > 42) // пусто!

val i1: Int = list.???      // какое из значений "распаковать"???
val i2: Int = emptyList.??? // как вытащить значение из пустого списка???

И тут список преподносит сюрпризы:

• не всегда возможно “распаковать” список, ведь этот контейнер может быть пустым;

• непонятно, что называть “распаковкой”, если в контейнере несколько значений. Ещё первым свойством обладают также некоторые стандартные контейнеры Scala, например, Option, Either, Try или Future.

Тогда будем называть контейнерами такие обобщённые типы, в которых значения типа параметра “хранятся” в отдельных полях?

Но вот ещё один пример:

type Func[A] = String => A
val parseInt: Func[A] = _.toIntOption.getOrElse(0)
val duplicateString: String => String = (s: String) => s concat s
val parseDouleInt: Func[A] = parseInt compose duplicateString
parseDouleInt("42") // 4242

Обобщённый тип Func[A] описывает функцию, возвращающую значение типа A, вычисляемую на основе переданной туда строки. Функция parseDouleInt: Func[Int] предваряет выполнение parseInt: Func[Int] удвоением исходной строки – мы опять получаем новый “контейнер” на основе исходного. В последней строчке, мы однозначно “распаковываем из контейнера” значение типа A = Int, используя строку "42". Но при этом, само “хранение” распаковываемого значения даже не предусмотрено!

Более запутанный случай представляет такой тип (ранее при обсуждении вариантности обобщённых типов уже упоминалось что-то похожее):

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

def value() = "значение"
val contStr: Cont[String] = continuation => continuation(value()) // замыкание!

val strToInt: String => Int = _.length
val contInt: Cont[Int]    = continuation => contStr(strToInt andThen continuation)

val strVal: String = contStr.??? // как распаковать???
val intVal: Int    = contInt.??? // как распаковать???

contStr(_ == "знание") // false. "значение" не равно "знание"!
contInt(_ <  10)       // true.  "значение".lenght меньше 10

Тут у нас тип функции, принимающей функцию-продолжение для типа A и возвращающий значение фиксированного типа. Функция-продолжение может как забывать исходное значение, так и, наоборот, обогащать его (тогда это значение удастся восстановить). Структура типа Cont[A] не предполагает хранения значений, поэтому для него нет ни только проектора этого значения, ни вообще какого-либо честного способа распаковки! Тем не менее, можно считать, что значение всё-таки содержится внутри contStr – в данном случае, это метод value(), умеющий вычислять значение нужного типа. Другая контейнерная переменная contInt определяется через преобразование contStr с помощью функции strToInt и перенимает всё тот же метод value. Его использование можно проследить в двух последних строчках. В итоге для конструктора типов Cont получаем следующее:

• “распаковка” значения не предусмотрена,

• но тип оказывается полезным – из его значений мы можем получать значения других типов;

• внутри скрытно “хранится” значение целевого типа, а точнее, способ его использования;

• из одного контейнеризированного значения можно получить другие контейнеризированные значения без распаковки! Можно ли Cont[A] считать “контейнером”? Вопрос выглядит спорным, но для содержательности дальнейших рассуждений предлагаю считать, что можно.

Приведённые примеры демонстрируют, что контейнерные типы не столько “хранят” значение, сколько содержат некий вычислительный контекст, который позволяет (или не позволяет) использовать значения указанного типа. При создании контейнера появляется “начальный” контекст, который меняется при “преобразованиях внутри контейнера” и используется при “распаковке”.

Вот ещё пара тривиальных, но важных типов-контейнеров:

type Id[A] = A
type Void[A] = Unit

Итак,

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

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

type Triple[+A, +B, +C] = (A, B Either C) // A × (B + C)

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

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

type Contravaianat[-A] = A => String
type Invariant    [ A] = A => A

Также как и для большинства других типов, важно понимание, как использовать значения типов-контейнеров. С функциональной точки зрения любой контейнерный тип полностью определяется единственной функцией “распаковки” F[A] = [B] => ???[A, B] => B. Здесь ???[A, B] – это всё, что необходимо для такого процесса. Однако, тип в общем случае не совпадает с , как это было с контейнером Cont, значит, и термин “распаковка” может показаться не достаточно удачным. Но для нас же это не проблема ??

Помимо распаковки таких типов, важны и другие их “контейнерные возможности” вроде map, flatMap и т.п. В Scala и многих других языках программирования они обычно реализованы как отдельные методы соответствующих обобщённых классов. Вынести эти возможности в некий общий родительский трейт не получится, ввиду широкого разнообразия контейнерных типов, не связанных наследованием. Да и, как уже упоминалось выше, ООП-шный подход плохо работает с функциями комбинирования (контейнеров, в нашем случае). Для единообразной работы с контейнерными типами удобнее использовать классы типов высокого рода.

Классы типов для контейнеров

Характерные возможности контейнерных типов распадаются на три основные группы:

• “преобразование внутри контейнера” (ковариантность);

• “преобразование самого контейнера”, когда имея значение одного контейнера, получаем другой контейнер, но с тем же простим типом;

• “перестановка контейнеров”, вложенных один в другой.

Запишем эти возможности в виде функциональных типов высокого рода:

type Lift[F[_]]       = [A, B] => (A => B) => (F[A] => F[B])
type ~>  [F[_], G[_]] = [A   ] => F[A]     => G[A]
type Swap[F[_], G[_]] = [A   ] => F[G[A]]  => G[F[A]]

Рассмотрим их детальнее.

Класс типов Lift отражает ковариантную сущность контейнера F. На практике удобнее использовать такие функции:

extension [A, B] (func: A => B)
  def lift[F[_]: Lift]: F[A] => F[B] = summon[Lift[F]](func)

extension [F[_]: Lift, A] (fa: F[A])
  def map(func: A => B): F[B] = func lift[F] f

Говорят, что функция высокого рода lift “поднимает” функцию func в “мир F” в то время как map “отображает” F[A] в F[B] посредством func: A => B. В многих языках для встроенных контейнеров доступна функция map, но, возможно, под другим именем (например, в C# это Select из Linq), так что всегда нужно обращать внимание на сигнатуру метода, тип функции, нежели на название. В Scala-библиотеке Cats, есть аналогичный класс типов Functor, название которого позаимствовано из теории категорий.

Стрелочку ~> иногда называют “естественным преобразованием”, что также восходит к теории категорий. В Cats есть тип FunctionK, но он чаще используется под таким же псевдонимом ~>. Этот обобщённый тип принимает сразу два типа-параметра, так что его значения не накладывают ограничений на какой-то один тип, что немного затрудняет его трактовку как класса типов. Но давайте введём такие каррированные псевдонимы

type To  [G[_]] = [F[_]] =>> F ~> G  
type From[F[_]] = [G[_]] =>> F ~> G
type Iso [F[_]] = [G[_]] =>> F ~> G & G ~> F // изоморфизм конейнеров... но это не точно ?

и с пользованием вспомогательных типов

type Id[A] = A  
type Dupe[F[_]] = [X] =>> F[F[X]]

получим наиболее часто встречающиеся примеры классов типов, основанных на естественных преобразованиях:

type Pure[F[_]]    = Id      ~> F   // = From[Id]  
type Extract[F[_]] = F       ~> Id  // = To[Id]  
type Flatten[F[_]] = Dupe[F] ~> F   // = From[Dupe[F]]

Введём полезные методы расширения:

extension[F[_], A] (fa: F[A])  
  def ~>[G[_]: From[F]]: G[A] = summon[F ~> G](fa)

extension[A] (a: A)
  def pure[F[_]: Pure]: F[A] = a.~>[F]

extension[F[_]: Extract, A] (fa: F[A])
  def extract: A = fa.~>[Id]

extension [F[_]: Flatten, A] (ffa: F[F[A]])
  def flatten: F[A] = ffa.~>[F]

extension[F[_]: Flatten: Lift, A] (fa: F[A])
  def flatMap[B](func: A => F[B]): F[B] = (fa map func).flatten

Функция pure “запаковывает” значение в контейнер. Название заимствовано у хаскелистов, подразумевающих хранение в контейнере именно вычислительного контекста – “запаковка” значения в контейнер заключается в создании чистого, “обеднённого” (pure) контекста. “Распаковку” контейнера представляет в примере выше функция extract – обычно такая возможность реализуется в классах-контейнерах как метод с названием, специфичным для каждого контейнера (run, get, reduce, use и т.п.). Естественное преобразование flatten называется так скорее всего потому, что в качестве контейнера F часто выступает список, и в этом случае flatten превращает двумерный список List[List[A]] в плоский (flat) List[A]. Часто встречающийся в коде Scala flatMap демонстрирует, что полезно комбинировать элементарные возможности, представленных основными классами типов-контейнеров. Другой пример – привычная фильтрация значений в контейнере F:

extension [F[_]: Lift: Flatten: From[Option], A] (fa: F[A])
  def filter(predicate: A => Boolean): F[A] =
    fa.flatMap(a => Option.when(predicate(a))(a).~>[F])

Наконец, третья ключевая возможность Swap позволяет переставлять вложенные контейнеры местами. К сожалению, не существует однозначного способа переставить местами произвольные вложенные контейнеры. Но это возможно в некоторых частных случаях, например, когда внешний контейнер представляет собой некую коллекцию, и её можно “свернуть” (fold), пробежаться по ней (traverse), а для внутреннего контейнера есть возможность преобразования пары контейнеров в контейнер для пары (про функции zip и tupled см. чуть ниже). В библиотеке Cats есть подходящий класс типов – Traverse, предоставляющий для таких контейнеров следующие функции (выражаются друг через друга):

extension[F[_]: Iso[Seq], A] (fa: F[A])  // F[_] - "сворачиваемый" список, Foldable
  def traverse[G[_]: Lift: Zip2: Pure, B](func: A => G[B]): G[F[B]] =
    fa.~>[Seq].foldLeft(Seq.empty[B].pure)((accum, a) => (accum zip func(a)).map(_ appended _)).map(_.~>[F])
   //  ↑↑↑↑↑↑↑                       ↑↑↑↑                       ↑↑↑          ↑↑↑                ↑↑↑   ↑↑↑↑↑

val urls: List[URL] = ???
def getStringFromUrl(url: URL): Future[String] = ???

val contents: Future[List[String]] = urls.traverse(getStringFromUrl)
//                                        ↑↑↑↑↑↑↑↑

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

type Distributive[G[_]] = [F[_], A] => F[G[A]] => G[F[A]]

extension[F[_], G[_]: Distributive, A] (fga: F[G[A]])
  def cosequence: G[F[A]] = summon[Distributive[G]](fga)

extension[F[_]: Lift, A] (fa: F[A])
  def distribute[G[_] : Distributive, B](agb: A => G[B]): G[F[B]] = summon[Distributive[G]](fa map agb)

Перестановку можно произвести не только с простыми, но и с N-контейнерами. В качестве последних часто выступают произведения типов (кортежи):

type Swap2  [F[_, _], G[_]   ] = [A, B] => F[G[A], G[B]] => G[F[A,    B]]
type Coswap2[F[_],    G[_, _]] = [A, B] => F[G[A,    B]] => G[F[A], F[B]]

// классы типов для контейнеров-кортежей:
type ×[A, B] = (A, B) // инфиксный синоним для произведения типов
type Zip2  [F[_]] = Swap2  [×, F]
type Unzip2[F[_]] = Coswap2[F, ×]

extension[F[_]: Zip2, A] (fa: F[A])
  def zip[B](fb: F[B]): F[A × B] = summon[Zip2[F]]((fa, fb))

extension[F[_]: Unzip2, A, B] (fab: F[A × B])
  def unzip: F[A] × F[B] = summon[Unzip2[F]](fab)

Здесь в названиях методов прослеживается аналогия между опять же списками и застёжками-молниями:

val ints = List(4, 2)
val strings = List("4", "2")
val intStrings = ints zip strings     //  List((4, "4"), (2, "2"))
val (ints1, ints2) = intStrings unzip // (List(4, 2), List("4", "2"))

Комбинатор zip производит контейнерные вычисления независимо друг от друга – например, даже если в одном из них произойдёт ошибка, другое всё равно будет запущено. Иными словами, безотносительно разнесения по времени, вычисления посредством zip производятся параллельно, в то время как flatMap организует последовательное выполнение, при котором сбой на любом шаге прервёт всю цепочку. Исходя из этих соображений, для комбинирования независимых вычислений вместо Zip2 вводится класс типов “аппликативный функтор” – к нему относят возможность zip и другие вспомогательные функции (prodctL, productR и т.п.). В библиотеке Cats этот класс типов называется Applicative. Аналогичные функции встречаются под названиями tupled/untupled, явно указывая, что они работают с кортежами.

Особняком стоит возможность, общая для большинства типов – вычисление значения произвольного типа на основе контейнеризированного: F[A] => B. Такие функции, как и обычная “распаковка“, называются по-разному в зависимости от самого контейнера (use, apply, fold и т.п.). В Scala для списков и других похожих на них контейнеров (Option, Either и т.п.) такая функция называется fold (“свёртка”). В библиотеке Cats представлен класс типов Foldable c реализациями для контейнеров, представимых в виде списков (Option, различные деревья и т.п.). На самом деле, такой класс типов эквивалентен естественному преобразованию F ~> List:

extension[F[_]: To[List], A] (fa: F[A])
  def fold[B](start: B, combine: (B, A) => B) =
    fa.~>[List].foldLeft(start)(combine)

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

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

То, что в данной статье называется “контейнерными типами” в других источниках нередко именуется “функторами” или даже чаще “монадами”. Всё дело в том, что такая возможность как map (lift) является ключевой для понятия “функтор”, а flatMap (flatten) – для “монады”, и эти названия транслируются на контейнерные типы, обладающими таким возможностями (что, на самом деле, не совсем корректно). Различие в терминологии стоит иметь в виду при изучении других источников на ту же тему:

• хабр-переводы статей из блога Эдит Баргавы, с примерами на Haskell, но большим количеством замечательных авторских картинок, раскрывающих концепцию контейнера:

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

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

• более фундаментальная, но достаточно популярная PDF-статья The Essence of the Iterator Pattern на английском (и на Haskell);

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

• статья Конора Макбрайда и Росса Патерсона Applicative programming with effects об аппликативных функторах.

Эффекты

Контейнерный тип позволяет разнести по времени создание экземпляра и его “распаковку”. Это позволяет клиентскому коду самому решать, когда и как “распаковывать контейнер”. Например, подготовленный в одном месте список целых чисел в других местах может быть просуммирован, или просто выведен на экран (это также своеобразный вариант “распаковки”), причём, сам контейнер может быть предварительно модифицирован – числа могут быть отфильтрованы, преобразованы в строки и т.п.

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

Для решения таких проблем в Scala есть контейнер Future, который хранит контекст асинхронного вычисления сложной задачи (см. например, статью A Guide to Scala Futures). При создании экземпляра контейнера на основе какой-либо функции, её вычисление запускается в новом потоке (но это не точно ?). Отложенная “распаковка” производимых в контейнере вычислений позволит среде исполнения и операционной системе более рационально распоряжаться мощностями компьютера, тем самым экономя ресурсы, прежде всего, время. Для Future также реализованы ключевые возможности контейнеров, вроде тех же map или flatMap – преобразования будут производится не в основном потоке (при необходимости), даже если изначально контейнер создавался методом Future.successful с чистым (pure) контекстом. Кроме того, в библиотеке Cats.Effect есть реализации некоторых классов типов для Future, предоставляющие этому контейнеру дополнительные возможности. Аналогичные обобщённые контейнеры для асинхронных вычислений встречаются в многих популярных языках программирования.

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

Впрочем, всё не так плохо. Есть несколько популярных Scala-библиотек, которые предоставляют ленивые контейнеры, предназначенные для построения композиции функций с побочными эффектами. Их “ленивость” заключается в том, что они не запускают вычисления сразу, а просто сохраняют внутри себя все преобразования до самого этапа распаковки. Это позволяет “чисто“ описать весь алгоритм, позволив компилятору гарантировать его корректность, а все побочные эффекты скобинированных внутри функций сработают только в самом конце программы, когда неявно библиотечными инструментами будет производится распаковка.

Хорошим примером является контейнер IO (Inpout/Output) из упомянутой ранее библиотеки Cats.Effect. Очень упрощённо этот контейнер можно определить так:

enum IO[+A]:
  case Pure[A](a: A)                           extends IO[A] // ≅ A
  case FlatMap[A, B](ib: IO[B], f: B => IO[A]) extends IO[A] // ≅ IO[B] × IO[A]ᴮ

Можно заметить, что контейнер IO представляет собой по сути список разнородных (по типу) функций, а в самом начале этого списка лежит некое исходное значение. Для такого типа очевидным образом определяются все основные возможности, присущие контейнерам. Отличительной особенностью IO и прочих ленивых контейнеров является то, что их всегда можно преобразовать к любому другому контейнеру без потерь. Способность контейнеров быть преобразованными к любым другим контейнерам без потерь часто называется “начальной” или “свободной” монадой.

import IO.* // из примера выше

type ~>[F[_], G[_]] = [A] => F[A] => G[A] // "естественное" преобразование контейнеров

val ioToOption: IO ~> Option =
  [A] => (_: IO[A]) match
    case Pure(a)          => Some(a)
    case FlatMap(ib, fba) => ioToOption(ib) flatMap {fba andThen ioToOption.apply}

val initIO = FlatMap(FlatMap(Pure(
  42),
  i => {                  println("Int: " + i); Pure(i.toString)}),
  s => {val l = s.length; println("Len: " + l); Pure(l)})

val res1 = ioToOption(initIO)
val res2 = ioToOption(initIO)
println("Res: " + res1)
// Вывод в консоль:
// Int: 42
// Len: 2
// Int: 42 <-- эффекты срабатывают не при конструировании IO,
// Len: 2      а при КАЖДОЙ его "перепаковке" (например, в Option)
// Res: Some(2)

Здесь демонстрируется преобразование самописного контейнера IO в стандартный Option, но не сложно экстраполировать это решение на любой другой конечный контейнер. Также пример раскрывает “ленивость” IO – побочные эффекты преобразований срабатывают не при конструировании контейнера (как в случае Future), а при каждой его “распаковке”, или “перепаковке” в другой контейнер. Впрочем, IO из Cats, или аналогичные ленивые контейнеры из других библиотек не являются “полностью свободными”, в том смысле, что для их распаковки не обязательно самому предоставлять преобразования к “неленивым” контейнерам, так как в библиотеках уже есть встроенные механизмы “интерпретации” (то бишь распаковки) этих контейнеров.

Контейнер IO в большинстве ситуаций является лучшей альтернативой в сравнении с Future. Использование IO позволяет писать “чистый” код в функциональном стиле. Про преимущества IO над Future можно прочесть тут:

• Gist.github: From Scala Future to Cats Async?, IO vs Future and Referential transparency;

• Stackoverflow: Why future has side effects?, Scala with cats IO/Either instead of Future/Exceptions;

• замечательная статья IO monad: which, why and how Матеуша Кубушока, опубликованная в его блоге.

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

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

В качестве примера рассмотрим контейнер для эффекта "возможного сбоя" вычислений:

import scala.util.Try
type F[X] = Try[X]

// шаги вычисления; реализация не важна
val fa :      F[A] = ??? // начальное значение в контейнере
val afb: A => F[B] = ??? // функция с "эффектом"
val bc:  B =>   C  = ??? // "чистая" функция
val cfd: C => F[D] = ??? // функция с "эффектом"

// один из вариантов записи композции вычислений
val program: F[D] = // : Try[D]
  fa  flatMap
  afb map
  bc  flatMap
  cfd

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

В дополнение можно прочитать хабр-обзор Особенности сред исполнения различных систем эффектов в Scala. Подробнее об использовании контейнеров для обработки эффектов можно узнать из оригинальных работ Евгения Могги Notions of computation and monads и Monads and Effects, или на основанной на них статье Бартоша Милевски Monads and Effects. Другая фундаментальная статья – The marriage of effects and monads от Филиппа Вадлера и Питера Тиманна.

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

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

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

  type  F[+X]           // полноценный контейнер со всеми возможностями
  type  G[+X]           // и ещё один
  type FG[+X] = F[G[X]] // комбинация контейнеров

Будет ли новый тип “контейнерным”? Согласно данному в этой статье определению контейнера через ковариантность – безусловно да. В библиотеке Cats есть класс Nested вида , с уже реализованной возможностью map для вложенных контейнеров:

import cats.syntax.all.*
import cats.data.Nested

val listOptInt: List[Option[Int]] = List(Some(2), Some(1), None)

Nested(listOptInt)
  .map(_ * 2) // умножаем на 2 всё непустые элементы списка
  .value      // List(Some(4), Some(2), None)

К сожалению, Nested не умеет комбинировать “эффективные” функции – для него нет возможности “разматрёшивания” flatten: F[F[X]] => F[X], которая для вложенного контейнера FG из примера выше будет выглядеть так

def flattenFG[X]: F[G[F[G[X]]]] => F[G[X]]

Теоретически, функцию flatten можно сконструировать для любого контейнера, но ввиду того, что количество потенциальных комбинаций эффектов неограниченно, было бы здорово уметь собирать такую функцию автоматически из возможностей имеющихся контейнеров. Например, если в flattenFG переставить местами средние контейнеры F[G[F[G[X]]]] => F[F[G[G[X]]]], останется только “разматрёшить“ F и G. То есть нужно отношение (которое почему-то называют дистрибутивным законом) вида

def swapGF[X]: G[F[X]] => F[G[X]]

Проблема заключается в том, что реализовать автоматичекую перестановку для произвольных контейнеров F и G не получается – в общем случае контейнеры не коммутируют (см. статью Тони Морриса: Monads do not compose).

Тем не менее, есть несколько полезных контейнеров, которые всегда можно “протащить на верх” композиции с любым другим контейнером. Это означает, что для каждого такого частного случая можно трансформировать произвольный контейнер в новый, обогащённый контекстом для работы с дополнительным эффектом. Значит, нам нужны новые типы – контейнерные трансформеры ?, который обычно называются монадными трансформерами, так как они “сохраняют” возможность flatten, ассоциирующуюся с понятием “монада”.

Контейнерный трансформер представляет собой обобщённый тип вида , но чаще встречаются трансформеры дополненные вспомогательными типами: . Библиотека Cats предлагает следующте трансформеры:

Трансформеры обогащают контекст исходного контейнера возможностью обработки дополнительных эффектов и сохраняют возможность flatMap исходного контейнера для комбинирования “эффективных” функций:

import cats.data.OptionT
import cats.syntax.all.*

def twiceAndTrice(i: Int) = OptionT(List(Some(i * 2), Some(i * 3)))

OptionT(List(Some(2), Some(1), None))
  .flatMap(twiceAndTrice)  // OptionT(List(Some(4), Some(6), Some(2), Some(3), None))
  .map(_ + 100)            // OptionT(List(Some(104), Some(106), Some(102), Some(103), None))
  .reduceLeftOption(_ + _) // Some(415)

К сожалению, контейнерные трансформеры не решают окончательно проблему композируемости контейнеров. Для одних контейнеров можно построить более одного соответствующего ему трансформера, а для других почти не возможно этого сделать. Например, сложности построения трансформера для контейнера List прояснили авторы Cats в ответе на частый вопрос Where is ListT?.

Помимо таких простых трансформеров есть носители и более интересных эффектов. В библиотеке Cats есть, например, такие трансформеры:

• Fiber позволяющий производить вычисления параллельно;

• Resource, который открывает доступ к ресурсу, только при попытке его использования (распаковки контейнера) и гарантирует его “освобождение“ сразу после этого;

• Ref, обеспечивающий конкурентный доступ к изменяемым данным. Библиотека FS2 предоставляет трансформер Stream[F[_], A], позволяющий работать с потоками данных (в том числе с асинхронными). Возможны и другие трансформеры.

Ещё про монадные трансформеры можно прочесть тут:

• хабр-перевод: Монадные трансформеры для практикующих программистов статьи Габриэля Петронеллы;

• фрагмент лекции Трансформаторы монад (“трансформаторы”, Карл!?) из курса Функциональное и логическое программирование на ресурсе Николая Якимова;

• статья Monad transformers с ресурса herding cats Юджина Йокоты;

• более фундаментальная статья Combining Monads Девида Кинга и Филиппа Вадлера.

Чаще всего трансформеры используются для надстройки контейнеров побочных эффектов, вроде Future или IO. Если необходимо использовать более одного трансформера, то это может вызвать определённую боль, которую можно попробовать полечить, например, с помощью библиотеки Cats-MTL. Другое решение предлагает библиотека ZIO (тут красочная реклама) – одноимённый тип позиционируется как универсальный контейнер, у которого имеются возможности для работы со всеми нужными эффектами. Этот тип очень упрощённо можно представить как применение к IO сразу двух трансформеров: ReaderT для инъекции зависимостей и EitherT для управления обработкой ошибок:

type ZIO[R, E, X] = R => IO[E Either X] 
//                = ReaderT[[A] =>> EitherT[IO, E, A], R, X]

Авторы библиотеки утверждают, что контейнер ZIO (в совокупности “ресурсами“ и “потоками” оттуда же, а также многочисленными интеграциями с другими библиотеками) предоставляет все необходимые возможности для комфортной “чистой” работы с эффектами, и не требует дополнительного применения трансформеров, или классов типов, вроде тех, что предлагает библиотека Cats.

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