FP на Scala: Invariant Functor

В статье рассматривается

• Как такая абстракция теории категорий как инвариантный функтор (Invariant Functor), который иногда называют экпоненциальным функтором (Exponential Functor), выражается на Scala.
• Два правила (Identity Law, Composition Law), которым доложен следовать каждый инвариантный функтор.
• Приведен пример инвариантного функтора с состоянием (Value Holder)
• Приведен пример инвариантного функтора-отношения между элементами множества (полугруппа)

Публикация является продолжением FP на Scala: Что такое функтор? в которой были рассмотрены следующие вопросы

• Какая имеется связь между теорией категорий, Haskell и Scala.
• Что такое ковариантный функтор.
• Что такое контравариантный функтор.

Содержание

• Введение
• Что такое Invariant Functor
• Invariant Functor — Identity Law
• Invariant Functor — Composition Law
• Пример #1: Value Holder
• Пример #2: Полугруппа
• Инвариантный функтор в библиотеках

Если Вы желаете сильнее погрузиться в мир Scala, математики и функционального программирования — попробуйте онлайн-курс «Scala for Java Developers» (видео + тесты, всего за 25% цены! Количество ссылочных купонов ограничено!).

Введение

Напомню основные тезисы предыдущей статьи:

• Нет необходимости знать теорию категорий, что бы разбираться в категориальных абстракциях в рамках функционального программирования. Более того, теория категорий не дает хороших примеров.
• Реализации категориальных абстракций в Scala пришли из Haskell. Полезно уметь читать исходный код более зрелого Haskell, что бы набирать примеры для более молодой Scala.
• Основные категориальные библиотеки (Scalaz, Cats) для выражения категориальных абстракций используют generics of higher kind. Однако этот языковой механизм (которого нет ни в Java ни в C#) используется для построения повторно используемых абстракций. «Штучные» идиомы можно реализовывать минимальными средствами.
• Ковариантный функтор — это источник данных.
• Контравариантный функтор — это приемник данных.

.
Но все же автор настоятельно рекомендует ознакомится с предыдущей статьей.

Что такое Invariant Functor

Инвариантный функтор — это ковариантный и контравариантный функтор «в одном флаконе».

В виде сигнатуры это можно выразить следующим образом

trait Invariant[T] {
  def xmap[R](f: T => R, g: R => T): Invariant[R]
}

То есть, для получения нового инвариантного функтора, нам необходимо предоставить отображения требуемые и ковариантному функтору (f: T => R) и контравариантному (g: R => T).

Или графически

     +---------------------------------------+
   R |             T  +------+  T            | R 
  -----> f: R=>T -----> C[T] -----> g: T=>R ----->
     |                +------+               |
     +---------------------------------------+

То есть «оттранслированный» Invariant[R] «сводится» к оригинальному Invariant[T] с помощью пары взаимно-обратных преобразований f и g которые «поджидают» данные «на входе» и «на выходе».

Invariant Functor — Identity Law

Invariant Functor (наравне с Covariant Functor и Contravariant Functor) тоже обязан следовать паре схожих правил. И правило первое (Identity Law) гласит: для всякого инвариантного функтора fun[T] должно выполняться IdentityLaw.case0(fun) тождественно равно IdentityLaw.case1(fun).

object IdentityLaw {
  def case0[T](fun: Invariant[T]): Invariant[T] = fun
  def case1[T](fun: Invariant[T]): Invariant[T] = fun.xmap(x => x, x => x)
}

Смысл правила становится понятен, если обратится к смыслу Identity Law для Covariant Functor и Identity Law для Contravariant Functor.

Invariant Functor — Composition Law

Правило второе (Composition Law) гласит: для всякого инвариантного функтора fun[T] и любых функций f1: T => R, g1: R => T, f2: R => Q, g2: Q => R должно выполняться CompositionLaw.case0(fun, f1, g1, f2, g2) тождественно равно CompositionLaw.case1(fun, f1, g1, f2, g2).

object CompositionLaw {
  def case0[T, R, Q](fun: Invariant[T], f1: T => R, g1: R => T, f2: R => Q, g2: Q => R): Invariant[Q] =
    fun.xmap(f1, g1).xmap(f2, g2)
  def case1[T, R, Q](fun: Invariant[T], f1: T => R, g1: R => T, f2: R => Q, g2: Q => R): Invariant[Q] =
    fun.xmap(f2 compose f1, g1 compose g2)
}

Смысл правила становится понятен, если обратится к смыслу Composition Law для Covariant Functor и Composition Law для Contravariant Functor.

Пример #1: Value Holder

Из предыдущей статьи следует, что ковариантный и контравариантный функторы — это две как бы «половины контейнера» (это метафора, более точно рассматривать сигнатуру + правила). Значит, если инвариантный (экспоненциальный) функтор — это и то и другое, то в качестве примера можно взять простейший из контейнеров — value holder.

trait Holder[T] { self =>
  def put(arg: T): Unit
  def get: T
  def xmap[R](f: T => R, g: R => T): Holder[R] = new Holder[R] {
    override def put(arg: R): Unit = self.put(g(arg))
    override def get: R = f(self.get)
  }
}

Например value holder для строк.

class StrHolder(var value: String = null) extends Holder[String] {
  override def put(arg: String): Unit = {value = arg}
  override def get: String = value
}

Демонстрация

object Demo extends App {
  val f: String => Int = Integer.parseInt(_, 16)
  val g: Int => String = Integer.toHexString

  val s: Holder[String] = new StrHolder
  val k: Holder[Int] = s xmap (f, g)

  k put 100500
  println(k get)
}

>> 100500

У нас получился контейнер Int, который хранит их в строковом шестнадцатеричном формате.

Ну а зачем нужен простейший value holder? Мы можем нарастить его функционал в нескольких направлениях

• Можно прикрепить данные (версию, лог обращений put/get, ...).
• Можно перехватывать обращения (для синхронизации, ведения лога обращений put/get, проксирования к удаленным источникам, ...).

Замечание: обратите внимание, что правила инвариантного функтора препятствуют «подсчитыванию» операций xmap, но не других (put, get)! Можно логировать во внутреннем состоянии вызовы put/get/..., но не xmap.
Задание: Реализуйте такую логику.

Пример #2: Полугруппа

Важно отметить, что ковариантный и контравариантные функторы — это именно источники и приемники данных работающие по определенным правилам (Identity Law, Composition Law), а не «половины контейнера». Мы не обязаны хранить данные (делать их частью своего состояния), мы просто должны иметь их аргументами и возвращаемыми значениями методов. Но если мы их не будем хранить, то операции put и get должны «выполняться одновременно», т.е. мы ищем структуры у которых type parameter T присутствует и в аргументах и в возвращаемом значении.

Нашими примерами могут стать не состояния, а процессы! Обратим внимание, что то, что является процессом (метод), может выражать отношение между элементами).

Напомню базовую алгебраическую терминологию (нам нужны простейшие отношения между элементами множества, которые дают инвариантный функтор. Совсем уж простейшие это, конечно, отношение эквивалентности и порядка, но они, согласно предыдущей статьи, являются контравариантными функторами).

Группоид (groupoid) — это множество снабженное одной бинарной операцией (T # T => T, T — тип элементов группоида, # — символ операции), которая не выводит за пределы множества.

Полугруппа (semigroup) — это группоид, операция которого ассоциативна ((a # b) # c == a # (b # c) для всяких a, b и c).

Моноид (monoid) — это полугруппа с нейтральным элементом (существует такой элемент 'e', что a # e == e # a == a, для всякого a).

Множество с операцией	Группоид	Полугруппа	Моноид
Int и '+'	+	+	+
Int и '-'	+	-	-
Int и '*'	+	+	+
Int и '/'	-	-	-
String и '+'	+	+	+
String (без "") и '+'	+	+	-

Замечания

1. В Int делить на 0 нельзя, ArithmeticException — результат не Int.
2. Сложение и умножение — ассоциативны, вычитание и деление — нет.
3. Для полугруппы Int по сложению нейтральным элементом является '0'.
4. Для полугруппы Int по умножению нейтральным элементом является '1'.
5. В строках по конкатенации нейтральный элемент — это пустая строка ("").

Представим полугруппу (или группоид, в Scala проверку ассоциативность все равно нельзя вынести на этап компиляции) в виде trait, который параметризирован типом элемента и содержит его операцию в качестве метода

trait Semi[T] {
  def |+|(x: T, y: T): T
}

Полугруппа является инвариантным (экспоненциальным) функтором

trait Semi[T] { self =>
  def |+|(x: T, y: T): T
  def xmap[R](f: T => R, g: R => T): Semi[R] = new Semi[R] {
    override def |+|(x: R, y: R): R = f(self |+| (g(x), g(y)))
  }
}

Выразим полугруппу строк по конкатенации

class SemiStr extends Semi[String]{
  override def |+|(x: String, y: String): String = x + y
}

Рассмотрим переход от полугруппы строк по конкатенации к «полугруппе целых чисел по конкатенации»

object SemiDemo10 extends App {
  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.|+|(100, 500))
}

>> 100500

Мы построили полугруппу в целых числах (Semi[Int]) у которого бинарная операция сводится к конкатенации строковых представлений числа в десятичной системе счисления (100 |+| 500 => «100» |+| «500» => «100500» => 100500).

Если предыдущий пример слишком банален, то посмотрите на следующее

object SemiDemo16 extends App {
  val f: String => Int = Integer.parseInt(_, 16)
  val g: Int => String = Integer.toHexString

  val x: Semi[String] = new SemiStr
  val y: Semi[Int] = x xmap (f, g)

  println(y.|+|(10, 10))
}

>> 170

Мы построили полугруппу в целых числах (Semi[Int]) у которой бинарная операция сводится к конкатенации строковых представлений числа в шестнадцатеричной системе счисления (10 |+| 10 => «A» |+| «A» => «AA» => 10 * 16 + 10 = 170). Можно убедиться, что такая операция над Int все еще ассоциативна (мы игнорируем случай переполнения Int и отрицательные числа, извините).

В библиотеке Scalaz тоже считают, что полугруппа и моноид — это инвариантные функторы.

package scalaz

object InvariantFunctor {
  /** Semigroup is an invariant functor. */
  implicit val semigroupInvariantFunctor: InvariantFunctor[Semigroup] 
    = new InvariantFunctor[Semigroup] {...}
  /** Monoid is an invariant functor. */
  implicit val monoidInvariantFunctor: InvariantFunctor[Monoid] 
    = new InvariantFunctor[Monoid] {...}
  ...
}

Инвариантный функтор в библиотеках

Лучший способ учить Scala и FP — читать исходный код профессионалов на Scala и FP.

Scalaz — это самая популярная и зрелая из библиотек, которые реализуют абстракции из теории категорий. Во многом дизайн взят из библиотек Haskell = scalaz.InvariantFunctor

Cats — это попытка заново реализовать категориальные абстракции (чем не устраивала Scalaz — не знаю) = cats.functor.Invariant

Play JSON library включает invariant functor, это обсуждают тут и тут.