Функторы

Представим список натуральных чисел и список строк. Типы элементов различаются, но устройство списка и операции над его структурой остаются общими. Обозначим тип элемента как $\mathtt{T}$: конструктор $\mathtt{List}$ принимает его и создаёт конкретный тип $\mathtt{List\;T}$. Поэтому род $\mathtt{List}$ — $\mathtt{* \to *}$.

Любитель C++ справедливо заметит, что шаблоны $\mathtt{std::vector}\langle \mathtt{T} \rangle$ и $\mathtt{std::list}\langle \mathtt{T} \rangle$ уже позволяют абстрагироваться от типа элемента, а итераторы и ranges — применять одни и те же алгоритмы к разным структурам, например к списку и дереву. Однако такие алгоритмы обобщаются по интерфейсу обхода готового объекта, а не по конструктору типа, сохраняющему форму контекста.

Haskell делает следующий шаг. И $\mathtt{List}$, и $\mathtt{Tree}$ имеют род $\mathtt{* \to *}$, поэтому класс типов $\mathtt{Functor}$ может абстрагироваться над самим конструктором $\mathtt{f}$. Операция $\mathtt{fmap}$ принимает функцию $\mathtt{a \to b}$, преобразует значения внутри $\mathtt{f\;a}$ и возвращает $\mathtt{f\;b}$, сохраняя форму контекста. Это полиморфизм не только по типу элемента, но и по конструктору контекста. В C++ его можно имитировать шаблонами и перегрузками, однако прямого стандартного аналога классов типов и единообразного полиморфизма высших родов в языке нет. Сам класс типов объявляется так:

class Functor f where
  fmap :: (a -> b) -> f a -> f b   -- применить функцию внутри контекста f

В этом объявлении $\mathtt{f}$ — переменная не конкретного типа, а конструктора типа рода $\mathtt{* \to *}$. Класс задаёт общую форму операции $\mathtt{fmap}$, а способ сохранения контекста определяет каждый экземпляр. Для списка и $\mathtt{Maybe}$ стандартные экземпляры устроены так:

instance Functor [] where
  fmap _ []       = []
  fmap g (x : xs) = g x : fmap g xs

instance Functor Maybe where
  fmap _ Nothing  = Nothing
  fmap g (Just x) = Just (g x)

Как видим, реализация $\mathtt{Functor}$ зависит от конструктора контекста, но не от конкретного типа его элементов. Теперь рассмотрим число 2 в некотором контексте. Начнём с ключевого понятия — значения в контексте:

Контекст позволяет один раз определить правила работы с особыми случаями и затем применять обычные функции, не размазывая проверки по алгоритму. Более мощные абстракции, построенные поверх этой идеи, позволяют связывать вычисления в цепочки и задавать стратегии их выполнения, но сам $\mathtt{Functor}$ гарантирует только преобразование через $\mathtt{fmap}$. Допустим, вычисление в JavaScript вернуло не значение, а $\mathtt{undefined}$. Тогда приходится писать $\mathtt{if}$; если передать результат дальше, проверки начинают расползаться по всему алгоритму. В Haskell отсутствие представляют явно с помощью $\mathtt{Maybe}$: экземпляр $\mathtt{Functor}$ оставляет $\mathtt{Nothing}$ без изменений, а к значению внутри $\mathtt{Just}$ применяет функцию. Точно так же отображение по пустому списку возвращает пустой список. К обычному значению функцию можно применить напрямую; значение в контексте сначала пришлось бы разбирать вручную. $\mathtt{fmap}$ берёт эту работу на себя:

fmap (+3) (Just 2)   -- Just 5
fmap (+3) Nothing    -- Nothing

У $\mathtt{fmap}$ есть инфиксный синоним: $g \mathbin{\mathtt{<\$>}} x$ $= \mathtt{fmap}\;g\;x$.

Экземпляры должны соблюдать два закона — тождество и композицию:

fmap id == id                     -- тождество
fmap (g . h) == fmap g . fmap h   -- композиция

Эти законы означают, что $\mathtt{fmap}$ меняет только значения, но не форму контекста: не перестраивает список и не превращает $\mathtt{Just}$ в $\mathtt{Nothing}$. Кроме того, последовательное отображение двух функций эквивалентно отображению их композиции.

Главные экземпляры:

-- Maybe — контекст «значение может отсутствовать»
fmap (+3) (Just 2)       -- Just 5

-- список — контекст «ноль или несколько значений»: fmap = map
fmap (+3) [1, 2, 3]      -- [4, 5, 6]

-- Either e — отображается только Right
fmap (+3) (Right 2)      -- Right 5
fmap (+3) (Left "oops")  -- Left "oops"

Функтор — отображение между категориями, сохраняющее $\mathtt{id}$ и композицию. В принятой для Haskell модели функторы являются эндофункторами категории типов и функций, а законы $\mathtt{fmap}$ в точности соответствуют аксиомам функтора.