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

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\).

Код

trait IdempotentMonoid[A] extends Monoid[A], Band[A]:
  override def combineN(a: A, n: Int): Either[String, A] =
    if n < 0 then
      Left("Repeated combining for monoids must have n >= 0")
    else if n == 0 then Right(empty)
    else Right(a) // combine(a, a) == a

Множества

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

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

Законы

Законы наследуются от моноида и идемпотентной полугруппы.

Схема

classDiagram
    class Semigroup~A~{
        +combine(x: A, y: A) A
    }
    class IdempotentSemigroup~A~
    Semigroup <|-- IdempotentSemigroup    
    class Monoid~A~{
        +empty() A
    }
    Semigroup <|-- Monoid
    class IdempotentMonoid~A~
    IdempotentSemigroup <|-- IdempotentMonoid
    Monoid <|-- IdempotentMonoid

Ссылки:

Ссылка на репозиторий с упражнениями

← Предыдущая Следующая →