Категория: сущность композиции

Я был ошеломлен положительной реакцией на мою предыдущую публикацию, Предисловие к теории категорий для программистов. И напуган, потому что я понял, насколько высокие ожидания у читателей. Думаю, вне зависимости от того, что я напишу, кто-то будет разочарован. Одни предпочтут более практичную книгу, другие - более теоретическую. Одни терпеть не могут C++ и хотят все примеры на Haskell. Другие терпеть не могут Haskell и требуют примеры на Java. И уверен, что темп изложения будет слишком медленным для одних и слишком быстрым для других. Я не напишу идеальную книгу - она будет полна компромиссов. И я лишь надеюсь, что смогу поделиться своими инсайтами с читателями. Начнем с азов.

Категория - это поразительно простое понятие. Категория состоит из объектов и стрелок между ними. Поэтому категории очень удобно представлять графически. Объект может быть нарисован как окружность или точка, а стрелка... стрелка - это всего лишь стрелка (для разнообразия, время от времени буду рисовать объекты в виде поросят, а стрелки - как фейерверки). Но основа категории - композиция. Или, если хотите, сущность композиции - категория. Стрелки компонуются, то есть, если есть стрелка от объекта A к объекту B, и еще одна стрелка от объекта B к объекту C, то должна быть еще одна стрелка (их композиция), направленная от A к C.

В категории, если есть стрелка от A к B и стрелка от B к C, то должна быть еще одна стрелка, соединяющая A и C напрямую. - их композиция. На этой диаграмме показана неполная категория, так как отсутствуют тождественные морфизмы (см. далее).

Стрелки как функции

Слишком много абстрактной бессмыслицы? Не отчаивайтесь. Поговорим о более приземленных вещах. Представьте стрелки (которые так же называют морфизмами) как функции. Пусть есть функция f аргумента типа A с возвращаемым значением типа B. Есть другая функция, g, аргумента типа B с возвращаемым значением типа C. Их можно скомпоновать, передав результат функции f функции g. Мы только что определили новую функцию аргумента типа A с возвращаемым значением типа C.

В математике такая композиция обозначается маленькой окружностью между функциями: $g \circ f$. Обратите внимание на порядок композиции - справа налево. Некоторых это сбивает с толку. Вы можете быть знакомы с синтаксисом конвейера в Unix:

lsof | grep Chrome

или шевроном >> из F#, которые направлены слева направо. Но в математике и в Haskell функции компонуются справа налево. Будет проще, если читать $g \circ f$ как "g после f".

Поясню еще нагляднее с помощью кода на C. У нас есть функция f аргумента типа A, которая возвращает значение типа B:

B f(A a);

и еще одна:

C g(B b);

Тогда их композиция:

C g_after_f(A a)
{
    return g(f(a));
}

Из этого примера снова видно направление композиции - справа налево; на этот раз в C.

Хотелось бы мне сказать, что есть шаблон в стандартной библиотеке C++, которые принимает на вход две функции и возвращает их композицию, но такого шаблона не существует. Так что попробуем немного Haskell, чтобы развеяться. Объявляем функцию от A к B:

f :: A -> B

Похожим образом нашу функцию g:

g :: B -> C

Их композиция:

g . f

Как только вы поймете, насколько удобен Haskell, невозможность выразить простейшие функциональные понятия в C++ будет слегка удручать. На самом деле, Haskell позволяет использовать символы Юникода, так что композицию можно записать так:

g ∘ f

Можно использовать даже двойные двоеточия и стрелки из Юникода:

f ∷ A → B

Вот и первый урок Haskell: двойное двоеточие означает "выражение типа...". Функция задается стрелкой между двумя типами. Композиция функций обозначается точкой между ними (либо кружком из Юникода).

Свойства композиции

Есть два крайне важных свойства, которыми должна обладать композиция в любой категории.

1. Композиция ассоциативна. Если есть три морфизма, f, g и h, которые могут быть скомпонованы (то есть, их объекты совместимы), то для их композиции не требуется скобок. Математически это выражается следующим образом:

$$h \circ (g \circ f) = (h \circ g) \circ f = h \circ g \circ f$$

На (псевдо) Haskell:

    f :: A -> B
    g :: B -> C
    h :: C -> D
    h . (g . f) == (h . g) . f == h . g . f

("Псевдо", потому что равенство не определено для функций.)

Ассоциативность довольно очевидна при работе с функциями, но может быть далеко не так очевидна в других категориях.

1. Для любого объекта A существует стрелка, являющаяся единицей композиции. Эта стрелка ведет от объекта обратно к нему же. Результатом компоновки единицы композиции с любой стрелкой, которая исходит от A или приходит к A, является та же самая стрелка. Единичная стрелка объекта A обозначается $id_A$ (тождество от A, от англ. identity - тождество).

   Математически, если стрелка f ведет от A к B, то

$$f \circ id_A = f$$

и

$$id_B \circ f = f$$

При рассмотрении функций тождественная стрелка - это тождественная функция, которая просто возвращает аргумент. Реализация одинакова для каждого типа, следовательно эта функция универсально полиморфна. В C++ мы могли бы представить ее в виде шаблона:

     template<class T> T id(T x) { return x; }

Разумеется, в C++ этим не обойтись, так как нужно учитывать не только что мы передаем, но еще и как (то есть, по значению, по ссылке, по const-ссылке, перемещением (move) и так далее).

В Haskell тождественная функция входит в стандартную библиотеку, которая называется Prelude. Вот объявление и определение функции:

    id :: a -> a
    id x = x

Как Вы можете заметить, полиморфные функции в Haskell - пара пустяков. В объявлении нужно просто заменить тип на переменную типа. Пояснение: названия конкретных типов всегда начинаются с прописной буквы, а названия переменных типа - со строчной. Так что в примере a может быть любым типом.

Определение функции в Haskell состоит из названия функции, после которого идут формальные параметры - в данном случае только один, x. Тело функции следует за знаком равенства. Такая краткость часто шокирует новичков, но Вы быстро поймете, что это абсолютно оправданно. Определение и вызов функций - это хлеб насущный в функциональном программировании, так что их синтаксис урезан до необходимого минимума. Отсутствуют не только скобки вокруг списка аргументов, но еще и запятые между отдельными аргументами (я покажу это позже, когда мы определим функцию нескольких аргументов).

Тело функции - всегда выражение: в функциях нет никаких операторов. Это же выражение и является результатом функции - в примере просто x.

На этом закончим наш второй урок по Haskell.

Условия тождества можно записать (опять-таки, на псевдо Haskell) в виде:

f . id == f
id . f == f

Можно задаться вопросом: "Зачем вообще нужна тождественная функция - функция, которая ничего не делает?" С другой стороны, зачем нужно число ноль? Ноль - символ ничего. У древних римлян была система счисления без нуля, и они могли строить замечательные дороги и акведуки, некоторые из которых дожили до наших дней.

Нейтральные значения, такие как ноль или id, чрезвычайно полезны при работе с символьными переменными. Поэтому римляне были были не так хороши в алгебре, как арабы и персы, которым понятие нуля было знакомо. Так что тождественная функция очень пригодится в качестве аргумента или возвращаемого значения для функций высшего порядка. Функции высшего порядка делают возможными символьные преобразования функций. На них построена алгебра функций.

Подводя итоги: категория состоит из объектов и стрелок (морфизмов). Стрелки могут быть скомпонованы, а композиция ассоциативна. У каждого объекта есть тождественная стрелка, которая служит в качестве единицы композиции.

Композиция - сущность программирования

Поклонники функционального программирования довольно своеобразно подходят к решению задач. Они начинают с практически буддистских вопросов. Например, при проектировании интерактивного приложения они бы спросили: "Что есть интерактивность?" При реализации игры Жизнь Джона Конвея они, наверное, размышляли бы о смысле жизни. Задам вопрос в том же ключе: "Что есть программирование?" На самом примитивном уровне программирование - это объяснение компьютеру, что нужно сделать. "Возьми содержимое памяти по адресу x и сложи с содержимым регистра EAX." Но даже при программировании на языке ассемблера инструкции, которые мы даем компьютеру, выражают нечто более осмысленное. Мы решаем нетривиальную задачу (будь она тривиальной, нам не потребовался бы компьютер). А как мы решаем задачи? Мы разбиваем крупные задачи на более мелкие. Если они все еще слишком крупные, мы разбиваем их на еще более мелкие составляющие, и так далее. Наконец, мы пишем код, который решает все маленькие задачи. А затем проявляется сущность программирования - мы собираем эти маленькие кусочки для решения более крупных задач. Декомпозиция бессмысленна, если нельзя снова собрать составляющие в единое целое.

Данный процесс иерархической декомпозиции и реконструкции не навязан нам компьютерами. Он отражает ограничения человеческого разума. Наш мозг может иметь дело лишь с небольшим количеством понятий единовременно. Одна из наиболее цитируемых статей в психологии, Магическое число семь плюс/минус два, установила, что мы можем удерживать в нашем разуме только 7 ± 2 "обрывков" информации. Детали нашего понимания человеческой кратковременной памяти могут измениться, но мы знаем наверняка, что она ограничена. Суть в том, что мы не способны воспринимать суп из объектов или спагетти-код. Нам нужна структура не потому, что хорошо структурированные программы отлично выглядят, а потому, что иначе наш мозг не способен эффективно их обрабатывать. Мы часто описываем код как элегантный или прекрасный, но на самом деле это означает, что он легко воспринимается нашим ограниченным человеческим разумом. Элегантный код подается небольшими порциями правильного размера, которые хорошо усваиваются нашей ментальной пищеварительной системой.

Так что собой представляют правильные "порции" для композиции программ? Площадь их поверхности должна увеличиваться медленнее их объема. (Мне нравится эта аналогия, так как за ней стоит интуитивное понимание, что площадь поверхности геометрического объекта растет как квадрат его размера - медленнее объема, который растет как куб.) Площадь поверхности - это информация, требуемая для композиции отдельных частей. Объем - информация, которая нужна для их реализации. Идея такова: после реализации отдельной "порции" мы можем забыть о подробностях ее реализации и сконцентрироваться на ее взаимодействии с прочими "порциями". В объектно-ориентированном программировании площадью является объявление класса объекта, или его абстрактный интерфейс. В функциональном программировании площадь - объявление функции. (Я немного упрощаю действительное положение вещей, но суть ясна.)

Теория категорий доходит до крайности в этом смысле, так как она постоянно отбивает охоту копаться во внутренностях объектов. Объект в понятии теории категорий - абстрактная и неясная сущность. Все, что мы можем о нем узнать, - как он связан с другими объектами посредством стрелок. Поисковые системы интернета ранжируют веб-сайты подобным образом - путем анализа входящих и исходящих ссылок (за исключением случаев, когда они мошенничают). В объектно-ориентированном программировании идеальный объект доступен только через его абстрактный интерфейс (только площадь, без объема), а методы играют роль стрелок. Как только возникает необходимость вникать в реализацию объекта, чтобы понять, как скомпоновать его с другими объектами, парадигма программирования лишается своих преимуществ.

Упражнения

1. Как можно лучше реализуйте тождественную функцию на самом любимом Вами языке программирования (или на втором любимом языке, если первый - Haskell).

2. Реализуйте композиционную функцию на предпочитаемом Вами языке. Функция принимает две других функции в качестве аргументов и возвращает функцию, являющуюся их композицией.

3. Напишите программу, которая проверяет, что Ваша композиционная функция соблюдает условие тождества.

4. Является ли Всемирная паутина категорией в каком-либо смысле? Являются ли ссылки морфизмами?

5. Является ли Facebook категорией, где люди - это объекты с морфизмом "находится в друзьях"?

6. Когда ориентированный граф является категорией?

Ценные комментарии

mikefhay

Понравилась статья, и я жду следующих. Хотя я совершенно запутался с последними тремя упражнениями.

Bartosz Milewski

@mikefhay: Эти упражнения лишь пища для размышлений. На них нет правильного или неправильного ответа. Попробуйте задать условия и посмотрите, удовлетворяют ли они определению категории. Если необходимо, измените свои определения. Поэкспериментируйте с разными идеями.

humbleoh

Доктор Бартош,

спасибо за хорошее изложение, но Ваши объяснения и примеры используют функции одной переменной. Не могли бы Вы дать более обобщенное объяснение композиции функций нескольких переменных? Например, пусть заданы функции $f(x), h(x), g(x_1, x_2)$, а нам нужно получить их композицию:

$w(x) = g(f(x), h(x))$.

Как описать их в виде графа, и какой синтаксис "подойдет" для описания их в каком-нибудь функциональном языке?

Bartosz Milewski

@humbleoh: Я расскажу о функциях нескольких аргументов позже. Краткое объяснение: нужно представить функцию нескольких аргументов как функцию первого аргумента, которая возвращает новую функцию от второго аргумента. Это называется каррирование.

В Haskell можно просто написать f x y, а потом вызвать функцию с одним аргументом, к примеру, f 41, и получить функцию, которая ожидает еще один аргумент. Полученную функцию можно немедленно вызвать, f 41 28, чтобы получить конечный результат. Можно поставить скобки вокруг первого вызова, (f 41) 28, но это необязательно. Суть в том, что это выглядит и рассчитывается как функция двух аргументов, но при этом еще позволяет определять функции с неполным набором аргументов, такие как g = f 41.

idg10

... Существует ли отличие между графом, отображающим рефлексивное транзитивное отношение, и графом, отображающим категорию? (Можно ли нарисовать диаграмму, которая представляет одно из этих понятий, но в то же время не является иллюстрацией другого?)

Bartosz Milewski

@idg10: Я привел пример категории всех множеств и функций между ними. Граф определен как множество вершин и ребер: ключевое слово - "множество". Не существует множества всех множеств (такое множество должно включать самое себя, что приводит к парадоксу). Но категория всех множеств существует. Так что здесь мы рассматриваем бОльшие бесконечности.

idg10

А-а! Я не думал о бесконечных множествах - теперь я понял. Спасибо за терпеливые объяснения!

Zheka Kozlov

Бартош, Вы сказали, что тождественный морфизм - это морфизм от объекта к нему же. Означает ли это, что любая функция типа Int -> Int является тождественным морфизмом?

Bartosz Milewski

Думаю, стоит подчеркнуть, что может существовать много морфизмов между двумя объектами, и много морфизмов от объекта к нему самому. Пример моноида в следующих статьях это покажет.

Mark

... Вопрос следующий. Вы сказали: "Категория - это поразительно простое понятие. Категория состоит из объектов и стрелок между ними."

Не могли бы Вы пояснить, почему было выбрано именно слово "категория"? В моем ограниченном мозге "категория" означает группу. К примеру, если Вы хотите собрать данные о людях, Вы можете использовать категории "возраст", "пол" и так далее. ...

Bartosz Milewski

Мое понимание следующее - категория описывает целую категорию (класс) систем или теорий, которые имеют общую структуру.

karkunow

Здравствуйте! Перечитываю эту статью и ответ на вопрос о необходимости тождественных морфизмов кажется мне неудовлетворительным. Думаю, было бы интересно включить объяснения, указанные на Quora профессором Baez и мистером Zhang.

Кратко: тождественные морфизмы нужны для вывода более полезного понятия изоморфизма в категории. И, конечно, для определения изоморфизма. ...

Bartosz Milewski

@karkunow: Я только объяснил, почему тождественная функция - полезное понятие в программировании. Заметьте, что ответы на Quora, которые рассматривают более общий вопрос тождественных морфизмов в произвольной категории, более продвинутые по сравнению с материалом вводной секции моей книги. Они говорят о важности изоморфизмов и о лемме Йонеды (я еще не ввел понятие изоморфизма на этом этапе, и лемма Йонеды будет гораздо позже).

Я думаю, что основная причина включения тождественных морфизмов в определение категории заключается в том, что без них теория не была бы достаточно богата, чтобы быть интересной. Определение должно быть настолько простым, насколько это возможно, но не проще. Очень прагматичное решение.

Alex Vong

Отличная статья! Попробую ответить на вопросы.

Учитывая, что морфизмы по определению должны быть компонуемы и в категории должно быть определено тождество, я считаю, что Всемирная паутина является категорией, если мы представим "возможность доступа к странице" в качестве стрелки. Чтобы получить доступ к той же странице, Вы не проходите по какой-либо ссылке, и Вы на той же странице, - тождественная стрелка. Предположим, что есть ссылки от A к B и ссылки от B к C. Тогда очевидно, что мы можем перейти от A к C.

С другой стороны, FB не является категорией, если мы представим "быть другом ..." в качестве стрелки, поскольку мне не нужно быть своим другом - тождественная стрелка отсутствует.

Bartosz Milewski

@Alex: Обратите внимание, что все зависит от определения морфизма. В случае со Всемирной паутиной Вы определили морфизм как "возможность доступа к странице". В случае с Facebook у Вас есть определенная свобода в том, как именно определить, что значит "быть другом ...", - например, это может означать возможность просмотра личных данных. При таком подходе Вы являетесь своим другом. Однако в этом случае нарушается правило композиции. Друг моего друга необязательно является моим другом. С другой стороны, если задать морфизм как "возможность зайти на чью-либо страницу через своих друзей, их друзей и так далее", в итоге окажется, что почти все в интернете являются Вашими друзьями. Таким образом, Кевин Бейкон - Ваш друг. Правда, это все не распространяется на клики без внешних друзей.

Подобные размышления совершенствуют креативность.

joco42

"Площадь поверхности - это информация, требуемая для композиции отдельных частей. Объем - информация, которая нужна для их реализации. Идея такова: после реализации отдельной "порции" мы можем забыть о подробностях ее реализации и сконцентрироваться на ее взаимодействии с прочими "порциями"."

Что есть информация? В каком смысле? Энтропия Колмогорова? Биты?

Возьмем функции, к примеру: поверхность = что она должна делать ? объем = что она делает (на уровне компьютера / реализации), чтобы сделать то, что она должна сделать?

Информация и там, и там одинаковая, только описана разными языками. Человеческим языком (поверхность) либо языком программирования (объем).

Так что лучшая аналогия была бы : площадь=понятное человеку описание, объем=понятное компьютеру описание - именно то, что ИИ в наши дни делает ближе друг к другу. Как информация (=алгоритмы/правила) представлены.

Bartosz Milewski

Поверхность - это интерфейс. Все, что необходимо знать, чтобы применять объект. К сожалению, в языках со слабой типизацией (скорее всего, имелась в виду динамическая типизация - прим. пер.) интерфейс не предоставляет Вам много информации, так что приходится больше полагаться на документацию или, в худшем случае, приходится изучать реализацию.

Roni

Начинаю думать, что я слишком глуп, чтобы понять что-либо за пределами детсадовской математики. К примеру, я просто не способен понять следующее:

"Для любого объекта A существует стрелка, являющаяся единицей композиции. Эта стрелка ведет от объекта обратно к нему же. Результатом компоновки единицы композиции с любой стрелкой, которая исходит от A или приходит к A, является та же самая стрелка. Единичная стрелка объекта A обозначается $id_A$ (тождество от A, от англ. identity - тождество)."

Bartosz Milewski

Должен признаться, что я понимаю выражения, подобные этому, только благодаря тому, что я видел их графическое представление. Вам нужен карандаш и лист бумаги - для визуализации.