O Conto dos Meios Anéis

Olá Habr! Trago à sua atenção uma tradução do artigo "Um conto sobre Semirings", de Luka Jacobowitz.

Já se perguntou por que a soma dos tipos é chamada de soma dos tipos. Ou talvez você sempre quis saber por que o operador <*> é escrito dessa maneira? E o que isso tem a ver com meias argolas? Interessado, por favor, peça um corte!

Este artigo é uma tradução de uma postagem no blog Typelevel por Luke Jakobovic. Para sua melhor percepção, é necessário pelo menos uma familiaridade superficial com a linguagem Scala e seu ecossistema (incluindo a biblioteca de gatos) e conhecimento dos conceitos básicos da álgebra abstrata: um semigrupo, um monóide, etc.

Estruturas algébricas

Muitos de nós conhecem monoides e semigrupos e até os usam. Essas estruturas têm propriedades que permitem aplicá-las diretamente para obter um nível mais alto de abstração (se você não souber sobre elas, pode ler a documentação da biblioteca de gatos ). No entanto, às vezes um tipo de dados possui mais de um monóide ou semigrupo. Um exemplo óbvio são os vários tipos numéricos, onde multiplicação e adição formam dois monoides completos.

Na álgebra abstrata, há uma classe separada de estruturas com dois monóides interagindo de uma certa maneira. Esta classe é meio toque. Como os monóides são frequentemente usados ​​para descrever tipos numéricos, eles geralmente são divididos em multiplicativo e aditivo. Como no caso dos números, as leis de uma semicondução determinam que a multiplicação é distributiva por adição e a multiplicação de qualquer número por unidade por adição - zero - dá zero.

Existem várias maneiras de apresentá-lo à medida que classes de tipo e bibliotecas diferentes fazem do seu jeito, mas vamos ver como isso é feito em um projeto de álgebra . A base nele são AdditiveSemigroup e MultiplicativeSemigroup .

[ Observação: como o nome "classe de tipo" não se enraizou em russo, sua versão em inglês será usada posteriormente - classe de tipo ]

 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 } 

[ Nota: a anotação @typeclass do projeto simulacrum permite gerar automaticamente métodos freqüentemente usados ​​para classes de tipo e não afeta o componente lógico do código ]

Nesse caso, o semiring ( Semiring ) é um monóide aditivo ( AdditiveMonoid ), combinado com o monóide multiplicativo ( MultiplicativeMonoid ) e equipado com as seguintes leis adicionais:

1. Comutatividade aditiva: $$$x + y = y + x$
2. Distribuição à direita: $$$(x + y) \ vezes z = (x \ vezes z) + (y \ vezes z)$
3. Distribuição à esquerda: $$$x \ times (y + z) = (x \ times y) + (x \ times z)$
4. A presença de zero à direita: $$$x \ vezes zero = zero$
5. A presença de zero à esquerda: $$$zero \ vezes x = zero$

Para definir a semirrada correspondente da classe de tipo, combine AdditiveMonoid e MultiplicativeMonoid :

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

Agora que temos o Semiring , podemos usá-lo com vários tipos numéricos: Int , Long , BigDecimal etc., mas vale realmente a pena o artigo inteiro sobre half rings? Acontece que muitas outras coisas também são meios-anéis, incluindo valores lógicos, conjuntos e até animações .

Gostaria de observar que é possível formar um homomorfismo semi-anel de muitos tipos no número total de possíveis representantes desses tipos. O que isso significa? Seja paciente e tentarei explicar o que quero dizer.

Números cardinais

Vamos começar com o que geralmente se entende por número cardinal. Cada tipo corresponde ao número de valores que os representantes desse tipo podem assumir. Por exemplo, o tipo Boolean tem um número cardinal $$$2$ porque possui apenas dois valores possíveis: true e false .

Então, no Boolean - $$$2$ , mas quantos outros tipos? Byte - $$$2 ^ 8$ Short - $$$2 ^ {16}$ , na Int - $$$2 ^ {32}$ e Long $$$2 ^ {64}$ . E as cordas? String é um tipo formalmente ilimitado e teoricamente possui um número infinito de valores (na prática, é claro, não temos memória infinita, portanto o número específico dependerá da configuração do computador).

Para que outros tipos podemos determinar seu número cardinal? Dois exemplos bastante simples: Unit , que possui exatamente um representante, e Nothing , que é o limite inferior de todos os tipos possíveis no Scala e, portanto, possui $$$0$ valores possíveis. Ou seja, você nunca pode criar um valor Nothing , que corresponde a um número cardinal $$$0$ .

Ótimo, agora você pode tentar expressar isso no código. Podemos criar uma classe de tipo que pode nos fornecer o número total de valores do tipo correspondente.

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

Agora tente criar várias instâncias dessa classe:

 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 } 

[ Nota: os valores fornecidos também podem ser declarados como valores implicit val ]

Vamos experimentá-los no REPL :

 scala> Cardinality.of[Int] res11: BigInt = 4294967296 scala> Cardinality.of[Unit] res12: BigInt = 1 scala> Cardinality.of[Long] res13: BigInt = 18446744073709551616 

Ótimo, mas é tudo muito simples, e o ADT ? Podemos lidar com eles dessa maneira? Acontece que podemos, precisamos apenas entender como lidar com as somas e produtos mais simples dos tipos. Para começar, considere o produto mais simples dos tipos: (Boolean, Byte)

Quantos representantes desse tipo? Sabemos que os Boolean $$$2$ e Byte $$$256$ . Assim, números de $$$-128$ antes $$$127$ combinado com true ou false . Acontece $$$512$ valores únicos.

$$$512$ parece $$$256$ vezes $$$2$ então talvez você só precise multiplicar o número de valores do primeiro tipo pelo número de valores do segundo? Se você verificar isso com o restante dos exemplos, verifique se isso é verdade. Vamos imaginar isso como uma instância de uma classe de tipo:

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

Agora considere um exemplo de uma soma de tipos: Either[Boolean, Byte] . Nesse caso, a resposta é ainda mais óbvia, já que o valor desse tipo (de fato) pode ser Boolean ou Byte ; portanto, basta adicionar os números cardinais. Então, Either[Boolean, Byte ] deveria ter $$ representantes.

Vamos expressá-lo da mesma maneira no código e confirmar os resultados no 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 

Consequentemente, para a soma dos tipos, os números cardinais são adicionados e para o produto, eles são multiplicados. Isso é lógico, considerando seus nomes.

Então, e o homomorfismo discutido anteriormente? Um homomorfismo é um mapeamento de preservação de estrutura entre duas estruturas algébricas do mesmo tipo (neste caso, semirriscos).

Isso significa que, para qualquer $$$x$ , $$$y$ e homomorfismo $$$f$ nós temos:

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

As últimas expressões podem parecer bastante abstratas, mas estão diretamente relacionadas ao que acabamos de fazer. Se "adicionarmos" dois tipos de Byte e Boolean , obteremos E Either[Byte, Boolean] e, se aplicarmos o homomorfismo da cardinality , obteremos $$$258$ . Isso é equivalente à aplicação de cardinality em Byte e Boolean separadamente, seguida pela adição dos resultados.

Obviamente, o mesmo se aplica à multiplicação e ao produto dos tipos. No entanto, ainda nos falta algo para o meio-anel correto, pois mencionamos apenas adição e multiplicação, mas não os elementos individuais correspondentes.

Como já vimos, o tipo Unit um representante e o tipo Nothing não Nothing nenhum. Podemos usar esses dois tipos para formar um meio anel?

Vamos tentar! Se Unit for uma unidade de multiplicação, o produto de qualquer tipo com Unit deverá ser equivalente ao primeiro tipo. Naturalmente, isso é feito, pois podemos mapear facilmente algo da descarga (Int, Unit) para Int e vice-versa sem perda, para que o número cardinal permaneça inalterado.

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

E o Nothing ? Como essa é uma unidade de adição, a soma de qualquer tipo com Nothing deve ser equivalente ao mesmo tipo. O Either[Nothing, A] corresponde a A ? Sim Como Nothing não tem significado, Either[Nothing, A] só pode estar Right e, como resultado, apenas A , portanto esses tipos são equivalentes.

Também precisamos verificar a correção de zero pela multiplicação: qualquer número multiplicado pela unidade adicionando zero deve corresponder a zero . Como Nothing é nossa unidade de adição, um produto de tipos como (Int, Nothing) deve ser equivalente a Nothing . Isso é feito porque não podemos criar um valor do tipo Nothing e, como resultado, uma tupla contendo esse valor.

Vamos verificar como isso se relaciona com os números cardinais.

Unidade de adição:

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

Absorção por zero:

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

Resta verificar a distributividade. No contexto dos tipos, isso significa que (A, Either[B, C]) deve corresponder a Either[(A, B), (A, C)] . Se você verificar, esses dois tipos serão realmente equivalentes.

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

Estruturas algébricas de ordem superior

Alguns já devem ter ouvido falar da classe do tipo Semigroupal . Mas por que é assim chamado e como se relaciona com o Semigroup ? Para começar, vamos dar uma olhada no próprio Semigroupal :

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

Há uma certa semelhança com o Semigroup : dois valores são combinados e a operação correspondente deve ser associativa (semelhante ao Semigroup ).

Até agora, tudo bem, mas o nome da função product pouco confuso. É lógico, já que combinamos A e B em uma tupla, que é um produto dos tipos, mas se usarmos o produto, talvez não seja um Semigroupal arbitrário, mas multiplicativo? Vamos renomeá-lo.

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

Agora vamos ver como seria a adição do Semigroupal . Naturalmente, tudo o que precisamos mudar é um produto de tipos para a soma:

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

Parece bom - podemos adicionar unidades para obter o Monoidal ? Claro que podemos! Novamente, será Nothing e Unit para a soma e o produto, respectivamente:

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

Agora temos essas classes de tipo, mas como podemos usá-las? Bem, declaro com confiança que eles já são usados ​​na biblioteca de gatos , mas com nomes diferentes.

O que poderia ser como essas classes? Para começar, dê uma olhada na função sum e tente encontrar algo semelhante ao AdditiveSemigroupal . Como os análogos dessas classes para tipos de ordem inferior têm operadores simbólicos correspondentes, vamos adicionar esse operador ao AdditiveSemigroupal .

Como essa é uma soma, é provável que este operador contenha + e indique que a operação está sendo executada em algum contexto. Seria ideal usar algo como [+] , mas esse é um identificador inválido, portanto, tente <+> .

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

A função <+> já existe em gatos como um alias para combineK , que pode ser encontrada no SemigroupK , mas se comporta de maneira diferente. Leva dois F[A] para a entrada e retorna F[A] - não exatamente como o que temos.

Ou similar? De fato, essas duas funções coincidem e podemos definir uma através da outra na presença de um functor:

 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) } 

Como o AdditiveSemigroupal equivalente ao SemigroupK , é possível que o AdditiveMonoidal igual ao MonoidK ? Sim, e é fácil de mostrar. MonoidK complementado pela função empty :

 def empty[A]: F[A] 

Essa função usa um quantificador universal para A , ou seja, funciona para qualquer A , o que significa que, na realidade, ela não pode operar com nenhum A específico e, portanto, é equivalente a F[Nothing] no AdditiveMonoidal .

Bem, encontramos análogos para classes aditivas e já sabemos que o MultiplicativeSemigroupal equivalente a cats.Semigroupal . Tudo o que resta para nós é encontrar o equivalente a MultiplicativeMonoidal .

Eu trapaceio um pouco e digo que esse equivalente é Applicative . Ele adiciona uma função pure que pega A e retorna F[A] . MultiplicativeMonoidal por sua vez, possui uma função de unit que não aceita parâmetros e retorna F[Unit] . Como passar de um para outro? A resposta novamente implica o uso de um functor:

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

Applicative usa um functor covariante, mas no caso geral, também podemos usar estruturas invariantes e contravariantes. Além disso, o Applicative inclui <*> como um alias para a combinação de product e map , que parece outra pista de que essa é uma classe multiplicativa e que a intuição não falhou.

Agora, nos gatos , temos <+> e <*> , mas existe uma classe de tipo que os combina, semelhante a como o Semiring combina + e * ? Sim, e se chama Alternative . É herdado de Applicative e MonoidK . Para ser consistente, chamaremos de Semiringal :

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

Ótimo, agora temos Semiring e sua contrapartida para tipos de pedidos mais altos. Infelizmente, o primeiro não está em gatos , mas talvez apareça em versões futuras.

Se estivesse disponível, poderíamos inferir Semiring para qualquer Alternative semelhante à Monoid de MonoidK para MonoidK ou Applicative . Além disso, poderíamos transformar o Semiring novamente em Alternative usando Const , semelhante a transformar Monoid em Applicative .

Em conclusão, vamos ver como essa transformação pode ser escrita:

 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) } 

Conclusão

Anéis e meios anéis são estruturas algébricas muito interessantes e, mesmo que você não tenha pensado nisso, provavelmente já os usou. Este post foi escrito para mostrar como o Applicative e o MonoidK relacionam com o Monoid , por que os tipos de dados algébricos formam um meio-anel e como essas estruturas algébricas se espalham no Scala e em outras linguagens de programação. Para mim, pessoalmente, a percepção de como isso está interconectado e forma uma simetria muito interessante foi apenas uma explosão cerebral, e espero que este post possa ajudar a encontrar paralelos interessantes semelhantes em Cats e outras bibliotecas com base em várias abstrações matemáticas. Você pode encontrar mais material sobre esse tópico aqui .

Adição

Neste post, fiquei em silêncio sobre a comutatividade no registro das classes de tipo. A comutatividade é uma propriedade muito importante para as semirrepções e o código deve refletir essa propriedade. No entanto, como o post já contém muitas definições, complementá-lo com várias outras classes de tipo comutativo que não fazem nada além de introduzir novas leis pareciam redundantes e distraíam o principal objetivo do post.

Além disso, concentrei-me nos números cardinais apenas daquelas classes que precisávamos, mas, para completar, você pode adicionar definições de Cardinality para coisas como 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]