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

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


В категории, если есть стрелка от А к В и стрелка от В к С, то есть должна быть стрелка от А до С, которая называется их композицией. Эта схема — не полное определение категории потому, что не хватает тождественных морфизмов (см ниже).

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

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

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

lsof | grep Chrome

или композицией >> в F#, и те и другие идут слева-направо. Но в математике и в функциях Haskell композиция направлена справа-налево. Это помогает, если вы читаете g∘f как «g после f.»

Давайте покажем это еще более явно кодом на Си. У нас есть одна функция f, которая принимает аргумент типа A и возвращает значение типа B:

B f(A a);

и другая:

C g(B b);

Их комбинацией будет:

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

Тут вы снова видите композицию справа-налево: g(f(a));, теперь и в Си.
Я хотел бы сказать вам, что есть шаблон в стандартной библиотеке С++, который принимает две функции и возвращает их композицию, но такого нет.
Примечание переводчика: но такой не сложно написать на С++14 (я опускаю тонны деталей владения и шаблонной магии для проверок, что эти функции и тип аргумента действительно можно компоновать):

template <typename T>
struct function_arg: public function_arg<decltype(&T::operator())> {};

template<typename ReturnType, typename Arg>
struct function_arg<ReturnType(Arg) const> {
	using type = Arg;
};

template<typename ClassType, typename ReturnType, typename Arg>
struct function_arg<ReturnType(ClassType::*)(Arg) const> {
	using type = Arg;
};

template<typename T>
using function_arg_t = typename function_arg<T>::type;

template<typename F, typename G>
auto compose(F&& f, G&& g) {
	return [f = std::forward<F>(f), g = std::forward<G>(g)]
		(function_arg_t<F>&& a) {return g(f(std::forward<function_arg_t<F>>(a)));};
}

Так что, давайте для разнообразия попробуем немного Haskell. Вот объявление функции от А к В:

f :: A -> B

По аналогии:

g :: B -> C

Их композицией будет:

g . f

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

g ∘ f

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

f ∷ A → B

Вот и первый Haskell урок: двойное двоеточие означает «имеет тип ...» Тип функции создается путем написания стрелки между двумя типами. Композиция двух функций записывается точкой между ники (или кругом из Unicode).

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

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

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

h∘(g∘f) = (h∘g)∘f = h∘g∘f

В (псевдо) Haskell:

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

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

2. Для каждого объекта A есть стрелка, которая будет единицей композиции. Эта стрелка от объекта к самому себе. Быть единицей композиции — означает, что при композиции единицы с любой стрелкой, которая либо начинается на A или заканчивается на A соответственно, композиция возвращает ту же стрелку. Единичная стрелка объекта А называется idA (единица на А). В математической нотации, если f идет от A до B, то

f∘idA = f

и

idB∘f = f

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

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

Примечание переводчика: по-хорошему, тождественную функцию стоит определить так:

template<class T> auto id(T&& x) { return std::forward<T>(x); }

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

В Haskell, тождественная функция — часть стандартной библиотеки (называемой Prelude). Вот ее объявление и определение:

id :: a -> a
id x = x

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

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

Тело функции всегда выражение — нет никаких стэйтментов. Результат функции это выражение — здесь, просто x.

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

Условия на композицию с единичной стрелкой могут быть записаны (опять же, на псевдо-Haskell), так:

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

Вы можете задавать себе вопрос: зачем кому-то возиться с тождественной функцей — функцией, которая ничего не делает? Опять же, почему мы возимся с числом ноль? Ноль — символ пустоты. Древние римляне не имели нуля в системе исчисления, и они строили отличные дороги и акведуки, некоторые из которых сохранились и по сей день.

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

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

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

Функциональные программисты имеют своеобразный способ подхода к проблемам. Они начинают с задания очень Дзен-подобных вопросов. Например, при проектировании интерактивной программы, они спросят: что такое интерактивность? При реализации игры Жизнь, они, вероятно, задумаются о смысле жизни. На этой волне я собираюсь спросить: что такое программирование? На самом базовом уровне, программирование — говорить компьютеру, что ему делать. «Возьмите содержимое памяти по адресу x и добавьте его к содержимому регистра EAX.» Но, даже когда мы программируем на ассемблере, инструкции, которые мы даем компьютеру — выражение чего-то более важного. Мы решаем нетривиальную задачу (если бы она была тривиальной, мы не нуждались бы в помощи компьютера). И как мы решаем задачи? Раскладываем большие задачи на более мелкие. Если мелкие все еще слишком большие, то их тоже раскладываем, и так далее. Наконец, мы пишем код, который решает все мелкие задачи. И вот тут проявляется суть программирования: мы составляем эти куски кода для создания решений более серьезных задач. Разложение не имело бы смысла, если мы не смогли сложить кусочки вместе.

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

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

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

Продолжение следует.

Теория категорий для программистов: предисловие

P.S. Кстати, не могу оставить без внимания, что Бартош будет выступать в феврале на конференции в Москве, как раз по этой теме: теория категорий для программистов.

Автор: Monnoroch

Источник