Die Geschichte der halben Ringe

Hallo Habr! Ich mache Sie auf eine Übersetzung des Artikels "Eine Geschichte über Semirings" von Luka Jacobowitz aufmerksam.

Überhaupt gewundert, warum die Summe der Typen die Summe der Typen genannt wird. Oder wollten Sie schon immer wissen, warum der Operator <*> so geschrieben ist? Und was hat das mit halben Ringen zu tun? Interessiert bitte um einen Schnitt!

Dieser Artikel ist eine Übersetzung eines Typelevel-Blogposts von Luke Jakobovic. Für eine optimale Wahrnehmung benötigt man zumindest eine oberflächliche Vertrautheit mit der Scala-Sprache und ihrem Ökosystem (einschließlich der Katzenbibliothek) und Kenntnisse der Grundkonzepte der abstrakten Algebra: eine Halbgruppe, ein Monoid usw.

Algebraische Strukturen

Viele von uns kennen Monoide und Halbgruppen und verwenden sie sogar. Diese Strukturen haben Eigenschaften, mit denen Sie sie direkt anwenden können, um eine höhere Abstraktionsebene zu erhalten (wenn Sie nichts über sie wissen, können Sie die Dokumentation aus der Katzenbibliothek lesen). Manchmal hat ein Datentyp jedoch mehr als ein Monoid oder eine Halbgruppe. Ein offensichtliches Beispiel sind die verschiedenen numerischen Typen, bei denen Multiplikation und Addition zwei vollständige Monoide bilden.

In der abstrakten Algebra gibt es eine separate Klasse von Strukturen, bei denen zwei Monoide auf bestimmte Weise interagieren. Diese Klasse besteht aus halben Ringen. Da Monoide häufig zur Beschreibung numerischer Typen verwendet werden, werden sie normalerweise in multiplikative und additive unterteilt. Wie im Fall von Zahlen bestimmen die Gesetze eines Semirings, dass die Multiplikation durch Addition verteilend ist, und die Multiplikation einer beliebigen Zahl durch Einheit durch Addition - Null - ergibt Null.

Es gibt verschiedene Möglichkeiten, dies als Typklassen darzustellen, und verschiedene Bibliotheken tun dies auf ihre eigene Weise. Schauen wir uns jedoch an, wie dies in einem Algebra- Projekt geschieht. Die Basis darin sind AdditiveSemigroup und MultiplicativeSemigroup .

[ Hinweis: Da der Name "Typklasse" nicht auf Russisch verwurzelt ist, wird seine englische Version später verwendet - Typklasse ]

 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 } 

[ Hinweis: Mit der @ typeclass-Annotation aus dem Simulacrum-Projekt können Sie häufig verwendete Methoden für Typklassen automatisch generieren und haben keinen Einfluss auf die logische Komponente des Codes. ]

In diesem Fall ist das Semiring ( Semiring ) ein additives Monoid ( AdditiveMonoid ), das mit dem multiplikativen Monoid ( MultiplicativeMonoid ) kombiniert und mit den folgenden zusätzlichen Gesetzen ausgestattet ist:

1. Additive Kommutativität: $$$x + y = y + x$
2. Verteilung rechts: $$$(x + y) \ mal z = (x \ mal z) + (y \ mal z)$
3. Verteilung links: $$$x \ times (y + z) = (x \ times y) + (x \ times z)$
4. Das Vorhandensein von Null rechts: $$$x \ times zero = zero$
5. Das Vorhandensein von Null auf der linken Seite: $$$null \ mal x = null$

Kombinieren Sie AdditiveMonoid und MultiplicativeMonoid , um das entsprechende Semiring der Typklasse MultiplicativeMonoid :

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

Jetzt, wo wir Semiring , können wir es mit verschiedenen numerischen Typen verwenden: Int , Long , BigDecimal usw., aber ist es wirklich den ganzen Artikel über Halbringe wert? Es stellt sich heraus, dass viele andere Dinge auch Halbringe sind, einschließlich logischer Werte, Mengen und sogar Animationen .

Ich möchte darauf hinweisen, dass es möglich ist, einen Halbringhomomorphismus aus vielen Typen in die Gesamtzahl möglicher Vertreter dieser Typen zu formen. Was bedeutet das? Nun, sei geduldig und ich werde versuchen zu erklären, was ich meine.

Kardinalzahlen

Beginnen wir mit dem, was allgemein mit einer Kardinalzahl gemeint ist. Jeder Typ entspricht der Anzahl der Werte, die Vertreter dieses Typs annehmen können. Beispielsweise hat der Boolean Typ eine Kardinalzahl $$$2$ weil es nur zwei mögliche Werte hat: true und false .

Also, bei Boolean - $$$2$ , aber wie viele andere Typen? Byte - $$$2 ^ 8$ , Short - $$$2 ^ {16}$ , bei Int - $$$2 ^ {32}$ und Long $$$2 ^ {64}$ . Was ist mit Saiten? String ist ein formal unbegrenzter Typ und hat theoretisch eine unendliche Anzahl von Werten (in der Praxis haben wir natürlich keinen unendlichen Speicher, daher hängt die spezifische Anzahl von der Konfiguration des Computers ab).

Für welche anderen Typen können wir ihre Kardinalzahl bestimmen? Zwei ziemlich einfache Beispiele: Unit , die genau einen Vertreter hat, und Nothing , die die Untergrenze aller möglichen Typen in Scala ist und dementsprechend hat $$$0$ mögliche Werte. Das heißt, Sie können niemals einen Wert von Nothing erstellen, der einer Kardinalzahl entspricht $$$0$ .

Großartig, jetzt können Sie versuchen, dies im Code auszudrücken. Wir können eine Typklasse erstellen, die uns die Gesamtzahl der Werte des entsprechenden Typs geben kann.

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

Versuchen Sie nun, mehrere Instanzen dieser Klasse zu erstellen:

 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 } 

[ Hinweis: Vorgegebene Werte können auch als implicit val Wert deklariert werden. ]

Probieren wir sie in der REPL aus :

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

Großartig, aber es ist alles sehr einfach. Was ist mit ADT ? Können wir damit umgehen? Es stellt sich heraus, dass wir es können, wir müssen nur verstehen, wie man mit den einfachsten Summen und Produkten von Typen umgeht. Betrachten Sie zunächst das einfachste Produkt von Typen: (Boolean, Byte)

Wie viele Vertreter dieser Art? Wir wissen, dass Boolean $$$2$ und Byte $$$256$ . Also Zahlen aus $$$-128$ vorher $$$127$ kombiniert mit true oder false . Es stellt sich heraus $$$512$ einzigartige Werte.

$$$512$ sieht aus wie $$$256$ mal $$$2$ Vielleicht müssen Sie nur die Anzahl der Werte des ersten Typs mit der Anzahl der Werte des zweiten multiplizieren? Wenn Sie dies anhand der übrigen Beispiele überprüfen, stellen Sie sicher, dass dies der Fall ist. Stellen wir uns dies als eine Instanz einer Typklasse vor:

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

Betrachten Sie nun ein Beispiel für eine Summe von Typen: Either[Boolean, Byte] . In diesem Fall ist die Antwort noch offensichtlicher, da der Wert dieses Typs (tatsächlich) entweder Boolean oder Byte kann. Es reicht also aus, einfach die Kardinalzahlen hinzuzufügen. Also sollte Either[Boolean, Byte ] haben $$$256 + 2 = $ 25$ Vertreter.

Lassen Sie es uns im Code auf die gleiche Weise ausdrücken und die Ergebnisse in REPL bestätigen:

 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 

Folglich werden für die Summe der Typen die Kardinalzahlen addiert und für das Produkt multipliziert. Dies ist angesichts ihrer Namen logisch.

Was ist also mit dem zuvor diskutierten Homomorphismus? Ein Homomorphismus ist eine strukturerhaltende Abbildung zwischen zwei algebraischen Strukturen desselben Typs (in diesem Fall Semirings).

Dies bedeutet, dass für jeden $$$x$ , $$$y$ und Homomorphismus $$$f$ wir haben:

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

Die letzteren Ausdrücke mögen ziemlich abstrakt erscheinen, aber sie stehen in direktem Zusammenhang mit dem, was wir gerade getan haben. Wenn wir zwei Arten von Byte und Boolean „hinzufügen“, erhalten wir Either[Byte, Boolean] , und wenn wir den cardinality anwenden, erhalten wir $$$258$ . Dies entspricht der getrennten Anwendung der cardinality auf Byte und Boolean , gefolgt von der Addition der Ergebnisse.

Gleiches gilt natürlich auch für die Multiplikation und das Produkt von Typen. Trotzdem fehlt uns noch etwas für den richtigen Halbring, da wir nur Addition und Multiplikation erwähnt haben, nicht aber die entsprechenden Einzelelemente.

Wie wir bereits gesehen haben, hat der Typ Unit einen Vertreter und der Typ Nothing keinen. Können wir diese beiden Typen verwenden, um einen Halbring zu bilden?

Lass es uns versuchen! Wenn Unit eine Multiplikationseinheit ist, sollte das Produkt eines beliebigen Typs mit Unit dem ersten Typ entsprechen. Dies geschieht natürlich, da wir leicht etwas von der Entladung (Int, Unit) auf Int und umgekehrt ohne Verlust abbilden können, so dass die Kardinalzahl unverändert bleibt.

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

Was ist mit Nothing ? Da dies eine Additionseinheit ist, muss die Summe aller Typen mit Nothing dem gleichen Typ entsprechen. Entspricht Either[Nothing, A] A ? Ja! Da Nothing keine Bedeutung hat, kann Either[Nothing, A] nur Right und folglich nur A , daher sind diese Typen äquivalent.

Wir müssen auch die Richtigkeit von Null durch Multiplikation überprüfen: Jede Zahl, die durch Addition von zero mit Eins multipliziert wird, muss mit zero übereinstimmen. Da Nothing unsere Additionseinheit ist, sollte ein Produkt von Typen wie (Int, Nothing) Nothing . Dies geschieht, weil wir keinen Wert vom Typ Nothing und daher ein Tupel mit einem solchen Wert erstellen können.

Lassen Sie uns überprüfen, wie dies mit Kardinalzahlen zusammenhängt.

Zusatzeinheit:

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

Absorption durch Null:

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

Es bleibt die Verteilungsfähigkeit zu überprüfen. Im Kontext von Typen bedeutet dies, dass (A, Either[B, C]) mit Either[(A, B), (A, C)] übereinstimmen muss. Wenn Sie dies überprüfen, sind diese beiden Typen tatsächlich gleichwertig.

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

Algebraische Strukturen höherer Ordnung

Einige haben vielleicht schon von der Semigroupal Typklasse gehört. Aber warum heißt es so und in welcher Beziehung steht es zur Semigroup ? Schauen wir uns zunächst Semigroupal selbst an:

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

Es gibt eine gewisse Ähnlichkeit mit der Semigroup : Zwei Werte werden kombiniert, und die entsprechende Operation sollte assoziativ sein (ähnlich wie bei der Semigroup ).

So weit, so gut, aber der Funktionsname product etwas verwirrend. Es ist logisch, da wir A und B zu einem Tupel kombinieren, das ein Produkt von Typen ist, aber wenn wir das Produkt verwenden, ist es vielleicht keine willkürliche Semigroupal , sondern multiplikativ? Lassen Sie es uns umbenennen.

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

Nun wollen wir sehen, wie eine zusätzliche Semigroupal aussehen könnte. Natürlich müssen wir nur ein Produkt von Typen für die Summe ändern:

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

Es sieht gut aus - können wir Einheiten hinzufügen, um Monoidal zu erhalten? Klar können wir! Dies ist wieder Nothing und Unit für die Summe bzw. das Produkt:

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

Jetzt haben wir diese Typklassen, aber wie können wir sie verwenden? Nun, ich erkläre zuversichtlich, dass sie bereits in der Katzenbibliothek verwendet werden, jedoch unter verschiedenen Namen.

Wie könnten diese Klassen möglicherweise sein? Schauen Sie sich zunächst die sum und versuchen Sie, etwas Ähnliches wie AdditiveSemigroupal zu finden. Da Analoga dieser Klassen für Typen niedrigerer Ordnung entsprechende symbolische Operatoren haben, fügen wir AdditiveSemigroupal einen solchen Operator hinzu.

Da dies eine Summe ist, sollte dieser Operator höchstwahrscheinlich + enthalten und angeben, dass die Operation in einem bestimmten Kontext ausgeführt wird. Es wäre ideal, etwas wie [+] , aber dies ist eine ungültige Kennung. Versuchen Sie stattdessen <+> .

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

Die <+> Funktion existiert bei Katzen bereits als Alias ​​für combineK , der in SemigroupK zu finden ist, verhält sich jedoch anders. Es braucht zwei F[A] zur Eingabe und gibt F[A] - nicht genau wie das, was wir haben.

Oder ähnlich? Tatsächlich fallen diese beiden Funktionen zusammen und wir können sie in Gegenwart eines Funktors durcheinander definieren:

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

MonoidK es möglich, dass AdditiveMonoidal mit MonoidK identisch ist, da AdditiveMonoidal SemigroupK MonoidK ? Ja, und es ist leicht zu zeigen. MonoidK ergänzt durch die MonoidK :

 def empty[A]: F[A] 

Diese Funktion verwendet einen universellen Quantifizierer für A , dh sie funktioniert für jedes A , was bedeutet, dass sie in Wirklichkeit nicht mit einem bestimmten A und daher F[Nothing] in AdditiveMonoidal .

Nun, wir haben Analoga für additive Klassen gefunden und wissen bereits, dass MultiplicativeSemigroupal gleichbedeutend mit cats.Semigroupal . cats.Semigroupal . Wir müssen nur noch das Äquivalent von MultiplicativeMonoidal .

Ich betrüge ein wenig und sage, dass dieses Äquivalent Applicative . Es fügt eine pure Funktion hinzu, die A nimmt und F[A] zurückgibt. MultiplicativeMonoidal wiederum eine unit , die keine Parameter akzeptiert und F[Unit] zurückgibt. Wie bewege ich mich von einem zum anderen? Die Antwort impliziert wiederum die Verwendung eines Funktors:

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

Applicative verwendet einen kovarianten Funktor, aber im allgemeinen Fall können wir auch invariante und kontravariante Strukturen verwenden. Darüber hinaus enthält Applicative <*> als Alias ​​für die Kombination von product und map , was wie ein weiterer Hinweis darauf aussieht, dass dies eine multiplikative Klasse ist und die Intuition uns nicht enttäuscht hat.

Jetzt haben wir bei Katzen <+> und <*> , aber gibt es eine Typklasse, die sie kombiniert, ähnlich wie Semiring + und * kombiniert? Ja, und es heißt Alternative . Es wird von Applicative und MonoidK . Um konsequent zu sein, nennen wir es Semiringal :

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

Großartig, jetzt haben wir Semiring und sein Gegenstück für Typen höherer Ordnung. Leider ist die erste nicht bei Katzen , aber vielleicht wird sie in zukünftigen Versionen erscheinen.

Wenn es verfügbar wäre, könnten Semiring für jede Alternative auf Semiring schließen Alternative ähnlich wie für MonoidK oder Applicative auf Monoid . Außerdem könnten wir Semiring mit Const wieder in Alternative verwandeln, ähnlich wie Monoid in Applicative .

Lassen Sie uns abschließend sehen, wie diese Transformation geschrieben werden kann:

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

Fazit

Ringe und Halbringe sind sehr interessante algebraische Strukturen, und selbst wenn Sie nicht darüber nachgedacht haben, haben Sie sie höchstwahrscheinlich bereits verwendet. Dieser Beitrag wurde geschrieben, um zu zeigen, wie sich Applicative und MonoidK auf Monoid beziehen, warum algebraische Datentypen einen Halbring bilden und wie sich diese algebraischen Strukturen in Scala und anderen Programmiersprachen verbreiten. Für mich persönlich war die Erkenntnis, wie dies miteinander verbunden ist und eine sehr interessante Symmetrie bildet, nur eine Gehirnexplosion, und ich hoffe, dass dieser Beitrag dazu beitragen kann, ähnliche interessante Parallelen in Cats und anderen Bibliotheken zu finden, die auf verschiedenen mathematischen Abstraktionen basieren. Weiteres Material zu diesem Thema finden Sie hier .

Ergänzung

In diesem Beitrag habe ich über die Kommutativität in der Aufzeichnung der Typklassen geschwiegen. Kommutativität ist eine sehr wichtige Eigenschaft für Semirings und der Code sollte diese Eigenschaft widerspiegeln. Da der Beitrag jedoch bereits viele Definitionen enthält, schien es überflüssig und ablenkend vom Hauptzweck des Beitrags, ihn mehreren kommutativen Typklassen hinzuzufügen, die nichts anderes tun, als neue Gesetze einzuführen.

Darüber hinaus habe ich mich auf die Kardinalzahlen nur der Klassen konzentriert, die wir brauchten. Der Vollständigkeit halber können Sie jedoch Cardinality für Dinge wie A => B , Option[A] , Ior[A, B] hinzufügen:

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]