Tale of semirings

Hi, Habr! I bring to your attention the translation of the article "A tale on Semirings" by Luka Jacobowitz.

Ever wondered why the sum of types is called the sum of types. Or maybe you always wanted to know why the <*> operator is written this way? And what does this have to do with semirings? Interested please under the cat!

This article is a translation of a post on Typelevel’s blog written by Luca Jakobovic. For its best perception, at least a superficial acquaintance with the Scala language and its ecosystem (including the cats library) and knowledge of the basic concepts of abstract algebra: a semigroup, a monoid, etc. are required.

Algebraic structures

Many of us know about monoids and semigroups and even use them. These structures have properties that allow you to apply them directly to obtain a higher level of abstraction (if you do not know about them, you can read the documentation of the ats library ). However, sometimes a data type has more than one monoid or semigroup. An obvious example is various numerical types, where multiplication and addition form two full-fledged monoids.

In abstract algebra there is a separate class of structures with two monoids that interact in a certain way. This class is semirings. Since monoids are often used to describe numerical types, they are usually divided into multiplicative and additive. As in the case with numbers, the laws of a semiring determine that multiplication is distributive in addition, and multiplication of any number by one in addition - zero - gives zero.

There are various ways to present this in the form of type classes and different libraries do it in their own way, but let's look at how this is done in the project algebra . The base in it are AdditiveSemigroup and MultiplicativeSemigroup .

[ Note: since the name "type class" is not particularly stuck in Russian, its English version will be used later - 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 } 

[ Note: The @typeclass annotation from the simulacrum project allows you to automatically generate frequently used methods for type classes and does not affect the logical component of the code ]

In this case, the semi-ring ( Semiring ) is an additive monoid ( AdditiveMonoid ), combined with a multiplicative monoid ( MultiplicativeMonoid ) and equipped with the following additional laws:

1. Commutativity of addition: $$$x + y = y + x$
2. Distributivity on the right: $$$(x + y) \ times z = (x \ times z) + (y \ times z)$
3. Left Distributivity: $$$x \ times (y + z) = (x \ times y) + (x \ times z)$
4. Zero on the right: $$$x \ times zero = zero$
5. Zero left: $$$zero \ times x = zero$

To set the appropriate half-ring type class, combine the AdditiveMonoid and MultiplicativeMonoid :

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

Now that we have Semiring , we can use it with various numerical types: Int , Long , BigDecimal , etc., but is it worth the whole article about semirings? It turns out that many other things are also semirings, including logical values, sets, and even animations .

I would like to note that it is possible to form a semiring homomorphism from the set of types into the total number of possible representatives of these types. What does it mean? Well, have patience, and I will try to explain what I mean.

Cardinal numbers

Let's start with what is generally meant by the cardinal number. Each type corresponds to the number of values ​​that representatives of this type can take. For example, the type Boolean has a cardinal number. $$$2$, because it has only two possible values: true and false .

So, Boolean - $$$2$, and how many other types? Byte $$$2 ^ 8$, Short - $$$2 ^ {16}$, Int - $$$2 ^ {32}$, and Long - $$$2 ^ {64}$. What about strings? String is a formally unlimited type and theoretically has an infinite number of values ​​(in practice, naturally, we do not have infinite memory, so a particular number will depend on the configuration of the computer).

For what other types we can determine their cardinal number? Two fairly simple examples: Unit , which has exactly one representative, and Nothing , which is the lower boundary of all possible types in Scala and therefore has $$$0$possible values. That is, you can never create a Nothing value, which corresponds to the cardinal number $$$0$.

Great, now you can try to express it in code. We can create a type class that can give us the total number of values ​​of the corresponding type.

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

Now we will try to create several instances of this class:

 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 } 

[ Note: values ​​given can also be declared as implicit val ]

Let's try them out at the REPL :

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

Great, but it's all very simple, what about ADT ? Can we process them in this way? It turns out that we can, we just need to understand how to handle the simplest sums and products of types. First, consider the simplest product of types: (Boolean, Byte)

How many representatives does this type have? We know that Boolean them $$$2$, and Byte - $$$256$. Thus, numbers from $$$-128$before $$$127$combined with true or false . Turns out $$$512$unique values.

$$$512$looks like $$$256$multiplied by $$$2$, so maybe you just need to multiply the number of values ​​of the first type by the number of values ​​of the second? If you check it with the rest of the examples, then make sure that this is true. Let's imagine this as a type class instance:

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

Now consider an example of the sum of types: Either[Boolean, Byte] . In this case, the answer is even more obvious, since the value of this type (as a matter of fact) can be either Boolean or Byte , so it’s enough just to add cardinal numbers. Thus, Either[Boolean, Byte ] should have $$$256 + 2 = $ 25$representatives.

Let's express it in a similar way in the code and confirm the results in the 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 

Therefore, for the sum of types, the cardinal numbers are added, and for the product - they are multiplied. This is logical, given their names.

So what about that homomorphism, which was discussed earlier? A homomorphism is a structure-preserving mapping between two algebraic structures of the same type (in this case, semirings).

This means that for any $$$x$, $$$y$and homomorphism $$$f$we have:

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

The last expressions may seem rather abstract, but they are directly related to what we have just done. If we “add” two types of Byte and Boolean , then we get Either[Byte, Boolean] , and if we apply the cardinality homomorphism to it, we get $$$258$. This is equivalent to applying cardinality to Byte and Boolean separately, followed by the addition of the results.

Of course, the same applies to multiplication and product of types. However, we still lack something for the correct semiring, since we have only mentioned addition and multiplication, but not the corresponding unit elements.

As we have already seen, the Unit type has one representative, and the Nothing type - none. Can we use these two types to form a semiring?

Let's try! If Unit is a unit by multiplication, then the product of any type with Unit must be equivalent to the first type. Naturally, this is done, since we can easily map something from the discharge (Int, Unit) to Int and back without loss, so that the cardinal number remains unchanged.

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

What about Nothing ? Since this is a unit of addition, the sum of any type with Nothing must be equivalent to the same type. Does Either[Nothing, A] match A ? Yes! Since Nothing has no value, Either[Nothing, A] can only have Right and, as a result, only A , so these types are equivalent.

We also need to check the correctness of zero by multiplication: any number multiplied by one by the addition of zero must coincide with zero . Since Nothing is our unit of addition, a product of types like (Int, Nothing) should be equivalent to Nothing . This is done because we cannot create a value of type Nothing and, as a result, a tuple containing such a value.

Check how this relates to the cardinal numbers.

Unit by addition:

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

Zero absorption:

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

It remains to check the distributivity. In the context of types, this means that (A, Either[B, C]) must match Either[(A, B), (A, C)] . If checked, then these two types will indeed be equivalent.

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

Higher order algebraic structures

Some may have heard of the type class Semigroupal . But why is it called that and how does it relate to Semigroup ? First, let's look at Semigroupal itself:

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

There is a certain similarity with Semigroup : two values ​​are combined, and the corresponding operation must be associative (similar to Semigroup ).

So far, so good, but the function name product bit confusing. It is logical, since we combine A and B into a tuple, which is a product of types, but if we use a product, perhaps this is not an arbitrary Semigroupal , but a multiplicative one? Let's rename it.

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

Now consider what Semigroupal might look like by addition. Naturally, all we have to change is the product of types for the sum:

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

Looks good - can we add units to get Monoidal ? Of course we can! These will again be Nothing and Unit for the sum and product respectively:

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

Now we have these type classes, but how can we use them? Well, with confidence I declare that they are already used in the cats library, but under different names.

What could be like these classes at all? To begin, take a look at the sum function and try to find something similar to AdditiveSemigroupal . Since the analogs of these classes for the types of lower order have corresponding symbolic operators, let's add such an operator to AdditiveSemigroupal .

Since this is a sum, this operator should most likely contain + and show that the operation is performed in some context. Ideal would be to use something like [+] , but this is not a valid identifier, so try <+> instead.

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

The <+> function already exists in cats as a pseudonym for combineK , which can be found in SemigroupK , but it behaves differently. It takes two F[A] as input and returns F[A] - not exactly like what we have.

Or similar? In fact, these two functions coincide and we can define one through the other in the presence of a 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) } 

Since AdditiveSemigroupal equivalent to SemigroupK , is it possible that AdditiveMonoidal matches MonoidK ? Yes, and it is easy to show it. MonoidK added with the empty function:

 def empty[A]: F[A] 

This function uses a universal quantifier for A , that is, it works for any A , which means that in fact it cannot operate on any particular A and is thus equivalent to F[Nothing] in AdditiveMonoidal .

Well, we have found analogues for additive classes and already know that MultiplicativeSemigroupal equivalent to cats.Semigroupal . All we have to do is find the equivalent of MultiplicativeMonoidal .

I cheat a little and say that Applicative is the equivalent. It adds the pure function, which accepts A and returns F[A] . MultiplicativeMonoidal in turn, has a function unit that takes no parameters and returns F[Unit] . How to move from one to another? The answer again implies the use of a functor:

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

Applicative uses a covariant functor, but in general we can also use invariant and contravariant structures. In addition to this, Applicative includes <*> as a pseudonym for the product and map combination, which looks like another clue that this is a multiplicative class and intuition has not let us down.

Now in cats , we have <+> and <*> , but does a type class exist that unites them, in the same way as Semiring combines + and * ? There is, and it is called Alternative . It is inherited from Applicative and MonoidK . To be consistent, we call it Semiringal :

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

Great, now we have both Semiring and its equivalent for higher order types. Unfortunately, the first in cats is not, but perhaps it will appear in future versions.

If it were available, we could derive Semiring for any Alternative similar to deriving Monoid for MonoidK or Applicative . Also, we could turn Semiring back into Alternative using Const , similar to turning Monoid into Applicative .

In conclusion, let's see how this transformation can be written:

 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

Rings and semirings are very interesting algebraic structures, and even if you didn’t think about it, most likely you have already used them. This post was written to show how Applicative and MonoidK relate to Monoid , why algebraic data types form a semi-ring, and how these algebraic structures have spread in Scala and other programming languages. For me personally, the realization of how all this is interconnected and forms a very entertaining symmetry was just a brain explosion, and I hope that this post will be able to help find similar interesting parallels in Cats and other libraries based on various mathematical abstractions. Further material on this topic can be found here .

Addition

In this post, I kept silent about commutativity in the record type class. Commutativity is a very important property for half-rings and the code should reflect this property. However, since the post already contains many definitions, the addition of several more commutative type classes that do nothing but introduce new laws seemed redundant and distracting from the main goal of the post.

Moreover, I focused on the cardinal numbers of only those classes that we needed, but for completeness, we can add Cardinality definitions for such things as 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]