Апрель 11, 2017
Полугруппа, моноид, бифунктор, профунктор

Полугруппа

В предыдущей статье были рассмотрены базовые понятия для дальнейшего применения абстракций из теории категорий в функциональном программировании.

Теперь рассмотрим понятие полугруппы, которая является инвариантным функтором, но более специализирована. Для начала несколько понятий из алгебраической терминологии.

Группоид (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

Добавить комментарий:
Комментариев: (1)
Рейтинг: 1 Опубликовал Ташуля 1922 дн. назад
Не нравится Нравится
Cаша, ты лучший !!!
Опубликовать