Полугруппа
В предыдущей статье были рассмотрены базовые понятия для дальнейшего применения абстракций из теории категорий в функциональном программировании.
Теперь рассмотрим понятие полугруппы, которая является инвариантным функтором, но более специализирована. Для начала несколько понятий из алгебраической терминологии.
Группоид (groupoid) - это множество, имеющее одну бинарную операцию, которая не выводит за пределы множества: T |+| T => T, где T - тип элементов группоида, |+| - символ операции.
Полугруппа (semigroup) - это группоид, операция которого ассоциативна ((a |+| b) |+| c == a |+| (b |+| c) для всяких a, b и c).
Полугруппой, например, являются Int с операцией "+", Int с операцией "*", String с операцией "+".
Полугруппу можно представить как trait, параметризованный типом элемента и содержащим его операцию в качестве метода "|+|" и метод "xmap", т.к. полугруппа является инвариантным функтором:
trait Semi[T] { self =>
def |+|(x: T, y: T): T
def xmap[R](f: T => R, g: R => T): Semi[R] = new Semi[R] {
def |+|(x: R, y: R): R = f(self |+| (g(x), g(y)))
}
}
Реализация полугруппы строк с конкатенацией в качестве операции "|+|":
class SemiStr extends Semi[String]{
def |+|(x: String, y: String): String = x + y
}
Получение полугруппы Int с конкатенацией в качестве операции "|+|" из полугруппы String (переход от полугруппы строк к полугруппе целых чисел):
val f: String => Int = _.toInt
val g: Int => String = _.toString
val x: Semi[String] = new SemiStr
val y: Semi[Int] = x xmap (f, g)
println(y.|+|(20, 17)) // 2017
Получилась полугруппа целых чисел, у которой бинарная операция это конкатенация строковых представлений числа в десятичной системе счисления. Эта операция ассоциативна.
Моноид
Определение:
Моноид (monoid) - это полугруппа, для которой существует нейтральный элемент - такой элемент "e", что a |+| e == e |+| a == a, для любого a.
Примеры моноида: Int с операцией "+" и нейтральным элементом 0, Int с операцией "*" и нейтральным элементом 1, String с операцией "+" и нейтральным элементом пустая строка.
Моноид можно представить, как расширенный trait полугруппы, в котором добавляется нейтральный элемент:
trait Monoid[T] extends Semi[T] {
def empty: T
}
Реализация моноида целых чисел с операцией сложения и нейтральным элементом 0:
class IntMonoid extends Monoid[Int] {
def empty: Int = 0
def |+|(x: Int, y: Int): Int = x + y
}
val y: Monoid[Int] = new IntMonoid
val z = y.|+|(10, 5)
println(z) // 15
println(y.|+|(z, y.empty)) // 15
println(y.|+|(y.empty, z)) // 15
Рассмотрим еще две категориальные абстракции, такие как бифунктор (bifunctor) и профунктор (profunctor).
Бифунктор
С математической точки зрения бифунктор — это функтор от двух аргументов.
С синтаксической точки зрения, бифунктор - это тип, параметризованный двумя ковариантными параметрами типа, с методом, условно называемым bimap, который производит отображения на обеих сторонах бифунктора:
trait Bifunctor[F[+_, +_]] {
def bimap[A, B, C, D](fab: F[A, B], f: A => C, g: B => D): F[C, D]
}
Данный тип должен соответствовать двум правилам: Identity Law и Composition Law. То есть, для любого бифунктора "bifunc" должны выполняться два равенства:
bifunc.bimap(identity, identity) == identity(bifunc) // true
bifunc.bimap(f compose g, h compose i) == bifunc.bimap(g, i).bimap(f, h) // true
Реализуем метод bimap для класса Either:
// Обертка для возможности более удобного вызова
// метода bimap
abstract class BifunctorWrapper[F[+_, +_], A, B] {
val value: F[A, B]
val bifunctor: Bifunctor[F]
// Метод, проксирующий bimap
def <-:->[C, D](f: A => C, g: B => D): F[C, D] = bifunctor.bimap(value, f, g)
}
object BifunctorWrapper {
def apply[F[+_, +_], A, B](v: F[A, B])(implicit b: Bifunctor[F]): BifunctorWrapper[F, A, B] =
new BifunctorWrapper[F, A, B] {
val value: F[A, B] = v
val bifunctor: Bifunctor[F] = b
}
}
implicit val eitherBifunctor = new Bifunctor[Either] {
// Реализация bimap для Either
def bimap[A, B, C, D](fab: Either[A, B], f: A => C, g: B => D): Either[C, D] =
fab.fold(a => Left(f(a)), b => Right(g(b)))
}
implicit def either2Bifunctor[A, B](v: Either[A, B]): BifunctorWrapper[Either, A, B] =
BifunctorWrapper[Either, A, B](v) // за счет обертки работает автовывод всех типов
val intStrEither: Either[Int, String] = Left(2115)
val f: Int => Float = (n: Int) => (n + 1).toFloat / 2
val g: String => String = (s: String) => s.reverse
val floatStrEither = intStrEither <-:-> (f, g)
println(floatStrEither) // Left(1058.0)
Профунктор
Фактически, профунктор - это бифунктор, первый параметр которого контравариантный, а второй параметр ковариантный. У профунктора должен быть реализован метод dimap, который производит отображения на обеих сторонах профунктора:
trait Profunctor[F[-_, +_]] {
def dimap[A, B, C, D](fab: F[A, B], f: C => A, g: B => D): F[C, D]
}
Данный тип должен соответствовать двум правилам: Identity Law и Composition Law. То есть, для любого бифунктора "profunc" должны выполняться два равенства:
profunc.dimap(identity, identity) == identity(profunc) // true
profunc.dimap(f compose g, h compose i) == profunc.dimap(f, i).dimap(g, h) // true
Реализуем метод dimap для класса Function1, применяя подход, аналогичный реализации bimap для Either:
abstract class ProfunctorWrapper[F[-_, +_], A, B] {
val value: F[A, B]
val profunctor: Profunctor[F]
// Метод, проксирующий dimap
def >>:>>[C, D](f: C => A, g: B => D): F[C, D] = profunctor.dimap(value, f, g)
}
object ProfunctorWrapper {
def apply[F[-_, +_], A, B](v: F[A, B])(implicit p: Profunctor[F]): ProfunctorWrapper[F, A, B] =
new ProfunctorWrapper[F, A, B] {
val value: F[A, B] = v
val profunctor: Profunctor[F] = p
}
}
implicit val function1Profunctor = new Profunctor[Function1] {
// Реализация dimap для Function1
def dimap[A, B, C, D](fab: Function1[A, B], f: C => A, g: B => D): Function1[C, D] =
fab.compose(f).andThen(g)
}
implicit def function12Profunctor[A, B](v: Function1[A, B]): ProfunctorWrapper[Function1, A, B] =
ProfunctorWrapper[Function1, A, B](v)
val fab: Double => Double = x => x + 0.3
val f: Int => Double = x => x.toDouble / 2
val g: Double => Double = x => x * 3
val h = fab >>:>> (f, g)
println(h(3)) // 5.4
На момент написания статьи, версия Scala 2.12.1.
Полезные ссылки:
http://blog.tmorris.net/posts/funky-scala-bifunctor/
https://habrahabr.ru/company/golovachcourses/blog/267087/
https://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Bifunctor.html
https://hackage.haskell.org/package/profunctors-5.2/docs/Data-Profunctor.html
