Оглавление обзора

1. Hom-типы

2. Функторы (данная публикация)

Это вторая вводная часть обзора, посвящённого применению теории категорий в программировании. В первой части представлены некоторые основные определения теории, в том числе, hom-типы, их значения-морфизмы, а также их композиция, позволяющая строить пути вычислений в рамках одной категории. В данной же публикации мы узнаем, как прокладывать пути вычислений через разные категории. Фокус заключается в том, что все категории, которые представлены в этом обзоре, вместе образуют ещё одну категорию, которая называется

Категория категорий

Да, всё так и есть! Ну, почти.

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

Впрочем, нам, простым программистам, не нужно забивать голову такими нюансами)). Дело в том, что на практике мы оперируем лишь инструментами конструктивной математики, которые просто не позволяют получить такого рода парадоксы. Например, если в качестве объектов использовать подкатегории F-типов, то правильнее говорить, что мы получим категорию категорий типов высокого рода. Объекты в ней будут индексированы всеми однопараметрическими конструкторами типов F[_] ().

Но гораздо важнее то, какие морфизмы будут нам полезны в подобных категориях. То есть нужно выяснить, каким будет hom-тип, а также единичный морфизм и композиция:

type Hom[F[_], G[_]]

type Category[Hom[_[_], _[_]]] = ( // ((* => *, * => *) => *) => *
	identity: [F[_]]             => ()                     => Hom[F, F],
	compose : [F[_], G[_], H[_]] => (Hom[G, H], Hom[F, G]) => Hom[F, H]
)

Конечно, мы всегда можем пойти проверенным путём и выбрать, например, константные hom-типы, как мы это делали в первой части обзора. Однако, категория категорий существенно богаче.

Мотивация для программистов

Контейнерные типы F[_] используются в функциональном программировании для «чистого» (то бишь безопасного) обслуживания различных эффектов, в том числе и побочных. Поэтому часто встречаются задачи по «переключению эффекта» — переносу вычислений из одного контейнера (чаще всего Id[_]) в другой:

Стрелка должна работать единообразно, универсально для всех путей вычислений, проходящих через любые объекты-типы. Это значит, что каждой функции F[A] => F[B] ставится в соответствие G[A] => G[B]. Впрочем, такое отображение не обязано быть взаимно однозначным — вполне допустимо, что разные f, g: F[A] => F[B] превращаются в одну и ту же h: G[A] => G[B]. Важно лишь то, что отображение сохранит законы композиции морфизмов из основной подкатегории типов. Притом должна сохраняться ассоциативная композиция и свойства тождественного морфизма identity. Вся диаграмма типов и функций без изменений должна переноситься из подкатегории F в подкатегорию G. Морфизмы с такими свойствами называются функторами.

Определение

Функтор — это такое отношение между категориями, которое каждому морфизму из одной категории ставит в соответствие морфизм из другой категории, сохраняя при этом тождественный морфизм и композицию.

Функтор преобразует морфизмы, сохраняя их композицию, следовательно, все диаграммы исходной категории без разрывов (говорят, «непрерывно») переносятся в конечную. Функтор как бы «встраивает» исходную категорию в целевую, моделирует её внутри конечной. Процитирую Милевски:

… основа понимания — умение создавать модели. Мы постоянно создаём простые модели сложных явлений. Понимая, как работают модели, мы получаем представление о том, как работают сложные явления. Но для этого нам необходимо установить соответствие, отображение, между областью модели и областью изучаемого нами явления. И какое самое важное свойство этого отображения? Наше понимание модели основано на понимании её частей и способов их составления. Поэтому отображение должно сохранять композируемость! Отображения, сохраняющие композируемость, называются функторами.

Во многих источниках можно встретить чуть расширенное определение функтора, включающее обязательное сопоставление объектов начальной категории с объектами конечной. В книге Маклейна такое «сопоставление» даже называется «функцией», что немного сбивает с толку. В нашем случае речь идёт не об обычных функциях, действующих на значениях, но на конструкторах типов, которые на основе одного типа известной структуры конструируют другой тип.

Но задача функтора — трансформировать именно морфизмы одной категории в морфизмы другой! Только если предоставлена реализация такой трансформации, то можно говорить о том, что у нас есть функтор между категориями. (Впрочем, у Маклейна также приводится и упрощённое определение функтора, аналогичное нашему.)

Для произвольных категорий типов hom-тип функтора будет таким:

type Hom[Hom1[_, _], Hom2[_, _]] = [A, B] => Hom1[A, B] => Hom2[A, B]

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

Функторы в подкатегориях типов

Определим класс hom-типов для категории подкатегорий типов (звучит как пенопластом по стеклу))):

type Category[==>[F[_], G[_]]] = (
  identity: [F[_]]             => ()                 => F ==> F,
  compose : [F[_], G[_], H[_]] => (G ==> H, F ==> G) => F ==> H
)

Параметризация стрелкой ещё пригодится нам в следующей части обзора. Сейчас же эта стрелка будет такой:

type Hom[F[_], G[_]] = [A, B] => (F[A] => F[B]) => (G[A] => G[B])

Тривиальный морфизм и композиция определяются так:

given category: Category[Hom] = (
  identity = [F[_]] => () =>
    [A, B] => (fab: F[A] => F[B]) => fab,
  
  compose  = [F[_], G[_], H[_]] => (gh: Hom[G, H], fg: Hom[F, G]) =>
    [A, B] => (fab: F[A] => F[B]) => (gh[A, B] compose fg[A, B])(fab)
)

Определим метод расширения для функций в подкатегории F-типов:

extension [F[_], A, B](fab: F[A] => F[B])
  def fmap[G[_]](using functor: Hom[F, G]): G[A] => G[B] =
    functor(fab)

Название метода fmap происходит от «function mapping» — отображение функций. Вот пример использования этого метода:

// сперва определяем функтор между категориями Option и List
given functorOptLst: Hom[Option, List] =
  [A, B] => (fOpt: Option[A] => Option[B]) => (listA: List[A]) =>
    fOpt(listA.headOption).map(_ +: functorOptLst(fOpt)(listA.tail)).toList.flatten
    //                     ↑↑↑                да, я читер)))                ↑↑↑↑↑↑↑

val fOpt: Option[Int] => Option[String] = _.map("строка " + е _) // почему бы и нет?))
val gLst: List  [Int] => List  [String] = fopt.fmap[List]
//                                             ↑↑↑↑ fmap!

gLst(List(40, 2)) // List(строка 40, строка 2)

Сигнатура hom-типа отличается от того, что принято считать функтором в программировании. Ведь обычно начальной выбирается категория всех типов, эквивалентная подкатегории, основанной на конструкторе типов Id[_]. В таком случае получается извеcтный класс типов Functor[_[_]]. Причины появления таких упрощённых формулировок мы рассмотрим далее.

Изоморфизм категорий

В предыдущей части обзора был определён изоморфизм объектов категории — это соотношение эквивалентности, задаваемое двумя противоположно направленными морфизмами между объектами, причём обе их композиции равны тождественным морфизмам. Теперь мы работаем с категорией подкатегорий типов — как тут обстоят дела с изоморфизмами подкатегорий ?

Формально тут всё как и всегда — чтобы между объектами C[_] и D[_] существовал изоморфизм, нужно предоставить два функтора f: Hom[C, D] и g: Hom[D, C], так, чтобы

• summon[Category].compose(f, g) совпадало с summon[Category].identity[D]()

• summon[Category].compose(g, f) совпадало с summon[Category].identity[C]()

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

type Pair[X] = X × X
type Pow2[X] = Boolean => X  // X²

Сперва определяем встречные функторы

val functorPairPow2: Hom[Pair, Pow2] =
  [A, B] => (f: Pair[A] => Pair[B]) => (a2: Pow2[A]) =>
    (b: Boolean) =>
      val pairB = f(a2(false), a2(true))
      if b then pairB._2 else pairB._1

val functorPow2Pair: Hom[Pow2, Pair] =
  [A, B] => (f: Pow2[A] => Pow2[B]) => (pairA: Pair[A]) =>
    val b2 = f(b => if b then pairA._2 else pairA._1)
    b2(false) -> b2(true)

Затем, строим любую их композицию. Для простоты, такую:

val roundUp: Hom[Pair, Pair]  = summon[Category].compose(functorPow2Pair, functorPairPow2)

А теперь продемонстрируем, что эта композиция эквивалентна тождественному морфизму

val morph1: Pair[Int] => Pair[Int] = p => (p._1 * 2, p._2 + 2)
val morph2: Pair[Int] => Pair[Int] = roundUp(morph1) // roundUp сохраняет исходный морфизм!

// проверяем, что мы получили ту же самую функцию
morph1(21, 40) // (42,42)
morph2(21, 40) // (42,42)

Путь вычисления morph2 начинается в категории Pair[_], затем идёт в категорию Pow2[_] и возвращается обратно. Этот длинный путь не меняет ничего, как будто мы и не покидали исходную категорию Pair[_]! Такие построенные на паре функторов пути работают одинаково для всех отправных точек, что и позволяет говорить об изоморфизме категорий Pair[_] и Pow2[_].

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

Если присмотреться к введённым в предыдущем разделе hom-типам, то станет заметно, что они не покрывают все случаи, удовлетворяющие законам функторов. Функтор должен отображать все пути из исходной категории в конечную, однако, сделать это можно не только в лоб, но и обратив все стрелки! Такой функтор будет называться контравариантным в отличие от приведённого выше, называемого ковариантным:

type     CovariantHom[F[_], G[_]] = [A, B] => (F[A] => F[B]) => (G[A] => G[B])
type ContravariantHom[F[_], G[_]] = [A, B] => (F[A] => F[B]) => (G[B] => G[A])
//                                                                 ↑       ↑

Для контравариантного функтора обычно используются методы с такими названиями:

extension [F[_], A, B](fab: F[A] => F[B])
  inline def fcontramap[G[_]](using contraFunctor: ContravariantHom[F, G]): G[B] => G[A] =
    contraFunctor(fab)

extension [G[_], A](ga: G[A])
  inline def contramap[F[_], B](f: F[B] => F[A])(using ContravariantHom[F, G]): G[B] =
    f.fcontraMap[G](ga)

Контравариантные функторы иногда удобнее воспринимать как обычные, ковариантные, но в которых исходная категория заменена на дуальную (см. предыдущую часть обзора):

Для двух заданных категорий обычно не ставится вопрос «функтор какой вариантности нам понадобится?» Скорее, приходится выяснять, если между ними можно построить функтор, то будет ли он ко- или контравариантным.

Если исходная и конечная категории фиксированы, то между ними можно построить либо ковариантный функтор, либо контравариантный, либо ни тот, ни другой. И только в очень редких случаях можно построить оба типа функтора. Нас прежде всего интересуют такие подкатегории типов, которые определяются конкретным конструктором типов F[_]. Очевидно, что вариантность функторов между двумя такими категориями будет определятся только устройством их конструкторов типов.

За точку отчёта принято брать общую категорию типов. Тогда очевидно, что функтор между ней и подкатегорией на основе Id[_] будет ковариантным. Также ковариантными будут функторы между любыми подкатегориями, основанными на Id, List, Option, Reader, Witer и проч. С другой стороны, контравариантными будут функторы между этими же категориями, и, например, основанной на таких конструкторах типов:

type ToString = [A] =>> A => String
type ToInt    = [A] =>> A => Int

Например,

given contraFunctor: ContravariantHom[Id, ToInt] =
  [A, B] => (f: A => B) => (_ : ToInt[B]) compose f

val f: Id   [Double] => Id   [Long  ] = Math.round
val g: ToInt[Long  ] => ToInt[Double] = fcontraMap(f)

val a: ToInt[Long  ] = _.toInt
val b: ToInt[Double] = g(a)

b(42.1) // 42

А вот функтор между этими двумя категориями (построенными на контравариантных конструкторах типов) будет снова ковариантным! Действительно,

given covariantFunctor: Hom[ToInt, ToString] = // ковариантный функтор!
  [A, B] => (f: ToInt[A] => ToInt[B]) => (toStrA: ToString[A]) =>
    f(toStrA andThen {(_ : String).length}) andThen {(_ : Int).toString}

val f: ToInt   [Long] => ToInt   [Double] = _ compose Math.round
val g: ToString[Long] => ToString[Double] = fmap(f)

val a: ToString[Long  ] = "covariantTest: " + _.toString
val b: ToString[Double] = g(a)

b(42.1) // 17

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

type Inv = [A] =>> A => A

Обходной манёвр для таких инвариантных типов будет рассмотрен далее.

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

В предыдущем обзоре обобщённых типов говорилось, что вариантность конструкторов типов однозначно определяется «знаками позиций» типа параметра. Если одно упоминание параметра находится слева нечётного количества стрелок => (т.е. нечётное количество раз является аргументом функций), то его позиция отрицательная, а иначе — положительная. Если позиции всех упоминаний параметра положительные (Id, Option и проч.), то обобщённый тип называется ковариантным, а если все отрицательные (ToString, ToInt) — контравариантным. Если же в определении параметры встречаются в позициях с разными знаками (Inv), такой обобщённый тип будет инвариантным.

В Scala можно явно проставить у типа параметра его знак, если он одинаковый для всех упоминаний в определении типа:

type ToString[-A] =         A       => String   // `A` упомянут левее ОДНОЙ стрелки
type MyOption[+A] = [X] => (A => X) => (X => X) // `A` упомянут левее ДВУХ  стрелок

Если знак указан явно, то его придётся учитывать в некоторых случаях композиции конструкторов типов, когда у компилятора не будет возможности выяснить знак самостоятельно.

Эндофункторы

Выше был показан пример функтора между подкатегориями Option и List, который абсолютно бесполезен на практике))). Он был нужен для демонстрации концепции функтора. Дело в том, что реализация вручную функций вида F[A] => F[B] — занятие весьма неблагодарное, приводящие к многократному копированию шаблонного кода. Гораздо проще определять функции вида A => B, чтобы потом их «поднимать» их в подкатегорию F[_] с помощью функтора Hom[Id, F]. Именно такие упрощённые функторы и получили распространение в программировании:

type Functor      [F[_]] =     CovariantHom[Id, F]
type Contravariant[F[_]] = ContravariantHom[Id, F]

Этот функтор связывает общую категорию типов с её подкатегорией, значит он начинается и заканчивается во всё той же категории типов! Функторы, чьи начальная и конечная категория совпадают, называются эндофункторами. Замечательным свойством эндофункторов является то, что их можно применять многократно, переходя ко всё более глубоким слоям «матрёшки» подкатегорий. В свою очередь, «разматрёшивание» вложенных F[_] — самая типичная задача при чистой работе с эффектами в функциональном программировании. Но об этом поговорим в других частях обзора.

Тип Functor, так же как и Hom для подкатегорий типов, удобнее использовать как класс типов, неявно передавая его экземпляры через контекст. С ним удобно использовать такие методы расширения:

extension [A, B](f: A => B)
  inline def lift[F[_]: Functor as functor]: F[A] => F[B] =
    functor(f)

extension[F[_]: Functor as functor, A] (fa: F[A])
  inline def map[B](f: A => B): F[B] =
    f.lift[F](fa)
//                  ↓    ↓
extension [A, B](f: B => A)
  inline def lift[F[_]: Contravariant as functor]: F[A] => F[b] =
    functor(f)

extension[F[_]: Functor as functor, A] (fa: F[A])
  inline def contramap[B](f: B => A): F[B] =
    f.lift[F](fa) //         ↑    ↑

В данном случае метод lift не просто отображает функции, как fmap, но «поднимает» их в подкатегорию F. На практике же по привычке чаще используют более императивный метод map, отображающий значения F[A] в F[B] с помощью функции A => B.

Думаю, всем и так знаком принцип работы метода map в Scala, но, на всякий случай, приведу такой простой пример:

type Writer[A] = (A, String)
given writerFunctor: Functor[Writer] =
	[A, B] => (f: A => B) => (pair: Writer[A]) =>
		val res = f(pair._1)
		res -> s"${pair._2} -> $res"

val a: Writer[Int   ] = (42, "число 42")
val b: Writer[String] = a.map("строка " + _) // ("строка 42", "число 42 -> строка 42")
//                        ↑↑↑

val f: Boolean => String  = if _ then "true" else "false"
val g: String  => Int     = _.length
val h: Int     => Boolean = _ % 2 != 0

given listFunctor: Functor[List] = [A, B] => (f: A => B) => (_: List[A]).map(f) // встроенный метод

val path1: List[Boolean] => List[Boolean] = (h            compose g            compose f           ).lift[List]
val path2: List[Boolean] => List[Boolean] =  h.lift[List] compose g.lift[List] compose f.lift[List]

val bLst = List(true, false)       // любой спиок булевеских значений
assert(path1(bLst) == path2(bLst)) // List(false, true)

В библиотеке Cats ковариантный и контравариантный эндофункторы представлены классами типов Functor и Contravariant.

При обсуждении функторов иногда говорят о «подъёме» не только функций, но и самих значений: lift: A => F[A]. В Haskell есть так называемый «pointed functor» — стандартный эндофунктор, дополненный функцией point, «поднимающей» значения. Но на самом деле эта функция не имеет прямого отношения к функторам между подкатегориями типов.

Конструкторов типов (Option, List, …) часто самих некорректно называют функторами. Причина кроется в тяжёлом наследии языка Haskell — основоположника статически типизированного функционального программирования. Дело в том, что там у классов типов допускается только единственная реализация. То есть, в Haskell не получится одновременно реализовать моноиды для сложения и умножения (только через извращения).

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

Кроме того, обобщённые классы вроде List, Option зачастую уже имеют при себе ООП-шные методы map, задающие поведение эндофунктора в категории типов. И в этом смысле их вполне даже простительно называть функторами… Тем не менее, необходимо помнить, что даже для одного контейнерного типа F[_] в зависимости от контекста могут предоставляться функторы с разным поведением.

Для наглядности приведу и другие примеры нескольких реализации функтора для одного F[_]. Не стану рассматривать «нечистые» реализации, даже с банальным println. Также не интересны реализации, проверяющие тип во время исполнения, или использующие встроенные функции неявного преобразования типа (в том числе, встроенные методы, вроде toString и equals) — они нарушают параметрический полиморфизм, следовательно, и законы функтора. Но даже кристально чистые, универсально полиморфные реализации функтора для знакомого List способны преподнести сюрпризы:

given darkFunctor: Functor[List] =
  [A, B] => (f: A => B) => (_: List[A]).map(f).reverse
  //                                           ↑↑↑↑↑↑↑

val func:         Int  =>      String  = (_: Int).toString
val lstFunc: List[Int] => List[String] = func.lift[List]
val lst = List(4, 2)

lstFunc(lst) // List("2", "4")

Остерегайтесь таких реализаций! Даже не смотря на то, что формально они вполне законопослушные.

Функториальность и подтипизация

В Scala, как и некоторых других языках программирования, основное назначение механизма контроля вариантности конструкторов типов типов F[_] заключается в «пробросе подтипизации». Напомню, если A <:< B, то для ковариантного F[+_] будет F[A] <:< F[B], а для контравариантного G[-_] — G[B] <:< G[A].

Фишка в том, что подтипизация — это, по определению, возможность использовать термы ( значения) подтипа там, где ожидается супертип. В таких случаях неявно вызывается функция приведения типа. Таким образом, вариантность конструкторов типов можно перефразировать в функциях так: для F[+_] и любых A и B, если предоставлена функция (неявного приведения) A => B, то мы автоматически получаем функцию (неявного приведения) F[A] => F[B]. Ничего не напоминает?

Да, это уже знакомый нам ковариантный эндофунктор, основанный на F[+_]! И для контравариантных G[-_] мы также имеем поведение соответствующего эндофунктора. То есть, компилятор уже умеет предоставлять доказательства функториальности конструкторов типов!

К сожалению, исторически сложилось так, что в современных популярных языках программирования этот механизм безнадёжно сломан. Изначально он появился как ООП-шный инструмент работы с иерархией наследования классов — организация размещения объекта в памяти такова, что смена типа от подкласса к суперклассу происходит совершенно бесплатно ещё на этапе компиляции. Позднее добавилась странная, слабо обоснованная подтипизация числовых типов данных (вроде Int <:< Long) и появились специальные типы (Any, Nothing), для которых в систему подтипизации встраивались отдельные костыли.

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

И даже в таком языке, как Scala нет встроенной поддержки эндофункторов, позволяющей без лишних телодвижений вручную переводить F[A] в F[B], если есть функция A => B, для любых F[+_]. Для этого приходится подключать хоть и популярные, но разношёрстные сторонние библиотеки, вроде Scalaz, или Cats, или велосипедить функторы вручную.

Бифункторы

В предыдущей части обзора упоминалось, что из двух любых категорий всегда можно построить новую, которая будет называться произведением категорий. Её объектами будут пары объектов, а морфизмами — пары морфизмов.

Функтор из произведения категорий в другую категорию называется бифунктором (латинская приставка «bi-» означает «двойной»):

В случае категорий типов бифунктор определяется двухпараметрическим конструктором типов:

type Bi[A, B] // (*, *) => *

Он переводит объекты категориального произведения в категорию типов. Сам же функтор должен преобразовывать морфизмы. Соответсвующий hom-тип будет иметь вид

type Bifunctor[Bi[_, _]] = [A, B, C, D] => (A => C, B => D) => (Bi[A, B] => Bi[C, D])

Очевидно, что такой бифунктор представляет сразу два (ковариантных) функтора — по одному для каждой исходной категории (для каждого параметра Bi[_, _]). В библиотеке Cats у класса типа Bifunctor есть методы получения обеих функторов, а также методы расширения map и leftMap для преобразования правого и левого параметров соответственно.

Для бифунктора привычны такие методы расширения:

extension [A, B, C, D] (fg: (A => C, B => D))
  inline def fbimap[Bi[_, _]: Bifunctor as bifunctor] = bifunctor[A, B, C, D].tupled(fg)

extension [Bi[_, _]: Bifunctor, A, B] (biab: Bi[A, B])
  inline def bimap[C, D](f: A => C, g: B => D) = (f, g).fbimap[Bi](biab)

Самые важные бифункторы связаны с суммой и произведением типов:

infix type + = [A, B] =>>  A Either B
infix type × = [A, B] =>> (A   ,    B)
//             ↑↑↑↑↑↑     ↑↑↑↑↑↑↑↑↑↑↑↑
//         произведение     категория
//          категорий         типов

Классы типов Bifunctor реализуются для них так:

given sumBifunctor: Bifunctor[+] =
  [A, B, C, D] => (f: A => C, g: B => D) => (ab: A + B) =>
    ab.map(g).left.map(f)

given prodBifunctor: Bifunctor[×] =
  [A, B, C, D] => (f: A => C, g: B => D) => (ab: A × B) =>
    f(ab._1) -> g(ab._2)

А вот пример использования:

val stringOrInt: String + Int = Left("2b")

stringOrInt.bimap(
  "To be or not to be? " + _,
  _ => 42
) // каков же ответ?

По аналогии с бифункторами можно ввести и мультифункторы на основе конструкторов типов от большего числа параметров. Например:

type Trifunctor[Tri[_, _, _]] = [A1, A2, A3, B1, B2, B3] =>
  (A1 => B1, A2 => B2, A3 => B3) => (Tri[A1, A2, A3] => Tri[B1, B2, B3])

Диагональный функтор

Если в определении бифунктора обратить стрелку, по мы получим диагональный функтор:

Он как бы встраивает категорию в произведение «по диагонали»:

Очевидно, что принцип «диагональности» соблюдается и для морфизмов — функтор просто дублирует каждый морфизм исходной категории.

Реализовать соответствующий конструктор типов сложнее, так как объекты конечной категории представляют собой пары типов, а не отдельные типы. И, тем не менее, это возможно:

type Δ[A] =  [Bi[_, _]     ] =>> Bi[A, A]
//     *  => (  (*, *) => *) =>  *

Тут нас выручает кодирование Чёрча — чем бы ни было то, что мы хотим использовать, важно лишь то, как именно мы будем это использовать! В данном случае показано, что чтобы воспользоваться парой типов, нужно предоставить двухпараметрический конструктор Bi[_, _].

Hom-тип диагонального функтора для категории типов будет такой полиморфной функцией:

type FunctorDiag = [A, B] => (A => B) => [Bi[_, _]: Bifunctor] => (Bi[A, A] => Bi[B, B])

Этот hom-тип сам по себе не параметризирован и его реализация по сути единственна, поэтому опишем её как обычную функцию, которую не нужно неявно передавать через контекст:

val functorDiag: FunctorDiag =
  [A, B] => (f: A => B) => [Bi[_, _]: Bifunctor] => (aa: Bi[A, A]) =>
    aa.bimap(f, f)

Для удобства использования определим такие методы расширения:

extension [A, B](f: A => B)
  inline def fmapBi[Bi[_, _] : Bifunctor]: Bi[A, A] => Bi[B, B] = functorDiag(f)[Bi]

extension [Bi[_, _] : Bifunctor, A](biaa: Bi[A, A])
  inline def mapBi[B](f: A => B): Bi[B, B] = f.fmapBi[Bi](biaa)

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

Сама идея диагонального функтора позволяет работать не только с бифункторами, но и с мультифункторами, то есть связывать исходную категорию не только с её категориальным произведением на себя же , но и с любым количеством таких произведений (просто представьте себе диагональ n-мерного куба))). Это приводит к необходимости обобщить -кратное категориальное произведение, что в свою очередь порождает другую трактовку диагонального функтора —

Константный функтор

Многократное произведение категории на саму себя можно представить себе как функциональное отображение из дискретной категории , состоящий из объектов-индексов, в :

То есть, каждый объект из категории индексов приводит к соответствующему объекту-множителю категориального произведения!

Такое межкатегориалное отображение можно рассматривать как функтор — он переводит тождественные морфизмы из одной дискретной категории в другую, то есть буквально индексирует объекты объектами . Семейство этих функторов образует свою собственную категорию . Можно сказать, что она представляет собой различные способы индексирования. Категория моделирует -кратное категориальное произведение на саму себя.

Среди всех таких функторов есть «диагональные» , которые отображают тождественные морфизмы каждого в один и тот же тождественный морфизм некоторого фиксированного объекта . То есть, такое отображение не зависит от того, какой индекс ему передадут на вход — оно всегда вернёт константу !

А вся совокупность этих константных для разных представляет собой как раз диагональный функтор:

Наглядно это можно представить так:

Если — это категория типов, а — дискретная категория из двух элементов, мы получаем конструкцию, изоморфную типу Δ[_], определённому ранее. Вот только чтобы её реализовать честно, нам так или иначе пришлось бы привлекать зависимые типы, но мы (уже договорись, верно?) постараемся не затрагивать эту тему в данном обзоре.

Зато мы можем рассмотреть другую полезную ситуацию, если выберем в качестве индексирующей всю ту же дискретную категорию типов . Тогда превращается в конструкторы типа вида . Ведь конструкторы типов можно трактовать не только как подкатегории типов, но и как эндофункторы в дискретной категории типов!

Диагональный же функтор будет таким:

type Const[C] = [I] =>> C // не важно, какой I, вернётся константа C

Реализация класса типов Functor[Const] также проста, как и сам этот тип Const[C] — все функции просто схлопываются в identity[C]. Кстати, это тот самый случай, когда для конструктора типов можно предоставить реализации как ковариантного, так и контравариантного функторов.

Но не нужно недооценивать такую простоту! Тип Const[C] частенько встречается на практике (чаще в библиотечном коде). Нам же константные функторы пригодятся в продолжении данного обзора для формулирования типов через их универсальные свойства.

Профункторы

Бифункторы, представленные ранее, являлись ковариантными по обеим параметрам. Переставив пару параметров местами (или обратив пару стрелок), можно получить контравариантный бифунктор, который также может быть полезен, но, признаться, не встречал необходимости его использования на практике.

Гораздо большее значение имеют бифункторы, которые контравариантны лишь по одному параметру: Pro[-_, +_]. Бифунктор, в котором в произведении категорий одна из них выбрана дуальной имеет отдельное название — профунктор:

Важность профункторов в программировании помогает раскрыть, пожалуй, самый простой из них:

infix type =>[-A, +B] = Function[A, B]

Профункторы в категориях типов представляют функциональные отношения! Да, контравариантность сама по себе всегда подразумевает функции, но профункторы одновременно параметризированы как входом, так выходом. Также, как и бифунктор, профунктор можно разложить на два функтора — ко- и контраваринатный.

Если вам показалось (как и мне поначалу), что профункторами могут быть только функции вида F[A] => G[B], то посмотрите на такой пример:

type MyPro[-A, +B] = (A, B => String) => String

val myPro1: MyPro[Boolean, Int] = (b: Boolean, intToStr: Int => String) =>
  intToStr(if b then 42 else 0)
//         ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ это Functon[Boolean, Int]

val myPro2: MyPro[Boolean, Int] = (b: Boolean, intToStr: Int => String) =>
  if b then intToStr(42) else "это ложь!"

Хотя профункторы всегда можно представить как некие функции (для появления контравариантности), все они не укладываются в какой-либо общий шаблон функции.

Hom-тип профунктора строится по аналогии с бифунктором:

type Bifunctor [Bi [_, _]] = [A, B, C, D] => (A => C, B => D) => (Bi[A, B] => Bi[C, D])
type Profunctor[==>[_, _]] = [A, B, C, D] => (C => A, B => D) => (A ==> B) => (C ==> D)
//                                            ↑    ↑ - поменялись местами

Для него характерны такие методы расширения:

extension [A, B, C, D] (fg: (C => A, B => D))
  inline def fdimap[==>[_, _]: Profunctor as profunctor] = profunctor[A, B, C, D].tupled(fg)

extension [==>[_, _]: Profunctor, A, B] (ab: A ==> B)
  inline def dimap[C, D](f: C => A, g: B => D) = (f, g).fdimap[==>](ab)

Так как латинская приставка «bi-» уже занята для бифунктора, то тут используется уже греческая приставка «di-», которая означает (кто бы мог подумать?) то же самое!)))

В Cats также есть класс типов Profunctor, в котором, помимо dimap, есть его частные случаи — методы lmap, rmap с очевидной реализацией. Важная практическая разновидность профункторов — стрелки — упоминалась мною в обзоре обобщённых типов. Мы ещё вернемся к ним ближе к концу данного обзора.

Существуют такие конструкторы типов F[_], в которых тип-параметр встречается как в положительных, так и в отрицательных позициях. В таких ситуациях не получится честно предоставить экземпляр ни ко-, ни контравариантного эндофунктора для F[_]. Но, как вы возможно уже догадались, нас выручит профунктор!

Действительно, любой F[_] всегда можно переписать в виде Pro[-_, +_] так, чтобы F[A] = Pro[-A, +A]. Если при этом предоставить корректное преобразование Pro[A, A] => Pro[B, B] на основе функций из общей категории типов, то мы получим инвариантный функтор:

type Invariant[F[_]] = [A, B] => (A => B, B => A) => (F[A] => F[B])

Вот типичные методы расширения для инвариантного функтора:

extension [A, B] (fg: (A => B, B => A))
  inline def fimap[F[_]: Invariant as ifunctor] = ifunctor[A, B].tupled(fg)

extension [F[_]: Invariant, A] (fa: F[A])
  inline def imap[B](f: A => B, g: B => A) = (f, g).fimap[F](fa)

Инвариантные F[_] обычно описывают процессы обработки значений одного типа. Т.е. по сути они являются частным случаем Pro[-_, +_], когда в обе дырки подставлен один и тот же тип. Это могут быть, например механизмы сериализации/десериализации (даже будучи распределённым, это один самосогласованный процесс), или реализация бинарной операции (полугруппа) и т.п.

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

Функторы для любых F[_]

В моих предыдущих обзорах демонстрировалось, что любой тип можно представить в виде алгебраического выражения, состоящего из некоторых предустановленных типов (Nothing, Unit, …) а также сумм, произведений и экспоненциалов. Обычные ООП-шные классы, (запечатанные) трейты со своей иерархией наследования — всё это прекрасно описывается алгебраическими операциями над типами. Такие алгебраические выражения можно встраивать друг в друга, получая более сложные типы.

Сейчас, мы видели, что для суммы, произведения и экспоненциала типов типов есть свои очевидные реализации ко-, контравариантных функторов (напомню, профунктор для экспоненциала представляет собой пару функторов разной вариантности). Для константных конструкторов типов реализация всех функторов вообще тривиальна. А можно ли столь же естественным образом автоматически предоставлять функтор для любых конструкторов типов F[_]?

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

Не будем полагаться на магию компилятора и проверим, как, например, ковариантные эндофункторы прокидываются через композицию конструкторов типов F ∘ G. автоматический вывод композитного функтора можно организовать так:

given compFunctor: [F[_] : Functor as fFunctor, G[_] : Functor as gFunctor] => Functor[F ∘ G] =
	[A, B] => (f: A => B) => (fFunctor[G[A], G[B]] compose gFunctor[A, B])(f)

Пусть у нас есть экземпляры функторов для List[_] и WighLog[_]:

given listFunctor: Functor[List] = [A, B] => (f: A => B) => (_: List[A]) map f

type WithLog[A] = (String, A)
given loggerFunctor: Functor[WithLog] = [A, B] => (f: A => B) =>
	(withLog: WithLog[A]) => withLog.copy(_2 = f(withLog._2))

Тогда мы можем любую функцию «поднять» в категорию List ∘ WithLog (композитный функтор будет выведен автоматически):

val getStrLength = (_: String).length
val getLengths = getStrLength.lift[List ∘ WithLog] // using compFunctor

Убеждаемся, что всё работает как задумано:

val lst: (List ∘ WithLog)[String] = List("журнал 1" -> "0", "журнал 2" -> "42")
getLenghts(lst) // List(("журнал 1", 1), ("журнал 2", 2))

Такое поведение соответствует ещё одному функтору — между категорией F-подкатегорий типов и дискретной категорией эндофункторов! Собственно, compFunctor как раз описывает эту функториальность, отображая композицию конструкторов типов [F[_], G[_]] =>> G ∘ F в композицию эндофункторов (Functor[F], Functor[G]) => Functor[G ∘ F].

В некоторых библиотеках можно найти автоматический вывод функторов для произвольных обобщённых типов. Например, подключив Kittens из экосистемы Cats, можно лишь прописать import cats.derived.* и явно привязать требуемый класс типов к обобщённому классу с помощью ключевого слова derives:

import cats.derived.*

enum CList[+A] derives Functor:
  case CNil
  case CCons(head: A, tail: CList[A])

Но также это можно сделать в полностью автоматическом режиме, просто импортировав в контекст cats.derived.auto.functor.given — функторы станут доступны для произвольных конструкторов типов.

Дополнительная литература

Материала по функторам в интернете полно. Здесь упомяну лишь несколько статей с Хабра:

• пара публикаций из цикла «FP на Scala»:

  • Что такое функтор?

  • Invariant Functor

• пара переводов статей Кшиштофа Граека:

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

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

• Функторы, аппликативные функторы и монады в картинках — о работе с ковариантными обобщёнными типами, как с контейнерами.

• Функторы — перевод главы книги «Теория категорий для программистов».

Промежуточный итог

Итак, в этой части мы познакомились с самой концепцией функтора — морфизма в категории категорий, рассмотрели основные свойства функторов между категориями типов, а также перечислили наиболее важные разновидности — они пригодятся нам в дальнейшем.

Возможно вас удивит, почему при обсуждении разновидностей функторов здесь не упоминались аппликативные. Дело в том, что такого понятия нет в теории категорий. Аппликативные, так же как и указывающие функторы придумали хаскелисты, посчитав их удобными инструментами для программирования. Но сами эти концепции существенно сложнее, чем просто функторы и мы рассмотрим их в последующих частях обзора.

В предыдущей части были представлены подкатегории типов, основанные на конструкторах типов F[_]. И, не смотря не то, что с одним и тем же F[_] можно построить множество категорий, выбирая разные hom-типы и способы композиции морфизмов, мы договорились, что по умолчанию морфизмами всегда будут функции. Тождественный морфизм и композиция для них естественны и встроены в основную библиотеку Scala. В этом смысле конструкторы типов удобно ассоциировать с подкатегориями, говоря, например, о категориях List, или Option. Но даже тут я стараюсь избегать фраз типа «List — это категория».

Традиционно эти же рассуждения переносятся на функторы — так как для каждого F[_] есть свои естественные реализации функторов, то часто можно услышать, что «List и Option — это функторы». (Меня каждый раз коробит, когда слышу такое, а тут ещё самому пришлось написать))). Отчасти такая точка зрения возникла из ограничений Haskell, где у любого класса типов возможна лишь единственная реализация.

Иногда это оправдывают тем, что обобщённые классы List и Option в Scala имеют встроенные методы map, т.е. они «владеют основной возможностью функтора». Проблема в том, что такое ООП-шное видение ломает простоту, предлагаемую теорией категорий, отделяет существующие классы F[_], в которых реализован map, от всех остальных типов G[_], для которых нет такой встроенной возможности. И это при том, что компилятор и так умеет проверять вариантность (= функториальность) любых обобщённых типов. Да и само теоретическое существование наиболее полезных функторов для любых типов и так уже реализуется в сторонних библиотеках, вроде упомянутой kitten…

Основная задача эндофункторов в программировании заключается в переводе морфизмов-функций общей категории типов в морфизмы её F-подкатегории. Наиболее правильно реализовывать эту возможность в экземплярах класса типа Functor[_[_]]. И стоит учитывать, что технически эти реализации могут быть разными. Другими словами, только значения fFunctor: Functor[F] справедливо называть функторами. Фраза «функтор List» корректна лишь в том смысле, что имеется в виду «конкретный функтор для List[_]».

Ещё одна беда, связанная с традиционной реализацией функторов в Scala, заключается в использовании наследования. Например, в той же Cats ко- и контравариантные функторы наследуют инвариантный. Получается, что инвариантный функтор — это не произведение ко- и контравариантных функторов, но их сумма (да ещё плюс он сам как таковой)!.. Такая нелепость оправдывается задачами оптимизации в объектно-ориентированной среде JVM, но архитектурно это совершенно некорректно, привносит ненужные ограничения и вводит в заблуждение программистов. Короче, будьте внимательны и пусть ясность ваших мыслей не будет затуманена)).

В первой части обзора мы познакомились с категориями типов, а в этой части мы работали в категории подкатегорий типов. Но до монад всё ещё добрались)). А это значит, что

В следующей части мы будем работать уже с категорией функторов!