Полукольцо с единицей
Формальное определение
Полукольцо с единицей - это полукольцо, в котором существует нейтральный элемент по умножению (называемый единицей): \(\exists 1 \in S \quad \forall a \in S \quad a * 1 = 1 * a = a\).
Для полукольца с единицей должны соблюдаться все законы полукольца:
- Замыкание сложения (closure): для \(\forall x, y \in S\) выполняется \(x + y \in S\).
- Ассоциативность сложения (associativity): для \(\forall x, y, z \in S\) выполняется \((x + y) + z = x + (y + z)\).
- Существование нулевого элемента: существует \(\exists 0 \in S\) такой, что для \(\forall x \in S\) выполняется \(0 + x = x + 0 = x\)
- Коммутативность сложения (commutative): для \(\forall x, y \in S\) выполняется \(x + y = y + x\).
- Замыкание умножения (closure): для \(\forall x, y \in S\) выполняется \(x * y \in S\).
- Ассоциативность умножения (associativity): для \(\forall x, y, z \in S\) выполняется \((x * y) * z = x * (y * z)\).
- Дистрибутивность (distributivus, распределительный закон): для \(\forall x, y, z \in S\) выполняется \(x * (y + z) = x * y + x * z\) и \((x + y) * z = x * z + y * z\).
- Мультипликативное свойство нуля: \(a * 0 = 0 * a = 0\)
, а также закон тождественности по умножению:
- Существование единичного элемента: \(\exists 1 \in S \quad \forall x \in S \quad x * 1 = 1 * x = x\)
Определение в виде кода на Scala
trait SemiringWithUnity[A] extends Semiring[A]:
def one: AЗаконы в виде кода на Scala
trait SemiringWithUnityLaw extends SemiringLaw:
def checkSemiringWithUnityLaw[A: SemiringWithUnity](
x: A,
y: A,
z: A
): ValidatedNel[String, Unit] =
checkSemiringLaw(x, y, z) combine
check(
SemiringWithUnity[A].times(x, SemiringWithUnity[A].one) == x,
"times right identity: x * 1 = x"
) combine
check(
SemiringWithUnity[A].times(SemiringWithUnity[A].one, x) == x,
"times left identity: 1 * x = x"
)Примеры
Числа относительно сложения с 0 и умножения с 1
(Z, +, *)
given SemiringWithUnity[Int] with
val empty: Int = 0
val one: Int = 1
def combine(x: Int, y: Int): Int = x + y
def times(x: Int, y: Int): Int = x * yРеализация
Реализация в Spire
import spire.algebra.Rig
import spire.math.Rational
Rig.plus(Rational(1, 2), Rational(1, 3))
// val res0: spire.math.Rational = 5/6
Rig.times(Rational(1, 2), Rational(1, 3))
// val res1: spire.math.Rational = 1/6
Rig.pow(Rational(1, 2), 3)
// val res2: spire.math.Rational = 1/8
Rig.zero[Rational]
// val res3: spire.math.Rational = 0
Rig.one[Rational]
// val res4: spire.math.Rational = 1Ссылки: