Функторы

Robert Gubin
Jul 22, 2017 · 4 min read

Хотелось бы поговорить немного о функторах и о том как их понимать и зачем они вообще нужны.
План такой — сначала немного теории, а потом напишем свой собственный функтор.
Чтобы понять что это и с чем едят нужно сделать несколько шагов назад и начать с определения ‘категории’.
Категории очень простые — это воображаемая вселенная в которой живут объекты и стрелки между ними, при этом стрелки могут сочетаться между собой, а все объекты имеют идентичность (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_

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade