Функтор

Формальное определение

Функтор — это преобразование из категории A

в категорию B. Такие преобразования часто изображаются стрелкой: A -> B (или через метод map). Функтор сохраняет структуру: что было связано в исходной категории, будет связано и в целевой.

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

Функтор (F) расширяет инвариантный функтор и должен следовать следующим законам (помимо законов инвариантного функтора):

Identity (тождественность): Если определен метод идентификации identity такой, что: identity(a) == a, тогда map(fa)(identity) == fa. Другими словами: если мы отобразим функцию identity на функтор, функтор, который мы получим, должен быть таким же, как исходный функтор.
Composition (композиция): Если определены два метода f и g, тогда fa.map(f).map(g) == fa.map(g(f(_))). Другими словами: композиция двух функций и последующее отображение результирующей функции на функтор должно быть таким же, как сначала отображение одной функции на функтор, а затем отображение другой.

Стоит отметить, что здесь и далее речь идет только о чистых функциях identity
, f и g.

Определение в виде кода на Scala

trait Functor[F[_]] extends InvariantFunctor[F]:
  extension [A](fa: F[A])
    def map[B](f: A => B): F[B]

    override def xmap[B](f: A => B, g: B => A): F[B] = fa.map(f)

  def lift[A, B](f: A => B): F[A] => F[B] = _.map(f)

  def mapply[A, B](a: A)(f: F[A => B]): F[B] = map(f)((ff: A => B) => ff(a))

  def fproduct[A, B](fa: F[A])(f: A => B): F[(A, B)] = map(fa)(a => (a, f(a)))

Как видно из примера выше, функтор позволяет определить дополнительные операции:

"поднимает" функцию A => B до функции преобразования функторов F[A] => F[B]
применяет функтор от функции преобразования из A в B (F[A => B]) к элементу типа A и получает функтор от B
по функтору от A и функции преобразования из A в B позволяет получать функтор от кортежа (A, B)

Примеры

"Обертка" является функтором

import cats.Id

given idFunctor: Functor[Id] with
  extension [A](as: Id[A]) override def map[B](f: A => B): Id[B] = Id(f(as))

Докажем, что Id

удовлетворяет функториальным законам.

сохраняет единичные морфизмы: map(fa)(identity) == fa
- по определению метода map получим: Id(a).map(identity) == Id(identity(a)) == Id(a)
сохраняет композицию: fa.map(f).map(g) == fa.map(g(f(_)))
- по определению метода map получим: Id(a).map(f).map(g) == Id(f(a)).map(g) == Id(g(f(a))) и Id(a).map(g(f(_))) == Id(g(f(a)))

Option

given optionFunctor: Functor[Option] with
  extension [A](optA: Option[A])
    override def map[B](f: A => B): Option[B] =
      optA match
        case Some(a) => Some(f(a))
        case None    => None

Докажем, что Option

удовлетворяет функториальным законам.

сохраняет единичные морфизмы: map(fa)(identity) == fa
- если fa равно None, то по определению метода map получим: None.map(identity) == None
- если fa равно Some(a), то по определению метода map получим: Some(a).map(identity) == Some(identity(a)) == Some(a)
сохраняет композицию: fa.map(f).map(g) == fa.map(g(f(_)))
- если fa равно None, то по определению метода map получим: None.map(f).map(g) == None.map(g) == None и None.map(g(f(_))) == None
- если fa равно Some(a), то по определению метода map получим: Some(a).map(f).map(g) == Some(f(a)).map(g) == Some(g(f(a))) и Some(a).map(g(f(_))) == Some(g(f(a)))

Последовательность

given listFunctor: Functor[List] with
  extension [A](as: List[A])
    override def map[B](f: A => B): List[B] = as match
      case Nil    => Nil
      case h :: t => f(h) :: t.map(f)

Either

given eitherFunctor[E]: Functor[[x] =>> Either[E, x]] with
  extension [A](fa: Either[E, A])
    override def map[B](f: A => B): Either[E, B] =
      fa match
        case Right(a) => Right(f(a))
        case Left(e)  => Left(e)

Writer - функциональный журнал

case class Writer[W, A](run: () => (W, A))

given writerFunctor[W]: Functor[[x] =>> Writer[W, x]] with
  extension [A](fa: Writer[W, A])
    override def map[B](f: A => B): Writer[W, B] =
      val (w, a) = fa.run()
      Writer[W, B](() => (w, f(a)))

State - функциональное состояние

case class State[S, +A](run: S => (S, A))

given stateFunctor[S]: Functor[[x] =>> State[S, x]] with
  extension [A](fa: State[S, A])
    override def map[B](f: A => B): State[S, B] =
      State[S, B] { s =>
        val (s1, a) = fa.run(s)
        (s1, f(a))
      }

IO

final case class IO[R](run: () => R)

given ioFunctor: Functor[IO] with
  extension [A](as: IO[A]) 
    override def map[B](f: A => B): IO[B] = IO { () => f(as.run()) }

Бинарное дерево

given Functor[BinaryTree] with
  extension [A](as: BinaryTree[A])
    override def map[B](f: A => B): BinaryTree[B] = as match
      case Leaf                   => Leaf
      case Branch(a, left, right) => Branch(f(a), left.map(f), right.map(f))

Композиция функторов

Композиция двух функторов - это функтор, для которого map

- есть композиция соответствующих map. Композиция функторов - категория, в которой объекты — это категории, а морфизмы — это функторы.

Рассмотрим пример:

final case class Nested[F[_], G[_], A](value: F[G[A]])

given nf[F[_]: Functor, G[_]: Functor]: Functor[[X] =>> Nested[F, G, X]] with
  extension [A](fga: Nested[F, G, A])
    override def map[B](f: A => B): Nested[F, G, B] =
      Nested[F, G, B](fga.value.map(_.map(f)))

Nested(Some(List(1, 2))).map(_ + 10)
// res0: Nested[[A >: Nothing <: Any] => Option[A], List, Int] = Nested(
//   value = Some(value = List(11, 12))
// )

Композиция функторов удовлетворяет функториальным законам:

сохраняет единичные морфизмы: map(fa)(identity) == fa
- fga.map(ga => ga.map(identity)) == fga.map(ga => ga) == fga.map(identity) == fga
сохраняет композицию: fa.map(f).map(g) == fa.map(g(f(_)))
- fga.map(ga => ga.map(f)).map(ga => ga.map(g)) == fga.map(ga => ga.map(f).map(g)) == fga.map(ga => ga.map(g(f(_))))

Реализация

Реализация в Cats

import cats.*
import cats.implicits.*

val list1 = List(1, 2, 3)
val list2 = Functor[List].map(list1)(_ * 2)  // List(2, 4, 6)

val func = (x: Int) => x + 1
val liftedFunc = Functor[Option].lift(func)
liftedFunc(Option(1))                        // Some(2)

Реализация в ScalaZ

import scalaz.*
import Scalaz.*

val len: String => Int = _.length
Functor[Option].map(Some("adsf"))(len)             // Some(4)
Functor[Option].map(None)(len)                     // None
Functor[List].map(List("qwer", "adsfg"))(len)      // List(4, 5)
// или через вызов метода на типе
List(1, 2, 3) map {_ + 1}                          // List(2, 3, 4)
List(1, 2, 3) ∘ {_ + 1}                            // List(2, 3, 4)

// В ScalaZ есть метод fpair, дублирующий значение в функторе 
List(1, 2, 3).fpair                                // List((1,1), (2,2), (3,3))

// Используя Functor можно «поднять» функцию для работы с типом Functor. Пример на Functor[Option]:
val lenOption: Option[String] => Option[Int] = Functor[Option].lift(len)
lenOption(Some("abcd"))                            // Some(4)
Functor[List].lift {(_: Int) * 2} (List(1, 2, 3))  // List(2, 4, 6)

// В ScalaZ есть методы strength, позволяющие "прокидывать" значение, создавая коллекцию tuple-ов
List(1,2,3).strengthL("a")                         // List("a" -> 1, "a" -> 2, "a" -> 3)
List(1,2,3).strengthR("a")                         // List(1 -> "a", 2 -> "a", 3 -> "a")

// Functor предоставляет функцию fproduct, которая сопоставляет значение с результатом применения функции к этому значению.
List("a", "aa", "b", "ccccc").fproduct(len)        // List((a,1), (aa,2), (b,1), (ccccc,5))

// Метод void «аннулирует» функтор, заменяя любой F[A] на F[Unit]
Functor[Option].void(Some(1))                      // Some(())

// Также в ScalaZ есть метод "принудительно" выставляющий заданное значение
List(1, 2, 3) >| "x"                               // List(x, x, x)
List(1, 2, 3) as "x"                               // List(x, x, x)

// Компоновка функторов
val listOpt = Functor[List] compose Functor[Option]
listOpt.map(List(Some(1), None, Some(3)))(_ + 1)   // List(Some(2), None, Some(4))

Ссылки:

Algebird
Category Theory for Programmers - Bartosz Milewski:
- Теория категорий для программистов
- Category Theory for Programmers, Functors
Cats
Functional Programming in Scala, Second Edition, Chapter 11
Herding Cats
Just what the funk is a Functor anyway?
Learn Functional Programming course/tutorial on Scala
Learning Scalaz
Scala with Cats
Scalaz API
SKB – Scala Functor
Tour of Scala
What the Functor? Functors in Scala - Rock the JVM

scalabook