Идемпотентное полукольцо

Формальное определение

Идемпотентное полукольцо - это полукольцо, которое также является идемпотентным, т.е. добавление значения к самому себе приводит к тому же значению.

Для полукольца с единицей должны соблюдаться все законы полукольца:

• Замыкание сложения (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\)

, а также закон идемпотентности сложения:

• Идемпотентность (idempotency): для \(\forall x \in S\) выполняется \(x + x = x\).

Определение в виде кода на Scala

trait CSemiring[A] extends Semiring[A]

Законы в виде кода на Scala

trait CSemiringLaw extends SemiringLaw:
  def checkCSemiringLaw[A: CSemiring](
      x: A,
      y: A,
      z: A
  ): ValidatedNel[String, Unit] =
    checkSemiringLaw(x, y, z) combine
      check(
        CSemiring[A].times(x, y) == CSemiring[A].times(y, x),
        "commutative: x * y = y * x"
      )

Примеры

Множества

given [A]: ISemiring[Set[A]] with
  val empty: Set[A]                         = Set.empty[A]
  def combine(x: Set[A], y: Set[A]): Set[A] = x ++ y
  def times(x: Set[A], y: Set[A]): Set[A]   = x.intersect(y)

Реализация

Ссылки:

• Wikipedia