Le conte des demi-anneaux

Bonjour, Habr! J'attire votre attention sur une traduction de l'article "Un conte sur Semirings" de Luka Jacobowitz.

Jamais demandé pourquoi la somme des types est appelée la somme des types. Ou peut-être avez-vous toujours voulu savoir pourquoi l'opérateur <*> est écrit de cette façon? Et qu'est-ce que cela a à voir avec les demi-anneaux? Intéressé, veuillez demander une coupe!

Cet article est une traduction d'un article de blog de Typelevel par Luke Jakobovic. Pour sa meilleure perception, il faut au moins une familiarité superficielle avec le langage Scala et son écosystème (y compris la bibliothèque des chats) et une connaissance des concepts de base de l'algèbre abstraite: un semi-groupe, un monoïde, etc.

Structures algébriques

Beaucoup d'entre nous connaissent les monoïdes et les semi-groupes et les utilisent même. Ces structures ont des propriétés qui vous permettent de les appliquer directement pour obtenir un niveau d'abstraction plus élevé (si vous ne les connaissez pas, vous pouvez lire la documentation de la bibliothèque des chats ). Cependant, parfois un type de données a plus d'un monoïde ou semi-groupe. Un exemple évident est les divers types numériques, où la multiplication et l'addition forment deux monoïdes complets.

En algèbre abstraite, il existe une classe distincte de structures avec deux monoïdes interagissant d'une certaine manière. Cette classe est demi-anneaux. Étant donné que les monoïdes sont souvent utilisés pour décrire les types numériques, ils sont généralement divisés en multiplicatifs et additifs. Comme dans le cas des nombres, les lois d'un semi-cercle déterminent que la multiplication est distributive par addition, et la multiplication de tout nombre par unité par addition - zéro - donne zéro.

Il existe différentes façons de présenter cela comme les classes de types et les différentes bibliothèques le font à leur manière, mais regardons comment cela se fait dans un projet d' algèbre . La base en elle est AdditiveSemigroup et MultiplicativeSemigroup .

[ Remarque: étant donné que le nom "type class" n'a pas pris racine en russe, sa version anglaise sera utilisée ultérieurement - 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 } 

[ Remarque: l'annotation @typeclass du projet simulacrum vous permet de générer automatiquement des méthodes fréquemment utilisées pour les classes de type et n'affecte pas la composante logique du code ]

Dans ce cas, le semiring est un monoïde additif ( AdditiveMonoid ), combiné avec un monoïde multiplicatif ( MultiplicativeMonoid ) et équipé des lois supplémentaires suivantes:

1. Commutativité additive: $$$x + y = y + x$
2. Distribution à droite: $$$(x + y) \ times z = (x \ times z) + (y \ times z)$
3. Distribution à gauche: $$$x \ times (y + z) = (x \ times y) + (x \ times z)$
4. La présence de zéro à droite: $$$x \ fois zéro = zéro$
5. La présence de zéro à gauche: $$$zero \ times x = zero$

Pour définir le semiring correspondant de la classe de type, combinez AdditiveMonoid et MultiplicativeMonoid :

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

Maintenant que nous avons Semiring , nous pouvons l'utiliser avec différents types numériques: Int , Long , BigDecimal , etc., mais vaut-il vraiment l'article complet sur les demi-anneaux? Il s'avère que beaucoup d'autres choses sont également des demi-anneaux, y compris des valeurs logiques, des ensembles et même des animations .

Je voudrais noter qu'il est possible de former un homomorphisme semi-circulaire à partir de nombreux types dans le nombre total de représentants possibles de ces types. Qu'est-ce que cela signifie? Eh bien, soyez patient et je vais essayer d'expliquer ce que je veux dire.

Nombres cardinaux

Commençons par ce que l'on entend généralement par un nombre cardinal. Chaque type correspond au nombre de valeurs que les représentants de ce type peuvent prendre. Par exemple, le type Boolean a un nombre cardinal $$$2$ car il n'a que deux valeurs possibles: true et false .

Donc, chez Boolean - $$$2$ , mais combien d'autres types? Byte - $$ , Short - $$$2 ^ {16}$ , chez Int - $$$2 ^ {32}$ et Long $$$2 ^ {64}$ . Et les cordes? String est un type formellement illimité et a théoriquement un nombre infini de valeurs (en pratique, bien sûr, nous n'avons pas de mémoire infinie, donc le nombre spécifique dépendra de la configuration de l'ordinateur).

Pour quels autres types pouvons-nous déterminer leur nombre cardinal? Deux exemples assez simples: Unit , qui a exactement un représentant, et Nothing , qui est la borne inférieure de tous les types possibles dans Scala et a en conséquence $$$0$ valeurs possibles. Autrement dit, vous ne pouvez jamais créer une valeur de Nothing , ce qui correspond à un nombre cardinal $$$0$ .

Très bien, vous pouvez maintenant essayer d'exprimer cela dans le code. Nous pouvons créer une classe de type qui peut nous donner le nombre total de valeurs du type correspondant.

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

Essayez maintenant de créer plusieurs instances de cette 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 } 

[ Remarque: les valeurs données peuvent également être déclarées comme des valeurs implicit val ]

Essayons-les dans le REPL :

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

Génial, mais tout est très simple, qu'en est-il d' ADT ? Pouvons-nous les gérer de cette manière? Il s'avère que nous pouvons, nous avons juste besoin de comprendre comment gérer les sommes et les produits les plus simples des types. Pour commencer, considérez le produit le plus simple des types: (Boolean, Byte)

Combien de représentants de ce type? Nous savons que Boolean $$$2$ et Byte $$ . Ainsi, les chiffres de $$$-128$ avant $$$127$ combiné avec true ou false . Il s'avère $$ des valeurs uniques.

$$ ressemble $$ fois $$$2$ , alors peut-être avez-vous juste besoin de multiplier le nombre de valeurs du premier type par le nombre de valeurs du second? Si vous vérifiez cela avec le reste des exemples, assurez-vous que cela est vrai. Imaginons cela comme une instance d'une classe de type:

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

Considérons maintenant un exemple d'une somme de types: Either[Boolean, Byte] . Dans ce cas, la réponse est encore plus évidente, car la valeur de ce type (en fait) peut être Boolean ou Byte , il suffit donc d'ajouter simplement les nombres cardinaux. Donc, Either[Boolean, Byte ] devrait avoir $$ représentants.

Exprimons-le de la même manière dans le code et confirmons les résultats dans 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 

Par conséquent, pour la somme des types, les nombres cardinaux sont ajoutés et pour le produit, ils sont multipliés. C'est logique étant donné leurs noms.

Alors qu'en est-il de l'homomorphisme discuté plus tôt? Un homomorphisme est une cartographie préservant la structure entre deux structures algébriques du même type (dans ce cas, les demi-anneaux).

Cela signifie que pour tout $$$x$ , $$$y$ et l'homomorphisme $$$f$ nous avons:

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

Ces dernières expressions peuvent sembler assez abstraites, mais elles sont directement liées à ce que nous venons de faire. Si nous «ajoutons» deux types d' Byte et Boolean , alors nous obtenons Either[Byte, Boolean] , et si nous lui appliquons l'homomorphisme de cardinality , nous obtenons $$ . Cela équivaut à appliquer séparément la cardinality à l' Byte et à la valeur Boolean , puis à additionner les résultats.

Bien sûr, la même chose s'applique à la multiplication et au produit des types. Néanmoins, il nous manque encore quelque chose pour le demi-anneau correct, car nous n'avons mentionné que l'addition et la multiplication, mais pas les éléments individuels correspondants.

Comme nous l'avons déjà vu, le type Unit un représentant et le type Nothing n'en Nothing aucun. Pouvons-nous utiliser ces deux types pour former un demi-anneau?

Essayons! Si Unit est une unité de multiplication, alors le produit de tout type avec Unit doit être équivalent au premier type. Naturellement, cela est fait, car nous pouvons facilement mapper quelque chose de la décharge (Int, Unit) à Int et vice versa sans perte, de sorte que le nombre cardinal reste inchangé.

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

Et Nothing ? Puisqu'il s'agit d'une unité d'addition, la somme de tout type avec Nothing doit être équivalente au même type. Est-ce que Either[Nothing, A] correspond à A ? Oui! Puisque Nothing n'a de sens, Either[Nothing, A] ne peut être que Right et, par conséquent, seulement A , donc ces types sont équivalents.

Nous devons également vérifier l'exactitude de zéro par multiplication: tout nombre multiplié par l'unité en ajoutant zero doit correspondre à zero . Étant donné que Nothing est notre unité d'addition, un produit de types tels que (Int, Nothing) doit être équivalent à Nothing . Cela est dû au fait que nous ne pouvons pas créer une valeur de type Nothing et, par conséquent, un tuple contenant une telle valeur.

Vérifions comment cela se rapporte aux nombres cardinaux.

Unité d'addition:

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

Absorption par zéro:

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

Reste à vérifier la distributivité. Dans le contexte des types, cela signifie que (A, Either[B, C]) doit correspondre à Either[(A, B), (A, C)] . Si vous cochez, ces deux types seront en fait équivalents.

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

Structures algébriques d'ordre supérieur

Certains ont peut-être déjà entendu parler de la classe de type Semigroupal . Mais pourquoi est-il ainsi appelé et comment est-il lié à Semigroup ? Pour commencer, jetons un œil à Semigroupal lui-même:

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

Il existe une certaine similitude avec Semigroup : deux valeurs sont combinées, et l'opération correspondante doit être associative (similaire à Semigroup ).

Jusqu'à présent, tout va bien, mais le nom de la fonction product peu déroutant. C'est logique, puisque nous combinons A et B en un tuple, qui est un produit de types, mais si nous utilisons le produit, ce n'est peut-être pas un Semigroupal arbitraire, mais multiplicatif? Renommons-le.

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

Voyons maintenant à quoi pourrait ressembler un ajout Semigroupal . Naturellement, tout ce que nous devons changer est un produit de types pour la somme:

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

Cela semble bon - pouvons-nous ajouter des unités pour obtenir Monoidal ? Bien sûr que nous le pouvons! Ce sera à nouveau Nothing et Unit pour la somme et le produit, respectivement:

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

Nous avons maintenant ces classes de types, mais comment pouvons-nous les utiliser? Eh bien, je déclare avec confiance qu'ils sont déjà utilisés dans la bibliothèque des chats , mais sous des noms différents.

À quoi pourraient ressembler ces cours? Pour commencer, jetez un œil à la fonction sum et essayez de trouver quelque chose de similaire à AdditiveSemigroupal . Étant donné que les analogues de ces classes pour les types d'ordre inférieur ont des opérateurs symboliques correspondants, ajoutons un tel opérateur à AdditiveSemigroupal .

Comme il s'agit d'une somme, cet opérateur devrait très probablement contenir + et indiquer que l'opération est effectuée dans un certain contexte. Il serait idéal d'utiliser quelque chose comme [+] , mais il s'agit d'un identifiant non valide, essayez donc <+> place.

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

La fonction <+> existe déjà chez les chats comme alias pour combineK , qui peut être trouvée dans SemigroupK , mais elle se comporte différemment. Il faut deux F[A] à l'entrée et renvoie F[A] - pas exactement comme ce que nous avons.

Ou similaire? En fait, ces deux fonctions coïncident et nous pouvons définir l'une à travers l'autre en présence d'un foncteur:

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

Puisque AdditiveSemigroupal équivalent à SemigroupK , est-il possible que AdditiveMonoidal identique à MonoidK ? Oui, et c'est facile à montrer. MonoidK complété par la fonction empty :

 def empty[A]: F[A] 

Cette fonction utilise un quantificateur universel pour A , c'est-à-dire qu'elle fonctionne pour tout A , ce qui signifie qu'en réalité, elle ne peut pas fonctionner sur un A spécifique et est donc équivalente à F[Nothing] dans AdditiveMonoidal .

Eh bien, nous avons trouvé des analogues pour les classes d'additifs et savons déjà que MultiplicativeSemigroupal équivalent aux cats.Semigroupal . Il ne nous reste plus qu'à trouver l'équivalent de MultiplicativeMonoidal .

Je triche un peu et dis que cet équivalent est Applicative . Il ajoute une fonction pure qui prend A et retourne F[A] . MultiplicativeMonoidal à son tour, a une fonction d' unit qui ne prend aucun paramètre et renvoie F[Unit] . Comment passer de l'un à l'autre? La réponse implique à nouveau d'utiliser un foncteur:

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

Applicative utilise un foncteur covariant, mais dans le cas général, nous pouvons également utiliser des structures invariantes et contravariantes. En plus de cela, Applicative inclut <*> comme alias pour la combinaison du product et de la map , ce qui ressemble à un autre indice qu'il s'agit d'une classe multiplicative et l'intuition ne nous a pas échoué.

Maintenant, chez les chats, nous avons <+> et <*> , mais existe-t-il une classe de type qui les combine, semblable à la façon dont Semiring combine + et * ? Oui, et ça s'appelle Alternative . Il est hérité de Applicative et MonoidK . Pour être cohérent, nous l'appellerons Semiringal :

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

Semiring , nous avons maintenant Semiring et son homologue pour les types d'ordre supérieur. Malheureusement, le premier n'est pas chez les chats , mais peut-être qu'il apparaîtra dans les futures versions.

S'il était disponible, nous pourrions déduire Semiring pour n'importe quelle Alternative similaire à inférer MonoidK pour MonoidK ou Applicative . De plus, nous pourrions transformer Semiring en Alternative utilisant Const , similaire à transformer Monoid en Applicative .

En conclusion, voyons comment cette transformation peut s'écrire:

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

Conclusion

Les anneaux et les demi-anneaux sont des structures algébriques très intéressantes, et même si vous n'y avez pas pensé, vous les avez probablement déjà utilisées. Cet article a été écrit pour montrer comment Applicative et MonoidK liés à Monoid , pourquoi les types de données algébriques forment un demi-anneau et comment ces structures algébriques se sont propagées dans Scala et d'autres langages de programmation. Pour moi personnellement, la réalisation de la façon dont cela est interconnecté et forme une symétrie très intéressante n'était qu'une explosion cérébrale, et j'espère que ce post peut aider à trouver des parallèles intéressants similaires dans Cats et d'autres bibliothèques basées sur diverses abstractions mathématiques. Vous pouvez trouver plus d'informations sur ce sujet ici .

Addition

Dans cet article, j'ai gardé le silence sur la commutativité dans l'enregistrement des classes de type. La commutativité est une propriété très importante pour les semirings et le code doit refléter cette propriété. Cependant, puisque le poste contient déjà de nombreuses définitions, le compléter avec plusieurs classes de type plus commutatif qui ne font rien mais introduire de nouvelles lois semblait redondant et distrait de l'objectif principal du poste.

De plus, je me suis concentré sur les nombres cardinaux des seules classes dont nous avions besoin, mais pour être complet, vous pouvez ajouter des définitions de Cardinality pour des choses comme 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]