Полугруппа

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

\((S, +)\) является полугруппой (semigroup) для множества \(S\) и операции \(+\), если удовлетворяет следующим свойствам для любых \(x, y, z \in S\):

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

Также говорится, что S образует полугруппу относительно +.

Благодаря ассоциативности, можно корректно определить натуральную степень элемента полугруппы ("сложить n раз") как:

\(a^{n} = \overset{n}{a + ... + a}\)

Для степени элемента справедливы соотношения \(a^{n + m} = a^{m}+a^{n}, (a^{m})^{n} = a^{mn}, \forall n,m \in \mathbb{N}\).

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

trait Semigroup[A]:
  def combine(x: A, y: A): A

  def combineN(x: A, n: Int :| Greater[0]): A =
    @tailrec def loop(b: A, k: Int, acc: A): A =
      if k == 1 then combine(b, acc)
      else
        val x = if (k & 1) == 1 then combine(b, acc) else acc
        loop(combine(b, b), k >>> 1, x)

    if n == 1 then x else loop(x, n - 1, x)

О том, что такое Int :| Greater[0] рассказывается в статье об уточняющих типах.

Для операции сложения встречаются следующие наименования: combine, append, mappend (Haskell), op, plus, times.

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

Законы полугруппы принимают следующий вид:

замыкание следует из определения функции combine - тип результата тот же, что и тип переменных. При условии использования при реализации только чистых функций без побочных эффектов.
ассоциативность формулируется так: m.combine(x, m.combine(y, z)) == m.combine(m.combine(x, y), z)

import cats.data.*
import cats.syntax.either.*

trait Laws:
  protected def check(
      law: Boolean,
      message: => String
  ): ValidatedNel[String, Unit] =
    Either
      .cond[String, Unit](law, (), message)
      .toValidatedNel

trait SemigroupLaw extends Laws:
  def checkSemigroupLaw[A: Semigroup](
      x: A,
      y: A,
      z: A
  ): ValidatedNel[String, Unit] =
    check(
      Semigroup[A].combine(Semigroup[A].combine(x, y), z) ==
        Semigroup[A].combine(x, Semigroup[A].combine(y, z)),
      "associative: (x + y) + z == x + (y + z)"
    )

Примеры

Непустой список

case class NonEmptyList[+A](head: A, tail: List[A]):
  def toList: List[A] = head :: tail

given [A]: Semigroup[NonEmptyList[A]] with
  def combine(x: NonEmptyList[A], y: NonEmptyList[A]) =
    NonEmptyList(x.head, x.tail ++ y.toList)

Натуральные числа N образуют полугруппу относительно сложения

given sumSemigroupInstance: Semigroup[Int] = (x: Int, y: Int) => x + y

Натуральные числа N образуют полугруппу относительно умножения

given productSemigroupInstance: Semigroup[Int] = (x: Int, y: Int) => x * y

Строки образуют полугруппу относительно конкатенации

given stringSemigroupInstance: Semigroup[String] = (x: String, y: String) => x + y

Последовательность образует полугруппу относительно операции объединения

given listSemigroupInstance[T]: Semigroup[List[T]] =
  (x: List[T], y: List[T]) => x ++ y

Кортеж от двух и более полугрупп также является полугруппой

given nestedSemigroupInstance[A, B](using aSemigroup: Semigroup[A], bSemigroup: Semigroup[B]): Semigroup[(A, B)] =
  (x: (A, B), y: (A, B)) => (aSemigroup.combine(x._1, y._1), bSemigroup.combine(x._2, y._2))

Реализация

Реализация в Cats

import cats.*
import cats.implicits.*

1 |+| 2                                     // 3
("hello", 123) |+| ("world", 321)           // ("helloworld",444)

Реализация в ScalaZ

import scalaz.*
import Scalaz.*

List(1, 2) |+| List(3)      // List(1, 2, 3)
List(1, 2) mappend List(3)  // List(1, 2, 3)
1 |+| 2                     // 3

Реализация в Spire

import spire.algebra.Semigroup
import spire.syntax.semigroup.*

1 |+| 2                           // 3
("hello", 123) |+| ("world", 321) // ("helloworld",444)

Semigroup.combineN(3, 5)          // 15

Ссылки: