El cuento de los medios anillos

Hola Habr! Les traigo a su atención una traducción del artículo "Un cuento sobre Semirings" de Luka Jacobowitz.

Alguna vez se preguntó por qué la suma de tipos se llama la suma de tipos. ¿O tal vez siempre quiso saber por qué el operador <*> está escrito de esta manera? ¿Y qué tiene esto que ver con los medios anillos? Interesado por favor pida un corte!

Este artículo es una traducción de una publicación de blog Typelevel de Luke Jakobovic. Para su mejor percepción, uno necesita al menos un conocimiento superficial del lenguaje Scala y su ecosistema (incluida la biblioteca de gatos) y el conocimiento de los conceptos básicos de álgebra abstracta: semigrupo, monoide, etc.

Estructuras algebraicas

Muchos de nosotros sabemos sobre monoides y semigrupos e incluso los usamos. Estas estructuras tienen propiedades que le permiten aplicarlas directamente para obtener un mayor nivel de abstracción (si no las conoce, puede leer la documentación de la biblioteca de gatos ). Sin embargo, a veces un tipo de datos tiene más de un monoide o semigrupo. Un ejemplo obvio son los diversos tipos numéricos, donde la multiplicación y la suma forman dos monoides completos.

En álgebra abstracta, hay una clase separada de estructuras con dos monoides que interactúan de cierta manera. Esta clase es medios anillos. Dado que los monoides se usan a menudo para describir tipos numéricos, generalmente se dividen en multiplicativos y aditivos. Al igual que en el caso de los números, las leyes de un semiring determinan que la multiplicación es distributiva por la suma, y ​​la multiplicación de cualquier número por la unidad por la suma - cero - da cero.

Hay varias formas de presentar esto a medida que las clases de tipos y las diferentes bibliotecas lo hacen a su manera, pero veamos cómo se hace esto en un proyecto de álgebra . La base en él son AdditiveSemigroup y MultiplicativeSemigroup .

[ Nota: dado que el nombre "clase de tipo" no se arraigó en ruso, su versión en inglés se usará más tarde - clase 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: la anotación @typeclass del proyecto simulacrum le permite generar automáticamente métodos utilizados con frecuencia para las clases de tipos y no afecta el componente lógico del código ]

En este caso, el semiring ( Semiring ) es un monoide aditivo ( AdditiveMonoid ), combinado con el monoide multiplicativo ( MultiplicativeMonoid ) y equipado con las siguientes leyes adicionales:

1. Conmutatividad aditiva: $$$x + y = y + x$
2. Distribución a la derecha: $$$(x + y) \ times z = (x \ times z) + (y \ times z)$
3. Distribución a la izquierda: $$$x \ times (y + z) = (x \ times y) + (x \ times z)$
4. La presencia de cero a la derecha: $$$x \ veces cero = cero$
5. La presencia de cero a la izquierda: $$$cero \ veces x = cero$

Para establecer el semired correspondiente de la clase de tipo, combine AdditiveMonoid y MultiplicativeMonoid :

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

Ahora que tenemos Semiring , podemos usarlo con varios tipos numéricos: Int , Long , BigDecimal , etc., pero ¿realmente vale la pena todo el artículo sobre medios anillos? Resulta que muchas otras cosas también son medios anillos, incluidos valores lógicos, conjuntos e incluso animaciones .

Me gustaría señalar que es posible formar un homomorfismo de semi-anillo de muchos tipos en el número total de posibles representantes de estos tipos. ¿Qué significa esto? Bueno, sea paciente, y trataré de explicar lo que quiero decir.

Números cardinales

Comencemos con lo que generalmente se entiende por un número cardinal. Cada tipo corresponde al número de valores que los representantes de este tipo pueden tomar. Por ejemplo, el tipo Boolean tiene un número cardinal $$$2$ porque solo tiene dos valores posibles: true y false .

Entonces, en Boolean - $$$2$ , pero cuantos otros tipos? Byte $$$2 ^ 8$ , Short - $$$2 ^ {16}$ , en Int - $$$2 ^ {32}$ y Long $$$2 ^ {64}$ . ¿Qué pasa con las cuerdas? String es un tipo formalmente ilimitado y teóricamente tiene un número infinito de valores (en la práctica, por supuesto, no tenemos memoria infinita, por lo que el número específico dependerá de la configuración de la computadora).

¿Para qué otros tipos podemos determinar su número cardinal? Dos ejemplos bastante simples: Unit , que tiene exactamente un representante, y Nothing , que es el límite inferior de todos los tipos posibles en Scala y, en consecuencia, tiene $$$0$ posibles valores Es decir, nunca puede crear un valor de Nothing , que corresponde a un número cardinal $$$0$ .

Genial, ahora puedes intentar expresar esto en código. Podemos crear una clase de tipo que nos puede dar el número total de valores del tipo correspondiente.

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

Ahora intente crear varias instancias de esta clase:

 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: los valores dados también pueden declararse como implicit val ]

Probémoslos en el REPL :

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

Genial, pero todo es muy simple, ¿qué pasa con ADT ? ¿Podemos manejarlos de esta manera? Resulta que podemos, solo tenemos que entender cómo manejar las sumas y productos de tipos más simples. Para comenzar, considere el producto de tipos más simple: (Boolean, Byte)

¿Cuántos representantes de este tipo? Sabemos que los Boolean $$$2$ y Byte $$$256$ . Por lo tanto, los números de $$$-128$ antes $$$127$ combinado con true o false . Resulta $$$512$ valores únicos

$$$512$ parece que $$$256$ tiempos $$$2$ , ¿entonces quizás solo necesite multiplicar el número de valores del primer tipo por el número de valores del segundo? Si verifica esto con el resto de los ejemplos, asegúrese de que esto sea cierto. Imaginemos esto como una instancia de una clase de tipo:

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

Ahora considere un ejemplo de una suma de tipos: Either[Boolean, Byte] . En este caso, la respuesta es aún más obvia, ya que el valor de este tipo (de hecho) puede ser Boolean o Byte , por lo que es suficiente simplemente agregar los números cardinales. Entonces, Either[Boolean, Byte ] debería tener $$$256 + 2 = $ 25$ representantes.

Expresémoslo de la misma manera en el código y confirmemos los resultados en 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 

En consecuencia, para la suma de tipos se suman números cardinales y para el producto se multiplican. Esto es lógico dados sus nombres.

Entonces, ¿qué pasa con el homomorfismo discutido anteriormente? Un homomorfismo es un mapeo que preserva la estructura entre dos estructuras algebraicas del mismo tipo (en este caso, semirrelaciones).

Esto significa que para cualquier $$$x$ , $$$y$ y homomorfismo $$$f$ tenemos:

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

Las últimas expresiones pueden parecer bastante abstractas, pero están directamente relacionadas con lo que acabamos de hacer. Si "agregamos" dos tipos de Byte y Boolean , entonces obtenemos Either[Byte, Boolean] , y si le aplicamos el homomorfismo de cardinality , obtenemos $$$258$ . Esto es equivalente a aplicar la cardinality a Byte y Boolean separado, seguido de la suma de los resultados.

Por supuesto, lo mismo se aplica a la multiplicación y al producto de tipos. Sin embargo, todavía nos falta algo para el medio anillo correcto, ya que mencionamos solo la suma y la multiplicación, pero no los elementos individuales correspondientes.

Como ya hemos visto, el tipo Unit un representante, y el tipo Nothing ninguno. ¿Podemos usar estos dos tipos para formar un medio anillo?

¡Intentémoslo! Si la Unit es una unidad de multiplicación, entonces el producto de cualquier tipo con Unit debería ser equivalente al primer tipo. Naturalmente, esto se hace, ya que podemos mapear fácilmente algo de la descarga (Int, Unit) a Int y viceversa sin pérdida, de modo que el número cardinal permanezca sin cambios.

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

¿Qué hay de Nothing ? Como se trata de una unidad de suma, la suma de cualquier tipo con Nothing debe ser equivalente al mismo tipo. ¿ Either[Nothing, A] coincide con A ? Si! Dado que Nothing no tiene significado, Either[Nothing, A] solo puede ser Right y, como resultado, solo A , por lo que estos tipos son equivalentes.

También necesitamos verificar la corrección del cero por multiplicación: cualquier número multiplicado por la unidad al sumar zero debe coincidir con zero . Como Nothing es nuestra unidad de adición, un producto de tipos como (Int, Nothing) debería ser equivalente a Nothing . Esto se hace porque no podemos crear un valor de tipo Nothing y, como resultado, una tupla que contiene dicho valor.

Veamos cómo se relaciona esto con los números cardinales.

Unidad de adición:

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

Absorción por cero:

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

Queda por verificar la distributividad. En el contexto de los tipos, esto significa que (A, Either[B, C]) debe coincidir con Either[(A, B), (A, C)] . Si marca, entonces estos dos tipos serán equivalentes.

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

Estructuras algebraicas de orden superior.

Es posible que algunos ya hayan oído hablar de la clase de tipo Semigroupal . Pero, ¿por qué se llama así y cómo se relaciona con Semigroup ? Para comenzar, echemos un vistazo a Semigroupal :

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

Hay una cierta similitud con Semigroup : se combinan dos valores y la operación correspondiente debe ser asociativa (similar a Semigroup ).

Hasta ahora, todo bien, pero el nombre del product poco confuso. Es lógico, ya que combinamos A y B en una tupla, que es un producto de tipos, pero si usamos el producto, ¿tal vez no es un Semigroupal arbitrario, sino multiplicativo? Cambiemos el nombre.

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

Ahora veamos qué Semigroupal podría tener Semigroupal . Naturalmente, todo lo que tenemos que cambiar es un producto de tipos para la suma:

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

Se ve bien, ¿podemos agregar unidades para obtener Monoidal ? ¡Por supuesto que podemos! Esto nuevamente será Nothing y Unit para la suma y el producto, respectivamente:

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

Ahora tenemos estas clases de tipos, pero ¿cómo podemos usarlas? Bueno, declaro con confianza que ya se usan en la biblioteca de gatos , pero con diferentes nombres.

¿Qué podría ser como estas clases? Para comenzar, eche un vistazo a la función de sum e intente encontrar algo similar a AdditiveSemigroupal . Como los análogos de estas clases para los tipos de orden inferior tienen operadores simbólicos correspondientes, agreguemos dicho operador a AdditiveSemigroupal .

Como se trata de una suma, lo más probable es que este operador contenga + e indique que la operación se realiza en algún contexto. Sería ideal usar algo como [+] , pero este es un identificador no válido, así que intente <+> lugar.

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

La función <+> ya existe en los gatos como un alias para combineK , que se puede encontrar en SemigroupK , pero se comporta de manera diferente. Se necesitan dos F[A] para la entrada y devuelve F[A] , no exactamente como lo que tenemos.

O similar? De hecho, estas dos funciones coinciden y podemos definir una a través de la otra en presencia de un 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) } 

Dado que AdditiveSemigroupal equivalente a SemigroupK , ¿es posible que AdditiveMonoidal mismo que MonoidK ? Sí, y es fácil de mostrar. MonoidK complementa con la función empty :

 def empty[A]: F[A] 

Esta función utiliza un cuantificador universal para A , es decir, funciona para cualquier A , lo que significa que en realidad no puede operar en ninguna A específica y, por lo tanto, es equivalente a F[Nothing] en AdditiveMonoidal .

Bueno, encontramos análogos para clases aditivas y ya sabemos que MultiplicativeSemigroupal equivalente a los cats.Semigroupal . cats.Semigroupal . Todo lo que nos queda es encontrar el equivalente de MultiplicativeMonoidal .

Hago un poco de trampa y digo que este equivalente es Applicative . Agrega una función pure que toma A y devuelve F[A] . MultiplicativeMonoidal a su vez, tiene una función de unit que no toma parámetros y devuelve F[Unit] . ¿Cómo pasar de uno a otro? La respuesta nuevamente implica usar un functor:

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

Applicative usa un functor covariante, pero en el caso general, también podemos usar estructuras invariantes y contravariantes. Además de esto, Applicative incluye <*> como un alias para la combinación de product y map , que parece otra pista de que se trata de una clase multiplicativa y la intuición no nos ha fallado.

Ahora en gatos tenemos <+> y <*> , pero ¿hay una clase de tipo que los combine, similar a cómo Semiring combina + y * ? Sí, y se llama Alternative . Se hereda de Applicative y MonoidK . Para ser coherentes, lo llamaremos Semiringal :

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

Genial, ahora tenemos Semiring , y su contraparte para los tipos de orden superior. Desafortunadamente, el primero no está en los gatos , pero quizás aparezca en futuras versiones.

Si estuviera disponible, podríamos inferir Semiring para cualquier Alternative similar a inferir MonoidK para MonoidK o Applicative . Además, podríamos convertir Semiring nuevamente en Alternative usando Const , similar a convertir Monoid en Applicative .

En conclusión, veamos cómo se puede escribir esta transformación:

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

Conclusión

Los anillos y los medios anillos son estructuras algebraicas muy interesantes, e incluso si no lo pensaste, lo más probable es que ya los hayas usado. Esta publicación fue escrita para mostrar cómo Applicative y MonoidK relacionan con Monoid , por qué los tipos de datos algebraicos forman un medio anillo y cómo estas estructuras algebraicas se propagan en Scala y otros lenguajes de programación. Para mí personalmente, la comprensión de cómo esto está interconectado y forma una simetría muy interesante fue solo una explosión cerebral, y espero que esta publicación pueda ayudar a encontrar paralelos interesantes similares en Cats y otras bibliotecas basadas en varias abstracciones matemáticas. Puede encontrar más material sobre este tema aquí .

Además

En esta publicación, guardé silencio sobre la conmutatividad en el registro de las clases de tipos. La conmutatividad es una propiedad muy importante para semirrelaciones y el código debe reflejar esta propiedad. Sin embargo, dado que la publicación ya contiene muchas definiciones, complementarla con varias clases de tipos conmutativas más que no hacen más que introducir nuevas leyes parecía redundante y distrae el propósito principal de la publicación.

Además, me concentré en los números cardinales de solo aquellas clases que necesitábamos, pero para completar, puede agregar definiciones de Cardinality para cosas 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]