Функторы
Хотелось бы поговорить немного о функторах и о том как их понимать и зачем они вообще нужны.
План такой — сначала немного теории, а потом напишем свой собственный функтор.
Чтобы понять что это и с чем едят нужно сделать несколько шагов назад и начать с определения ‘категории’.
Категории очень простые — это воображаемая вселенная в которой живут объекты и стрелки между ними, при этом стрелки могут сочетаться между собой, а все объекты имеют идентичность (identity, стрелку из себя в себя самого). Самое интересное что объекты могут быть чем угодно а стрелки обозначать какие угодно отношения между ними — именно поэтому они и называются стрелками а не функциями. Объекты в категории могут быть подобраны любым способом — чаще всего это они обладают некоторыми сходными свойствами, такими что между ними могут существовать некие отношения (стрелки).
Например:
Есть группа людей разного возраста. Эти люди — объекты категории. Между ними можно установить порядок ‘старше — младше’ и обозначить его стрелками. Полчится следующее:
A:
a -f-> b -g-> c
где A — категория
a, b, c — люди (объекты этой категории)
f, g — стрелки, обозначающие что один человек младше другого.
Интересно что достаточно одного взгляда чтобы понять что ‘a’ младше ‘c’.
Это и есть композиция стрелок и обозначается она как g . f
Читается как ‘g после f’.
Понятие категории о том как сочетать объекты — о их композиции.
Теперь вернемся на землю программирования. Для дальнейшего понимания лучше прочитать:
https://medium.com/@gubinrobert/%D1%82%D0%B8%D0%BF%D1%8B-%D0%BA%D0%B0%D0%BA-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8-25b7cd47aa92
По сути в scala есть только одна категория — категория типов, её объекты — это типы, а стрелки — функции между этими типами. Соответственно если взять предыдущий пример то выходит что
A:
a -f-> b -g-> c
A — категория
a, b, c — некоторые типы
f, g — функции этих типов
Получается что тип функции f :: a -> b, а функции g :: b -> c
или если в контексте scala:
def f(a: A): B
def g(b: B): C
Теперь к определению функтора.
Функтор — это отображение между категориями. Как мы теперь знаем категория состоит из объектов, их идентичности и стрелок между ними, выходит что функтор должен отображать это всё, причем таким образом чтобы сохранить структуру, то есть все стрелки.
Получаются следующие правила:
F(id a) == id F a — сохранение идентичности
F(g . f) == (F g) . (F f) — сохранение композиции
Но у нас одна категория — категория типов. Получается в программировании функтор может отображать только из категории типов в категорию типов? Да, в большинстве случаев это так. Собственно выходит что мы имеем не функтор, а эндофунктор, то есть функтор из категории в себя саму.
Если подходить со стороны ежедневного программирования на scala то функтор это вроде как контейнерный тип с опрерацией map. Например Option[Int]. Я предлагаю подойти к функтору немного с другой стороны. Со стороны стрелок а не объектов.
Как говорилось выше — функтор должен отображать стрелки, соответственно спаведливо будет иметь некоторую функцию, которая из
a -> b
сделает
F a -> F b
Назовем эту функцию lift. Мы как-бы поднимаем стрелку из одной категории в другую. Если нам удастся реализовать эту функцию то map мы получим совершенно бесплатно, ведь map это способ применить функцию к объекту находящемуся в другой категории. Соответственно map можно выразить в терминах lift как lift (f)(F).
Забегая вперед хочу сказать что и lift легко выражается в терминах map. Об этом ниже.
Подчеркну плюс определения функтора через lift. Становится очевидным что контейнерные типы сами по себе являются просто объектами во всё той-же категории типов, а не функторами.
Итак, определим что же будет являться функтором.
Из этого определения должно стать понятно как map выражается в терминах lift.
Так же мы видим что функтор это тип высшего порядка, соответственно имеет следующий вид:
(* -> *) -> *
Из этой нотации видно что функтор это абстракция отображения типов, а операция lift служит для отображения стрелок.
Теперь реализуем этот функтор для следующего алгебраического типа:
Как видно из названия — это будет наш самописный аналог Option из scala.
Перейдём к реализации:
Проверим что он следует функторным законам:
Второе правило для себя я читаю следующим образом — неважно отобразить функции по очереди а затем сделать композицию, или сделать композицию а затем отобразить.
Как видно сам по себе тип Maybe не является функтором, потому как делает лишь часть работы — а именно отображает один тип в другой. Функтор же отображает еще и стрелки и при этом сохраняет их композицию.
Ну и на последок реализация функтора через map:
Итог: функторы не контейнеры. Контейнеры лишь отчасти похожи на них потому как создаются благодаря конструктору типа, который является единственным способом отображения из одного типа в другой.
Ресурсы:
https://www.youtube.com/watch?v=FyoQjkwsy7o&index=11&list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_