Идемпотентная полугруппа

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

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

Band должна удовлетворять следующим законам:

• Замыкание (closure): для \(\forall x, y \in B\) выполняется \(x + y \in B\).
• Ассоциативность (associativity): для \(\forall x, y, z \in B\) выполняется \((x + y) + z = x + (y + z)\).
• Идемпотентность (idempotency): для \(\forall x \in B\) выполняется \(x + x = x\).

Первые два закона наследуются от полугруппы.

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

trait Band[A] extends Semigroup[A]:
  override def combineN(x: A, n: Int :| Greater[0]): A = x

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

trait BandLaw extends SemigroupLaw:
  def checkBandLaw[A: Band](x: A, y: A, z: A): ValidatedNel[String, Unit] =
    checkSemigroupLaw(x, y, z) combine
      check(Band[A].combine(x, x) == x, "idempotency: x + x = x")

Примеры

Множества

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

given [A]: Band[Set[A]] =
  (x: Set[A], y: Set[A]) => x ++ y

Ссылки:

• Scalaz API