Идемпотентный моноид

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

IdempotentMonoid — это моноид, который также является идемпотентным, т.е. добавление значения к самому себе приводит к тому же значению.

IdempotentMonoid должен удовлетворять законам своих "родителей":

• Замыкание (closure): для \(\forall x, y \in IM\) выполняется \(x + y \in IM\).
• Ассоциативность (associativity): для \(\forall x, y, z \in IM\) выполняется \((x + y) + z = x + (y + z)\).
• Тождественность или существования нейтрального элемента (identity): существует \(\exists e \in IM\) такой, что для \(\forall x \in IM\) выполняется \(e + x = x + e = x\)
• Идемпотентность (idempotency): для \(\forall x \in IM\) выполняется \(x + x = x\).

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

trait IdempotentMonoid[A] extends Monoid[A], Band[A]

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

trait IdempotentMonoidLaw extends MonoidLaw, BandLaw:
  def checkIdempotentMonoidLaw[A: IdempotentMonoid](
      x: A,
      y: A,
      z: A
  ): ValidatedNel[String, Unit] =
    checkMonoidLaw(x, y, z) combine checkBandLaw(x, y, z)

Примеры

Множества

Некоторые операции над множествами являются идемпотентными: объединение, пересечение и т.п. Например, объединение множеств образуют IdempotentMonoid:

given [A]: IdempotentMonoid[Set[A]] with
  override def empty: Set[A] = Set.empty[A]
  override def combine(x: Set[A], y: Set[A]): Set[A] = x ++ y

Ссылки: