wps.su

Введение

Каждой парадигме языков программирования свойственны свои механизмы абстрагирования и идиомы, в которых эти механизмы используются.

Если для объектно-ориентированных языков это классы, наследование, полиморфизм, инкапсуляция, делегирование и шаблоны проектирования, где все это используется, то для функциональных языков это шаблоны высшего порядка (generics of higher kind), типы, зависимые от пути (path-dependent types), классы типов (type classes) и идиомы, которые их используют: ковариантный функтор, аппликативный функтор, монада, зависимая функция, моноид, группа и т.п.

Абстракции были перенесены в языки функционального программирования из разных разделов математики. В частности, из возникшего в середине 20-го века нового раздела - "теории категорий". Классификация идиом (приведена только часть из всех существующих) по названиям разделов математики с примерами механизмов Scala:

Идиомы FP	Механизмы Scala	Библиотеки Scala	Разделы математики
Covariant functor, applicative functor, monad, arrow	Type classes, generics of higher kind	Scalaz, Cats	Теория Категорий
Dependent pair, dependent function	Path-dependent types	Shapeless	Математическая логика
Моноид, группа, поле, кольцо	Type classes, generics of higher kind	Algebird, Spire	Алгебра

• Generics of higher king применяют для построения повторно используемой абстракции (например, ковариантный функтор). В ООП таком случае создают родительский тип.
• Type classes используют для того, чтобы применить абстракцию к коду. Например, пользовательский класс становится ковариантным функтором. В ООП в таком случае наследуются от абстрактного родительского класса.
• Path-dependent types позволяют объявлять вложенные типы и ссылаться на них через "пути". В ООП для этого используются модули.

Есть несколько подходов к определению идиом функционального программирования. В данной статье будет использоваться "синтаксический" подход, т.е., подход, основанный на том, что некая идиома это тип с определенным методом (или методами). Этот подход удобен еще и тем, что позволяет свести в общую схему многие категориальные конструкции. Примеры кода будут приводиться для языка Scala. В статье рассмотрены понятия ковариантного, контравариантного и инвариантного функтора.

Методы различных абстракций (единственные требуемые или одни из требуемых):

trait X[T] {
  // ковариантный функтор
  def map[R](f: T => R): X[R]

  // контравариантный функтор
  def contramap[R](f: R => T): X[R]

  // инвариантный функтор
  def xmap[R](f: (T => R, R => T)): X[R]

  // аппликативный функтор
  def apply[R](f: X[T => R]): X[R]

  // монада
  def flatMap[R](f: T => X[R]): X[R]

  // комонада
  def coflatMap[R](f: X[T] => R): X[R]
}

Ковариантный функтор

Ковариантным функтором является тип X, имеющий type parameter T, с методом map, имеющим следующую сигнатуру:

trait X[T] {
  def map(f: T => R): X[R]
}

Примеры ковариантного функтора:

// Option

import java.lang.Integer.toHexString

val i: Option[Int] = Map("a" -> 1, "b" -> 2).get("c")
val s: Option[String] = i map toHexString

// Future

import java.lang.Integer.toHexString
import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.Future

def mult: Int = 11 * 21

val i: Future[Int] = Future(mult)
val s: Future[String] = i map toHexString

// List

import java.lang.Integer.toHexString

val i: List[Int] = List(1, 2, 3)
val s: List[String] = i map toHexString

Ковариантный функтор - это как бы контейнер. Например, Option - это контейнер, где что-то может лежать (Some), а может и нет (None). List - это контейнер, в котором может быть от 0 до n элементов. Но точнее будет сказать, что ковариантный функтор - половина контейнера. Та половина, которая отвечает за извлечение данных, так как нету явного метода "put" для того, чтобы положить данные в контейнер.

Для того, чтобы являться ковариантным функтором, кроме наличия метода с определенной сигнатурой, тип должен соответствовать двум правилам: Identity Law и Composition Law.

Identity Law: для любого ковариантного функтора "func" должно выполняться правило, что IdentityLaw.case0(func) - это то же самое, что и IdentityLaw.case1(func) в следующем примере кода:

object IdentityLaw {
  def case0[T](func: Functor[T]): Functor[T] = identity(func)
  def case1[T](func: Functor[T]): Functor[T] = func.map(identity)
}

identity — это единичная функция из scala.Predef (полиморфная тождественная функция):

def identity[A](x: A): A = x

Таким образом, вызов func.map(identity) ничего не должен менять внутри функтора. Например, если контейнер хранит счетчик и увеличивает его при каждом вызове метода map, то этот контейнер не является ковариантным функтором.

Composition Law: для любого ковариантного функтора "func[T]" и любых функций "f" и "g" должно выполняться правило, что CompositionLaw.case0(func) - это то же самое, что и CompositionLaw.case1(funс):

object CompositionLaw extends App {
  def case0[T, R, Q](func: Functor[T], f: T => R, g: R => Q): Functor[Q] =
    (func map f) map g
  def case1[T, R, Q](func: Functor[T], f: T => R, g: R => Q): Functor[Q] =
    func map (f andThen g)
}

То есть, вызов "map" сначала с функцией "f", потом с функцией "g" должен быть эквивалентен тому, что мы вызываем "map" с функцией-композицией функций "f" и "g".

Рассмотрим, как мог бы выглядеть метод "map" у связного списка:

sealed trait LinkedList[+T] {
  def map[R](f: T => R): LinkedList[R]
}

case object Empty extends LinkedList[Nothing] {
  def map[R](f: Nothing => R): LinkedList[R] = this
}

case class MyList[+T](head: T, tail: LinkedList[T]) extends LinkedList[T] {
  def map[R](f: T => R): LinkedList[R] = MyList(f(head), tail.map(f))
}

val sampleList = MyList(5, MyList(10, Empty))

// Identity Law

println(identity(sampleList) == sampleList.map(identity)) // true

// Composition Law

def f(i: Int) = i + 2
def g(i: Int) = i * 3
val composition = f _ andThen g
val result1 = sampleList.map(f).map(g)
val result2 = sampleList.map(composition)

println(result1 == result2) // true

Контравариантный функтор

Контравариантным функтором является тип X, имеющий type parameter T, с методом, условно называемым contramap, имеющим сигнатуру:

trait X[T] {
  def contramap[R](f: R => T): X[R]
}

Если ковариантный функтор - это половина контейнера, отвечающая за извлечение данных, то в случае контравариантного функтора в качестве примеров нужно рассматривать типы, которые принимают данные в качестве аргументов, но не возвращают как результат функции:

// Ordering

import scala.math.Ordering._

val strOrd: Ordering[String] = String // scala.math.Ordering.String
val f: (Int => String) = _.toString
val intOrd: Ordering[Int] = strOrd on f // "on" в качестве метода "contramap"

То есть, имея способ сравнивать строки и имея функцию преобразования числа в строку, мы можем построить способ сравнивать числа. Еще один пример:

// Writes

import play.api.libs.json._
import play.api.libs.functional.syntax._

case class User(id: Int, name: String)

implicit val userWrites: Writes[User] = 
  (JsPath \ "name").write[String].contramap(_.name)

Зная, как представить строку в json и имея функцию преобразования объекта пользователя в строку, мы получаем способ представления объекта пользователя в json.

Контравариантный функтор должен соответствовать двум правилам: Identity Law и Composition Law.

Identity Law: для любого контравариантного функтора "cofunc" должно выполняться правило, что IdentityLaw.case0(cofunc) - это то же самое, что и IdentityLaw.case1(cofunc) в следующем примере кода:

object IdentityLaw {
  def case0[T](cofunc: Contravariant[T]): Contravariant[T] = identity(cofunc)  
  def case1[T](cofunc: Contravariant[T]): Contravariant[T] = cofunc.contramap(identity)
}

То есть, вызов cofunc.contramap(identity) ничего не меняет внутри контравариантного функтора.

Composition Law: для любого контравариантного функтора "cofunc[T]" и произвольной пары функций f: Q => R и g: R => T должно выполняться правило, что CompositionLaw.case0(cofunc) - это то же самое, что и CompositionLaw.case1(cofunс):

object CompositionLaw {
  def case0[Q, R, T](cofunc: Contravariant[T], f: Q => R, g: R => T): Contravariant[Q] =
    (cofunc contramap g) contramap f
  def case1[Q, R, T](cofunc: Contravariant[T], f: Q => R, g: R => T): Contravariant[Q] =
    cofunc contramap (f andThen g)
}

То есть, последовательный вызов "contramap" с каждой функцией должен быть эквивалентен вызову "contramap" с инвертированной композицией этих функций.

Для примера рассмотрим простой encryptor, который получает из объектов различных типов строку-хэш:

import org.apache.commons.codec.digest.DigestUtils

trait Encryptor[-T] {
  outer =>

  def encrypt(x: T): String

  def contramap[R](f: R => T): Encryptor[R] = new Encryptor[R] {
    def encrypt(x: R): String = outer.encrypt(f(x))
  }
}

object StringEncryptor extends Encryptor[String] {
  def encrypt(x: String): String = DigestUtils.sha1Hex(x)
}

val int2str: (Int => String) = _.toString
val intEnc = StringEncryptor.contramap(int2str)

// Identity Law

val result01 = identity(intEnc).encrypt(2017)
val result02 = intEnc.contramap[Int](identity).encrypt(2017)

println(result01 == result02) // true

// Composition Law

case class Triangle(a: Int, h: Int)

def f(t: Triangle) = 0.5f * t.a * t.h // Triangle => Float
def g(f: Float) = math.round(f) // Float => Int

val composition = f _ andThen g
val result11 = intEnc.contramap(g).contramap(f).encrypt(Triangle(5, 7))
val result12 = intEnc.contramap(composition).encrypt(Triangle(5, 7))

println(result11 == result12) // true

Инвариантный функтор

Если ковариантный функтор - это источник данных, а контравариантный функтор - это приемник данных, то инвариантный функтор совмещает в себе оба этих качества. Используя синтаксический подход, можно сказать, что инвариантный (экспоненциальный) функтор - это тип X, имеющий type parameter T, с методом, условно называемым xmap, имеющим сигнатуру:

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

То есть, для получения функтора X[R] нужно предоставить отображения "f" и "g", которые будут применяться к данным на входе и на выходе.

В качестве примера инвариантного функтора можно привести Format из play.api.libs.json:

// Format

import play.api.libs.json._
import play.api.libs.functional.syntax._

case class User(name: String)

implicit val userFormat: Format[User] =
  (JsPath \ "name").format[String].inmap(User, _.name)

Передав функции для создания объекта пользователя из строки и обратно, мы получаем экземпляр класса Format[User], который объединяет в себе и сериализатор, и десериализатор. В качестве метода "xmap" здесь выступает "inmap".

Инвариантный функтор также должен соответствовать правилам Identity Law и Composition Law.

Identity Law: для любого инвариантного функтора "infunc" должно выполняться правило, что IdentityLaw.case0(infunc) - это то же самое, что и IdentityLaw.case1(infunc) в следующем примере кода:

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

Смысл правила уже известен: infunc.xmap(identity) никак не меняет функтор.

Composition Law: для любого инвариантного функтора "infunc[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](infunc: Invariant[T], f1: T => R, g1: R => T, f2: R => Q, g2: Q => R): Invariant[Q] =
    infunc.xmap(f1, g1).xmap(f2, g2)
  def case1[T, R, Q](infunc: Invariant[T], f1: T => R, g1: R => T, f2: R => Q, g2: Q => R): Invariant[Q] =
    infunc.xmap(f2 compose f1, g1 compose g2)
}

Последовательный вызов "xmap" сначала с функциями "f1" и "g1", затем с функциями "f2" и "g2" должен быть эквивалентен вызову "xmap" с композицией функций "f1" и "f2" и с инвертированной композицией функций "g1" и "g2".

В качестве примера возьмем простейший из контейнеров — 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)
  }
}

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

val f: Option[String] => Option[Int] =
  x => x.map(Integer.parseInt(_, 16))
val g: Option[Int] => Option[String] =
  x => x.map(Integer.toHexString)

val strHolder = new StringHolder
val intHolder = strHolder.xmap(f, g)

// Identity Law

intHolder.put(Some(2017))
val result1 = intHolder.get
val result2 = intHolder.xmap[Option[Int]](x => x, x => x).get

println(result1 == result2) // true

// Composition Law

val f2: Option[Int] => Option[BigDecimal] =
  x => x.map(BigDecimal(_) / 2) // из Int в BigDecimal / 2
val g2: Option[BigDecimal] => Option[Int] =
  x => x.map(d => (d * 2).intValue) // из BigDecimal в Int * 2

val composition1 = f2 compose f
val composition2 = g compose g2

val holder1 = strHolder.xmap(f, g).xmap(f2, g2)
val holder2 = strHolder.xmap(composition1, composition2)

holder1.put(Some(3.5))
holder2.put(Some(3.5))

println(holder1.get == holder2.get) // true

Правила, которым должен следовать инвариантный функтор, не разрешают менять состояние функтора внутри операции "xmap", но это можно делать, например, в "put" и "get" операциях. Поэтому, мы можем добавить логирование, либо другой дополнительный функционал в данных методах.

Описанные в статье понятия являются базой для понимания остальных абстракций из теории категорий, которые являются композициями или более специализированными конструкциями на основе описанных функторов. Например, полугруппа - это инвариантный функтор, а монада - это ковариантный функтор.

На момент написания статьи, версия Scala 2.12.1.

Полезные ссылки:
https://habrahabr.ru/company/golovachcourses/blog/266905/