[Из песочницы] Сказ о полукольцах30.03.2019 18:49

habr.png

Привет, Хабр! Предлагаю вашему вниманию перевод статьи «A tale on Semirings» автора Luka Jacobowitz.

Когда-нибудь задумывались, почему сумма типов называется суммой типов. Или, может, вы всегда хотели узнать, почему оператор <*> записывается именно так? И что это имеет общего с полукольцами? Заинтересовавшихся прошу под кат!

Данная статья является переводом поста в блоге компании Typelevel под авторством Луки Якобовича. Для наилучшего ее восприятия требуется хотя бы поверхностное знакомство с языком Scala и его экосистемой (в том числе, библиотекой cats) и знание базовых понятий абстрактной алгебры: полугруппа, моноид и т.д.


Алгебраические структуры

Многие из нас знают о моноидах и полугруппах и даже пользуются ими. Эти структуры обладают свойствами, которые позволяют применять их напрямую для получения более высокого уровня абстракции (если вы о них не знаете, можете прочитать в документации библиотеки сats). Тем не менее, иногда тип данных обладает более чем одним моноидом или полугруппой. Очевидным примером являются различные численные типы, где умножение и сложение образуют два полноценных моноида.

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

Существуют различные способы представить это в виде классов типов и разные библиотеки делают это по-своему, но давайте рассмотрим как это сделано в проекте (библиотека?) алгебра (ссылка). Базой в ней являются AdditiveSemigroup и MultiplicativeSemigroup.

[Примечание: поскольку название «класс типов» не особо прижилось в русском языке, далее будет использоваться его английский вариант — type class]

import simulacrum._

@typeclass trait AdditiveSemigroup[A] {
  def +(x: A)(y: A): A
}

@typeclass trait AdditiveMonoid[A] extends AdditiveSemigroup[A] {
  def zero: A
}

@typeclass trait MultiplicativeSemigroup[A] {
  def *(x: A)(y: A): A
}

@typeclass trait MultiplicativeMonoid[A] extends MultiplicativeSemigroup[A] {
  def one: A
}

[Примечание: Аннотация @typeclass из проекта simulacrum позволяет автоматически генерировать часто-используемые методы для type class-ов и не влияет на логическую составляющую кода]

В таком случае, полукольцо (Semiring) — это аддитивный моноид (AdditiveMonoid), объединенный с мультипликативным моноидом (MultiplicativeMonoid) и снабженный следующими дополнительными законами:


  1. Коммутативность по сложению: $inline$ x + y = y + x $inline$
  2. Дистрибутивность справа: $inline$ (x + y) \times z = (x \times z) + (y \times z) $inline$
  3. Дистрибутивность слева: $inline$ x \times (y + z) = (x \times y) + (x \times z) $inline$
  4. Наличие нуля справа: $inline$ x \times zero = zero $inline$
  5. Наличие нуля слева: $inline$ zero \times x = zero $inline$

Чтобы задать соответствующий полукольцу type class, объединим AdditiveMonoid и MultiplicativeMonoid: 

@typeclass trait Semiring[A] extends MultiplicativeMonoid[A] with AdditiveMonoid[A]

Теперь, когда у нас есть Semiring, мы можем использовать его с различными численными типами: Int, Long, BigDecimal и т.д., но разве это стоит целой статьи о полукольцах? Оказывается, множество других вещей также являются полукольцами, включая логические значения, множества и даже анимации.

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


Кардинальные числа

Давайте начнем с того, что вообще подразумевается под кардинальным числом. Каждому типу соответствует число значений, которые представители этого типа могут принимать. Например, тип Boolean обладает кардинальным числом $inline$2$inline$, потому что у него всего два возможных значения: true и false.

Итак, у Boolean — $inline$2$inline$, а сколько у других типов? У Byte — $inline$2^8$inline$, у Short — $inline$2^{16}$inline$, у Int — $inline$2^{32}$inline$, а у Long — $inline$2^{64}$inline$. А что насчет строк? String — формально неограниченный тип и теоретически обладает бесконечным числом значений (на практике, естественно, мы не обладаем бесконечной памятью, поэтому конкретное число будет зависеть от конфигурации компьютера).

Для каких еще типов мы можем определить их кардинальное число? Два довольно простых примера: Unit, у которого ровно один представитель, и Nothing, который является нижней границей всех возможных типов в Scala и соответственно имеет $inline$0$inline$ возможных значений. То есть, вы никогда не сможете создать значение Nothing, что соответствует кардинальному числу $inline$0$inline$.

Отлично, теперь можно попробовать выразить это в коде. Мы можем создать type class, способный дать нам общее число значений соответствующего типа.

trait Cardinality[A] {
  def cardinality: BigInt
}

object Cardinality {
  def of[A: Cardinality]: BigInt = apply[A].cardinality

  def apply[A: Cardinality]: Cardinality[A] = implicitly
}

Теперь попробуем создать несколько экземпляров этого класса: 

implicit def booleanCardinality = new Cardinality[Boolean] {
  def cardinality: BigInt = BigInt(2)
}

implicit def longCardinality = new Cardinality[Long] {
  def cardinality: BigInt = BigInt(2).pow(64)
}

implicit def intCardinality = new Cardinality[Int] {
  def cardinality: BigInt = BigInt(2).pow(32)
}

implicit def shortCardinality = new Cardinality[Short] {
  def cardinality: BigInt = BigInt(2).pow(16)
}

implicit def byteCardinality = new Cardinality[Byte] {
  def cardinality: BigInt = BigInt(2).pow(8)
}

implicit def unitCardinality = new Cardinality[Unit] {
  def cardinality: BigInt = 1
}

implicit def nothingCardinality = new Cardinality[Nothing] {
  def cardinality: BigInt = 0
}

[Примечание: приведенные значения могут быть также объявлены как implicit val]

Давайте опробуем их в REPL: 

scala> Cardinality.of[Int]
res11: BigInt = 4294967296

scala> Cardinality.of[Unit]
res12: BigInt = 1

scala> Cardinality.of[Long]
res13: BigInt = 18446744073709551616

Здорово, но все это очень просто, что насчет ADT? Можем ли мы обрабатывать их подобным образом? Оказывается, можем, нужно лишь понять, как обращаться с простейшими суммами и произведениями типов. Для начала, рассмотрим простейшее произведение типов: (Boolean, Byte)

Как много представителей у этого типа? Мы знаем, что у Boolean их $inline$2$inline$, а у Byte — $inline$256$inline$. Таким образом, получаются числа от $inline$-128$inline$ до $inline$127$inline$ объединенные с true или false. Получается $inline$512$inline$ уникальных значений.

$inline$512$inline$ выглядит как $inline$256$inline$, умноженное на $inline$2$inline$, так что, возможно, нужно просто умножить число значений первого типа на число значений второго? Если вы проверите это с остальными примерами, то убедитесь, что это действительно так. Давайте представим это в виде экземпляра type class«а: 

implicit def tupleCardinality[A: Cardinality, B: Cardinality] =
  new Cardinality[(A, B)] {
    def cardinality: BigInt = Cardinality[A].cardinality * Cardinality[B].cardinality
  }

Теперь рассмотрим пример суммы типов: Either[Boolean, Byte]. В этом случае ответ еще более очевиден, поскольку значением этого типа (по сути) может быть либо Boolean, либо Byte, так что достаточно просто сложить кардинальные числа. Таким образом, у Either[Boolean, Byte] должно быть $inline$256+2 = 258 $inline$ представителей.

Давайте аналогичным образом выразим это в коде и подтвердим результаты в REPL: 

implicit def eitherCardinality[A: Cardinality, B: Cardinality] =
  new Cardinality[Either[A, B]] {
    def cardinality: BigInt = Cardinality[A].cardinality + Cardinality[B].cardinality
  }

scala> Cardinality.of[(Boolean, Byte)]
res14: BigInt = 512

scala> Cardinality.of[Either[Boolean, Byte]]
res15: BigInt = 258

scala> Cardinality.of[Either[Int, (Boolean, Unit)]]
res16: BigInt = 4294967298

Следовательно, для суммы типов кардинальные числа складываются, а для произведения — перемножаются. Это логично, учитывая их названия.

Так что насчет того гомоморфизма, о котором шла речь ранее? Гомоморфизм — это сохраняющее структуру отображение между двумя алгебраическими структурами одного типа (в данном случае, полукольцами).

Это означает, что для любых $inline$x$inline$, $inline$y$inline$ и гомоморфизма $inline$f$inline$ мы имеем:


  1. $inline$f (x \times y) = f (x) \times f (y)$inline$
  2. $inline$f (x + y) = f (x) + f (y)$inline$

Последние выражения могут показаться достаточно абстрактными, но они имеют непосредственное отношение к тому, что мы только что сделали. Если мы «сложим» два типа Byte и Boolean, то получим Either[Byte, Boolean], и если мы применим к нему гомоморфизм cardinality, то получим $inline$258 $inline$. Это равносильно применению cardinality к Byte и к Boolean отдельно с последующим сложением результатов.

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

Как мы уже видели, у типа Unit — один представитель, а у типа Nothing — ни одного. Можем ли мы использовать эти два типа, чтобы образовать полукольцо?

Давайте попробуем! Если Unit — единица по умножению, то произведение любого типа с Unit должно быть эквивалентно первому типу. Естественно, это выполняется, поскольку мы легко можем отобразить что-нибудь из разряда (Int, Unit) в Int и обратно без потерь, так что и кардинальное число остается без изменения.

scala> Cardinality.of[Int]
res17: BigInt = 4294967296

scala> Cardinality.of[(Unit, Int)]
res18: BigInt = 4294967296

scala> Cardinality.of[(Unit, (Unit, Int))]
res19: BigInt = 4294967296

А что насчет Nothing? Поскольку это единица по сложению, сумма любого типа с Nothing должна быть эквивалентна этому же типу. Совпадает ли Either[Nothing, A] с A? Да! Поскольку у Nothing нет ни одного значения, то Either[Nothing, A] может быть только Right и, как следствие, только A, так что эти типы эквивалентны.

Нам также необходимо проверить корректность нуля по умножению: любое число, умноженное на единицу по сложению zero, должно совпадать с zero. Поскольку Nothing является нашей единицей по сложению, такое произведение типов как (Int, Nothing) должно быть эквивалентно Nothing. Это выполняется, поскольку мы не можем создать значение типа Nothing и, как следствие, содержащий такое значение кортеж.

Проверим, как это соотносится с кардинальными числами.

Единица по сложению: 

scala> Cardinality.of[Either[Nothing, Boolean]]
res0: BigInt = 2

scala> Cardinality.of[Either[Nothing, (Byte, Boolean)]]
res1: BigInt = 258

Поглощение нулем: 

scala> Cardinality.of[(Nothing, Boolean)]
res0: BigInt = 0

scala> Cardinality.of[(Nothing, Long)]
res1: BigInt = 0

Осталось проверить дистрибутивность. В контексте типов это означает, что (A, Either[B, C]) должно совпадать с Either[(A, B), (A, C)]. Если проверить, то эти два типа действительно окажутся эквивалентными.

scala> Cardinality.of[(Boolean, Either[Byte, Short])]
res20: BigInt = 131584

scala> Cardinality.of[Either[(Boolean, Byte), (Boolean, Short)]]
res21: BigInt = 131584


Алгебраические структуры высшего порядка

Некоторые возможно уже слышали о type class-е Semigroupal. Но почему он так называется и как соотносится с Semigroup? Для начала, давайте посмотрим на сам Semigroupal: 

@typeclass trait Semigroupal[F[_]] {
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

Есть определенная схожесть с Semigroup: комбинируются два значения, причем соответствующая операция должна быть ассоциативна (аналогично Semigroup).

Пока все в порядке, но имя функции product немного смущает. Оно логично, поскольку мы объединяем A и B в кортеж, который является произведением типов, но если мы используем произведение, возможно, это не произвольный Semigroupal, а мультипликативный? Давайте его переименуем.

@typeclass trait MultiplicativeSemigroupal[F[_]] {
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

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

@typeclass trait AdditiveSemigroupal[F[_]] {
  def sum[A, B](fa: F[A], fb: F[B]): F[Either[A, B]]
}

Выглядит неплохо — можем ли мы добавить единицы, чтобы получить Monoidal? Конечно можем! Это будут опять Nothing и Unit для суммы и произведения соответственно: 

@typeclass trait AdditiveMonoidal[F[_]] extends AdditiveSemigroupal[F] {
  def nothing: F[Nothing]
}

@typeclass trait MultiplicativeMonoidal[F[_]] extends MultiplicativeSemigroupal[F] {
  def unit: F[Unit]
}

Теперь у нас есть эти type class-ы, но как мы можем их использовать? Что ж, с уверенностью заявляю, что они уже используются в библиотеке cats, но под другими именами.

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

Так как речь идет о сумме, этот оператор скорее всего должен содержать + и показывать, что операция выполняется в каком-то контексте. Идеальным было бы использование чего-то вроде [+], но это некорректный идентификатор, так что попробуем <+> вместо него.

def <+>[A, B](fa: F[A], fb: F[B]): F[Either[A, B]]

Функция <+> уже существует в cats в качестве псевдонима для combineK, который можно найти в SemigroupK, но он ведет себя по-другому. Он принимает на вход два F[A] и возвращает F[A] — не совсем похоже на то, что мы имеем.

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

def sum[A, B](fa: F[A], fb: F[B]): F[Either[A, B]]

def combineK[A](x: F[A], y: F[A]): F[A] = {
  val feaa: F[Either[A, A]] = sum(x, y)
  feaa.map(_.merge)
}

Поскольку AdditiveSemigroupal эквивалентен SemigroupK, возможно, AdditiveMonoidal совпадает с MonoidK? Да, и это показать это достаточно легко. MonoidK дополнен функцией empty: 

def empty[A]: F[A]

Эта функция использует универсальный квантор для A, то есть, работает для любого A, что означает, что на самом деле она не может оперировать никаким конкретным A и тем самым эквивалентна F[Nothing] в AdditiveMonoidal.

Что ж, мы нашли аналоги для аддитивных классов и уже знаем, что MultiplicativeSemigroupal эквивалентен cats.Semigroupal. Все, что нам осталось, это найти эквивалент MultiplicativeMonoidal.

Я немного сжульничаю и скажу, что этим эквивалентом является Applicative. Он добавляет функцию pure, которая принимает A и возвращает F[A]. MultiplicativeMonoidal в свою очередь обладает функцией unit, не принимающей параметров и возвращающей F[Unit]. Как перейти от одного к другому? Ответ опять подразумевает использование функтора: 

def unit: F[Unit]

def pure(a: A): F[A] = unit.map(_ => a)

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

Теперь в cats у нас есть <+> и <*>, но существует ли type class, объединяющий их, аналогично как Semiring объединяет + и *? Есть, и он называется Alternative. Он наследуется от Applicative и MonoidK. Чтобы быть последовательными, мы назовем его Semiringal: 

@typeclass 
trait Semiringal[F[_]] extends MultiplicativeMonoidal[F] with AdditiveMonoidal[F]

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

Если бы он был доступен, мы могли бы вывести Semiring для любого Alternative аналогично выведению Monoid для MonoidK или Applicative. Также, мы могли бы превратить Semiring обратно в Alternative, используя Const, аналогично превращению Monoid в Applicative.

В завершение, посмотрим, как можно записать данное преобразование: 

import Semiring.ops._

case class Const[A, B](getConst: A)

implicit def constSemiringal[A: Semiring] = new Semiringal[Const[A, ?]] {
  def sum[B, C](fa: Const[A, B], fb: Const[A, C]): Const[A, Either[B, C]] =
    Const(fa.getConst + fb.getConst)

  def product[B, C](fa: Const[A, B], fb: Const[A, C]): Const[A, (B, C)] =
    Const(fa.getConst * fb.getConst)

  def unit: Const[A, Unit] =
    Const(Semiring[A].one)

  def nothing: Const[A, Nothing] =
    Const(Semiring[A].zero)
}


Заключение

Кольца и полукольца представляют собой весьма интересные алгебраические структуры, и, даже если вы не задумывались об этом, скорее всего вы уже ими пользовались. Этот пост был написан, чтобы показать как Applicative и MonoidK соотносятся с Monoid, почему алгебраические типы данных образуют полукольцо и как эти алгебраические структуры распространились в Scala и других языках программирования. Лично для меня осознание того, как все это взаимосвязано и образует очень занятную симметрию, было просто взрывом мозга, и я надеюсь, что этот пост сможет помочь найти аналогичные интересные параллели в Cats и других библиотеках, основанных на различных математических абстракциях. Дальнейший материал по этой теме вы сможете найти здесь.


Дополнение

В этом посте я умолчал о коммутативности в записи type class-ов. Коммутативность — очень важное свойство для полуколец и код должен отражать это свойство. Тем не менее, поскольку пост уже содержит множество определений, дополнение его еще нескольими коммутативными type class-ами, которые не делают ничего, кроме внесения новых законов, выглядело излишним и отвлекающим от основной цели поста.

Более того, я фокусировался на кардинальных числах только тех классов, которые были нам нужны, но для полноты можно добавить определения Cardinality для таких вещей как A => B, Option[A], Ior[A, B]: 


  1. Cardinality.of[A => B] === Cardinality.of[B].pow(Cardinality.of[A])


  2. Cardinality.of[Option[A]] === Cardinality.of[A] + 1


  3. Cardinality.of[Ior[A, B]] === Cardinality.of[A] + Cardinality.of[B] + Cardinality.of[A] * Cardinality.of[B]

© Habrahabr.ru