scalabook
Полугруппа
Формальное определение
\((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.Semigroupimport spire.syntax.semigroup.*
1 |+| 2 // 3("hello", 123) |+| ("world", 321) // ("helloworld",444)
Semigroup.combineN(3, 5) // 15
Ссылки: