半环的故事

哈Ha！ 我提请您注意卢卡·雅各布维兹（Luka Jacobowitz）的文章“半环的故事” 。

曾经想过为什么将类型之和称为类型之和。 或者，也许您一直想知道为什么<*>运算符是这样写的？ 与半环有什么关系？ 有兴趣请减价！

本文是Luke Jakobovic 的Typelevel博客文章的翻译。 为了获得最佳的感知，至少需要对Scala语言及其生态系统（包括cats库）有一点表面的了解，并且需要抽象代数的基本概念（半群，类半群等）的知识。

代数结构

我们中的许多人都知道Monoid和半群，甚至使用它们。 这些结构的属性使您可以直接应用它们以获得更高的抽象级别（如果您不了解它们，则可以从cats库中阅读文档 ）。 但是，有时一种数据类型具有多个monoid或半组。 一个明显的例子是各种数值类型，其中乘法和加法形成两个完整的类半体。

在抽象代数中，有一类单独的结构，其中两个类半定体以某种方式相互作用。 这节课是半响。 由于Monoid通常用于描述数值类型，因此通常将它们分为乘法和加法。 与数字的情况一样，半圆环的定律确定乘法是加法的分布，而任何数字乘以加一的统一数-零-则为零。

有多种方式可以将其表示为类型类，并且不同的库以各自的方式来实现此目的，但让我们看一下如何在代数项目中完成该工作。 其中的基础是AdditiveSemigroup和MultiplicativeSemigroup 。

[ 注意：由于“类型类别”这个名称并非以俄语为根，因此稍后将使用其英文版本-类型类别 ]

 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 } 

[ 注意：simulacrum项目中的@typeclass批注使您可以自动生成类型类的常用方法，并且不会影响代码的逻辑组件 ]

在这种情况下，半环是加和性的单面体（ AdditiveMonoid ），与乘法性的单面体（ MultiplicativeMonoid ）组合，并具有以下附加定律：

1. 可加交换性： $$$x + y = y + x$
2. 右边的分布： $$$（x + y）\乘以z =（x \乘以z）+（y \乘以z）$
3. 分布在左侧： $$$x \次数（y + z）=（x \次数y）+（x \次数z）$
4. 右侧为零： $$$x \零=零$
5. 左侧为零： $$$零\乘以x =零$

要设置类型类的相应半环，请组合AdditiveMonoid和MultiplicativeMonoid ：

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

现在我们有了Semiring ，我们可以将其与各种数值类型一起使用： Int ， Long ， BigDecimal等，但是整篇关于半环的文章真的值得吗？ 事实证明，其他许多东西也都是半环，包括逻辑值，集合甚至动画 。

我想指出，有可能将许多类型的半环同构形成为这些类型的可能代表总数。 这是什么意思？ 好吧，请耐心等待，我将尽力解释我的意思。

基数

让我们从通常的基数开始。 每种类型对应于该类型代表可以采用的值的数量。 例如， Boolean类型具有基数 $$$2$ 因为它只有两个可能的值： true和false 。

因此，在Boolean - $$$2$ ，但还有其他几种类型？ Byte - $$$2 ^ 8$ ， Short - $$$2 ^ {16}$ ，位于Int $$$2 ^ {32}$ 和Long $$$2 ^ {64}$ 。 字符串呢？ String是形式上不受限制的类型，理论上具有无限数量的值（当然，实际上，我们没有无限的内存，因此具体数量将取决于计算机的配置）。

我们还能确定其他哪些类型的基数？ 两个相当简单的示例： Unit ，它只有一个代表； Nothing ，它是Scala中所有可能类型的下限，因此具有 $$$0$ 可能的值。 也就是说，您永远无法创建与基数对应的Nothing值 $$$0$ 。

太好了，现在您可以尝试用代码表达这一点。 我们可以创建一个类型类，它可以为我们提供相应类型的值的总数。

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

现在尝试创建该类的几个实例：

 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 } 

[ 注意：给定值也可以声明为implicit val ]

让我们在REPL中尝试一下：

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

很好，但是非常简单， ADT呢？ 我们可以这样处理吗？ 事实证明，我们可以，我们只需要了解如何处理最简单的总和和类型乘积。 首先，请考虑以下最简单的乘积类型：（ (Boolean, Byte)

有多少这种类型的代表？ 我们知道Boolean它们 $$$2$ 和Byte $$$256$ 。 因此，来自 $$$-128$ 之前 $$$127$ 结合false 。 原来 $$$512$ 独特的价值观。

$$$512$ 看起来像 $$$256$ 次 $$$2$ ，所以也许您只需要将第一种类型的值的数量乘以第二种类型的值的数量？ 如果在其余示例中进行了检查，请确保这是正确的。 让我们将其想象为类型类的实例：

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

现在考虑一个类型总和的示例： Either[Boolean, Byte] 。 在这种情况下，答案就更加明显了，因为这种类型的值（实际上）可以是Boolean或Byte ，因此只需添加基数就足够了。 因此Either[Boolean, Byte ]应该具有 $$$256 + 2 = $ 25$ 代表。

让我们以相同的方式在代码中表达它，并在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 

因此，对于类型的总和，将基数相加，对于乘积，将它们相乘。 给定他们的名字，这是合乎逻辑的。

那么前面讨论的同态又如何呢？ 同态是两个相同类型的代数结构（在这种情况下为半环）之间的保留结构映射。

这意味着对于任何 $$$x$ ， $$$y$ 和同态 $$$f$ 我们有：

1. $$$f（x \乘以y）= f（x）\乘以f（y）$
2. $$$f（x + y）= f（x）+ f（y）$

后面的表达式可能看起来很抽象，但是它们与我们所做的工作直接相关。 如果我们将Byte和Boolean两种类型“相加”，则得到Either[Byte, Boolean] ，如果对它应用cardinality同构，则得到 $$$258$ 。 这等效于分别对Byte和Boolean应用cardinality ，然后将结果相加。

当然，乘法和类型乘积也是如此。 尽管如此，我们仍然缺少用于正确的半环的东西，因为我们仅提及加法和乘法，而没有提及相应的单个元素。

正如我们已经看到的， Unit类型Unit一个代表， Nothing类型没有。 我们可以使用这两种类型来形成半环吗？

试试吧！ 如果Unit是乘法单位，则任何类型与Unit的乘积应等于第一种类型。 自然地，这样做就可以了，因为我们可以轻松地将放电(Int, Unit)到Int映射(Int, Unit)反之亦然，而基数不变。

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

那Nothing呢？ 由于这是一个加法单位，因此Nothing的任何类型的总和必须等于同一类型。 Either[Nothing, A]匹配A吗？ 是的 由于Nothing没有意义，因此Either[Nothing, A]只能是Right ，因此只能是A ，因此这些类型是等效的。

我们还需要通过乘法检查零的正确性：任何数字乘以零再乘以零的数字都必须匹配zero 。 由于Nothing是我们的加法单位，因此(Int, Nothing)之类的乘积应等于Nothing 。 这样做是因为我们无法创建Nothing类型的值，因此无法创建包含该值的元组。

让我们检查一下这与基数之间的关系。

加法单位：

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

零吸收：

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

仍然需要验证分布。 在类型的上下文中，这意味着(A, Either[B, C])必须与Either[(A, B), (A, C)]匹配。 如果您检查，那么这两种类型实际上是等效的。

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

高阶代数结构

有些人可能已经听说过Semigroupal类型类。 但是为什么这么称呼它，它与Semigroup什么关系呢？ 首先，让我们看一下Semigroupal本身：

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

与Semigroup有一定的相似性：将两个值组合在一起，并且对应的操作应该是关联的（类似于Semigroup ）。

到目前为止，还算不错，但是函数名称product有点令人困惑。 这是合乎逻辑的，因为我们将A和B组合成一个元组，这是类型的乘积，但是如果我们使用乘积，也许它不是一个任意的Semigroupal ，而是乘法的？ 让我们重命名它。

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

现在，让我们来看看添加的Semigroupal可能是什么样子。 自然，我们要做的就是更改总和类型的乘积：

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

看起来不错-我们可以添加单位以获得Monoidal吗？ 当然可以！ 总和和乘积分别为Nothing和Unit ：

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

现在我们有了这些类型类，但是如何使用它们呢？ 好吧，我有信心声明它们已经在cats库中使用过，但是使用了不同的名称。

这些课程可能是什么样的？ 首先，请看一看sum函数并尝试找到与AdditiveSemigroupal类似的东西。 由于这些类的低序类型类似物具有相应的符号运算符，因此我们将此类运算符添加到AdditiveSemigroupal 。

由于这是一个和，因此该运算符很可能应包含+并指示在某些情况下正在执行该操作。 最好使用[+]类的东西，但这是无效的标识符，因此请尝试使用<+> 。

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

猫中已经存在<+>函数作为combineK的别名，可以在combineK中找到它，但其行为有所不同。 它需要两个F[A]作为输入并返回F[A] -与我们所拥有的不完全相同。

还是类似的？ 实际上，这两个函数是重合的，我们可以在有函子的情况下定义另一个函数：

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

由于AdditiveSemigroupal等效于MonoidK ， AdditiveMonoidal可能与MonoidK相同？ 是的，而且很容易显示。 MonoidK由empty函数补充：

 def empty[A]: F[A] 

此函数对A使用通用量词，也就是说，它适用于任何A ，这意味着实际上它不能对任何特定A进行操作，因此等效于AdditiveMonoidal F[Nothing] 。

好吧，我们找到了加法类的类似物，并且已经知道MultiplicativeSemigroupal等同于cats.Semigroupal 。 对我们而言，剩下的就是找到MultiplicativeMonoidal的等效项。

我作弊一点，说这等效于Applicative 。 它添加了一个pure函数，该函数采用A并返回F[A] 。 反过来， MultiplicativeMonoidal具有一个不带参数且返回F[Unit]的unit函数。 如何从一个移动到另一个？ 答案再次暗示使用函子：

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

Applicative使用协变函子，但在一般情况下，我们也可以使用不变和反变的结构。 除此之外， Applicative还包括<*>作为product和map组合的别名，这似乎是另一个线索，表明这是一个乘法类，直觉并没有使我们失望。

现在在猫中，我们有了<+>和<*> ，但是有没有将它们组合在一起的类型类，类似于Semiring如何将+和*组合在一起？ 是的，它叫Alternative 。 它是从Applicative和MonoidK继承的。 为了保持一致，我们将其称为Semiringal ：

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

太好了，现在有了Semiring ，它对应于高阶类型。 不幸的是，第一个不是出现在cats中 ，但是可能会在将来的版本中出现。

如果可用，我们可以推断出MonoidK任何Alternative类似于推断MonoidK或MonoidK Monoid 。 同样，我们可以使用Const将Monoid转换回Alternative ，类似于将Monoid转换为Applicative 。

最后，让我们看看如何编写这种转换：

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

结论

环和半环是非常有趣的代数结构，即使您没有考虑它，也很可能已经使用了它们。 写这篇文章是为了展示Applicative和MonoidK与Monoid ，为什么代数数据类型形成半环，以及这些代数结构如何在Scala和其他编程语言中传播。 对我个人而言，如何实现这种相互联系并形成一个非常有趣的对称性只是脑子爆炸，我希望这篇文章可以帮助Cats和其他基于各种数学抽象的库中找到类似的有趣相似之处。 您可以在此处找到有关此主题的更多材料。

加法

在这篇文章中，我对类型类记录中的可交换性保持沉默。 对于半环来说，可交换性是非常重要的属性，并且代码应反映该属性。 但是，由于该帖子已经包含许多定义，因此用一些更多的可交换类型类对其进行补充，这些类什么也不做，只能引入新的法律，这似乎是多余的，并且分散了该帖子的主要目的。

此外，我只关注我们需要的那些类的基数，但是为了完整起见，您可以为A => B ， Option[A] ， Ior[A, B]类A => B事物添加Cardinality定义：

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]