пройдём по образу пути в категории F B. Так и так мы попадём в одно и то же место. Схематически это
можно изобразить так:
f
g
A
B
C
F
F
F
F A
F B
F C
F f
F g
Стрелки сверху находятся в категории A, а стрелки снизу находятся в категории B. Функтор F : A > A,
который переводит категорию A в себя называют эндофунктором (endofunctor). Функторы отображают одни
категории в другие сохраняя структуру первой категории. Мы словно говорим, что внутри второй категории
есть структура подобная первой. Интересно, что последовательное применение функторов, также является
функтором. Мы будем писать последовательное применение функторов F и G слитно, как F G. Также можно
определить и тождественный функтор, который ничего не делает с категорией, мы будем обозначать его как
IA или просто I, если категория на которой он определён понятна из контекста. Это говорит о том, что мы
можем построить категорию, в которой объектами будут другие категории, а стрелками будут функторы.
15.3 Естественное преобразование
В программировании часто приходится переводить данные из одной структуры в другую. Каждая из
структур хранит какие-то конкретные значения, но мы ничего с ними не делаем мы просто перекладываем
содержимое из одного ящика в другой. Например в нашем ящике только один отсек, но вдруг нам пришло
бесконечно много подарков, что поделать нам приходится сохранить первый попавшийся, отбросив осталь-
ные. Главное в этой аналогии это то, что мы ничего не меняем, а лишь перекладываем содержимое из одной
структуры в другую.
В Haskell это можно описать так:
onlyOne :: [a] -> Maybe a
onlyOne []
= Nothing
onlyOne (a:as)
= Just a
В этой функции мы перекладываем элементы из списка [a] в частично определённое значение Maybe.
Тоже самое происходит и в функции concat:
230 | Глава 15: Теория категорий
concat :: [[a]] -> [a]
Элементы перекладываются из списка списков в один список. В теории категорий этот процесс называ-
ется естественным преобразованием. Структуры определяются функторами. Поэтому в определении будет
участвовать два функтора. В функции onlyOne это были функторы [] и Maybe. При перекладывании элемен-
тов мы можем просто выбросить все элементы:
burnThemALl :: [a] -> ()
burnThemAll = const ()
Можно сказать, что единичный тип также определяет функтор. Это константный функтор, он переводит
любой тип в единственное значение (), а функцию в id:
data Empty a = Empty
instance Functor Empty where
fmap = const id
Тогда тип функции burnThemAll будет параметризован и слева и справа от стрелки:
burnThemAll :: [a] -> Empty a
burnThemAll = const Empty
Пусть даны две категории A и B и два функтора F, G : A > B. Преобразованием (transformation) в B из
F в G называют семейство стрелок ?:
?A : F A >B GA
для любого A из A
Рассмотрим преобразование onlyOne :: [a] -> Maybe a. Категории A и B в данном случае совпадают~–
это категория Hask. Функтор F – это список, а функтор G это Maybe. Преобразование onlyOne для каждого
объекта a из Hask определяет стрелку
onlyOne :: [a] -> Maybe a
Так мы получаем семейство стрелок, параметризованное объектом из Hask:
onlyOne :: [Int] -> Maybe Int
onlyOne :: [Char] -> Maybe Char
onlyOne :: [Int -> Int] -> Maybe (Int -> Int)
…
…
Теперь давайте определим, что значит перекладывать из одной структуры в другую, не меняя содержа-
ния. Представим, что функтор – это контейнер. Мы можем менять его содержание с помощью метода fmap.
Например мы можем прибавить единицу ко всем элементам списка xs с помощью выражения fmap (+1) xs.
Точно так же мы можем прибавить единицу к частично определённому значению. С точки зрения теории ка-
тегорий суть понятия “останется неизменным при перекладывании” заключается в том, что если мы возьмём
любую функцию к примеру прибавление единицы, то нам неважно когда её применять до функции onlyOne
или после. И в том и в другом случае мы получим одинаковый ответ. Давайте убедимся в этом:
onlyOne $ fmap (+1) [1,2,3,4,5]
=>
onlyOne [2,3,4,5,6]
=>
Just 2
fmap (+1) $ onlyOne [1,2,3,4,5]
=>
fmap (+1) $ Just 1
=>
Just 2
Результаты сошлись, обратите внимание на то, что функции fmap (+1) в двух вариантах являются раз-
ными функциями. Первая работает на списках, а вторая на частично определённых значениях. Суть в том,
что если при перекладывании значение не изменилось, то нам не важно когда выполнять преобразование
внутри функтора [] или внутри функтора Maybe. Теперь давайте выразим это на языке теории категорий.
Преобразование ? в категории B из функтора F в функтор G называют естественным (natural), если
F f ; ?B = ?A ; Gf
для любого f : A >A B
Естественное преобразование | 231
Это свойство можно изобразить графически:
?
F A
A
GA
F f
Gf
F B
GB
?B
По смыслу ясно, что если у нас есть три структуры данных (или три функтора), если мы просто пере-
ложили данные из первой во вторую, а затем переложили данные из второй в третью, ничего не меняя. То
итоговое преобразование, которое составлено из последовательного применения перекладывания данных
также не меняет данные. Это говорит о том, что композиция двух естественных преобразований также явля-
ется естественным преобразованием. Также мы можем составить тождественное преобразование, для двух
одинаковых функторов F : A > B, это будет семейство тождественных стрелок в категории B. Получает-
ся, что для двух категорий A и B мы можем составить категорию F tr( A, B), в которой объектами будут
функторы из A в B, а стрелками будут естественные преобразования. Поскольку естественные преобразова-
ния являются стрелками, которые соединяют функторы, мы будем обозначать их как обычные стрелки. Так
запись ? : F > G обозначает преобразование ?, которое переводит функтор F в функтор G.
Интересно, что изначально создатели теории категорий Саундедерс Маклейн и Сэмюэль Эйленберг при-
думали понятие естественного преобразования, а затем, чтобы дать ему обоснование было придумано поня-
тие функтора, и наконец для того чтобы дать обоснование функторам были придуманы категории. Катего-
рии содержат объекты и стрелки, для стрелок есть операция композиции. Также для каждого объекта есть
тождественная стрелка. Функторы являются стрелками в категории, в которой объектами являются другие
категории. А естественные преобразования являются стрелками в категории, в которой объектами являются
функторы. Получается такая иерархия структур.
15.4 Монады
Монадой называют эндофунктор T : A > A, для которого определены два естественных преобразования
? : I > T и µ : T T > T и выполнены два свойства:
• T ?A ; µA = idTA
• T µA ; µTA = µTTA ; µA
Преобразование ? – это функция return, а преобразование µ – это функция join. В теории категорий в
классе Monad другие методы. Перепишем эти свойства в виде функций Haskell:
join . fmap return
= id
join . fmap join
= join . join
Порядок следования аргументов изменился, потому что мы пользуемся обычной композицией (через
точку). Выражение T ?A означает применение функтора T к стрелке ?A. Ведь преобразование это семейство
стрелок, которые параметризованы объектами категории. На языке Haskell это означает применить fmap к
полиморфной функции (функции с параметром).
Также эти свойства можно изобразить графически:
