Язык мироздания — теория групп и теория категорий

Около полутора лет назад я опубликовал на Хабре статью под названием "Слово Божие — функциональное программирование как основа Вселенной", в которой я рассказывал про лямбда-исчисление и про то, как программу любой сложности можно свести к алгоритму на базе всего трёх SKI-комбинаторов или же одного единственного йота-комбинатора. В ней мы разобрались с алфавитом божественного языка, на котором написана книга мироздания. Теперь же пришло время разобраться с его грамматикой.

Красота абстракций

В посте "Эйлер, Чёрч и Мандельброт — этюд о красоте и математике" я упоминал, что лучшей математической мерой эстетической красоты служит колмогоровская сложность. Эта величина, названная в честь русского математика Андрея Николаевича Колмогорова, показывает то, как много символов некоего абстрактного языка программирования нужно, чтобы описать определенный математический объект.

К примеру, колмогоровская сложность строки 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf равна её длине, ведь самое короткое её описание - это она сама. А вот колмогоровская сложность строки abababababababababababababababababababababababababababababababab гораздо меньше, так как её можно описать простым "повтор ab 32 раза"

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

Самое невероятное свойство книги мироздания состоит в том, что она никем никогда не была написана, но читать её можно на множестве языков, и при каждом прочтении будут открываться новые смыслы. А самый поэтически складный и красивый из этих языков - это, без сомнения, язык математики. И самое по-колмогоровски красивые и сладкие уху его наречия - это теория групп и теория категорий, о которых мы сегодня и поговорим.

Увидеть Париж и умереть

Ранним утром 30 мая бурного 1832 года в пригороде Парижа выпущенная из дуэльного пистолета пуля оборвала жизнь двадцатилетнего юноши-республиканца. В тот день Франция потеряла одного из ярчайших гениев в своей истории и большого храбреца - последние слова умиравшего от смертельного ранения в живот дуэлянта были обращены к сидевшему у его больничной койки брату: "Только не плачь, Альфред! Мне нужно всё моё мужество, чтобы умереть в двадцать лет!". Так ушёл из жизни Эварист Галуа.

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

В ночь перед дуэлью Галуа отправил своему другу Огюсту Жану Батисту Шевалье все свои математические работы и письмо, в котором вкратце изложил их суть. В этих работах вечно молодой с тех пор математик заложил фундамент одной из самых основополагающих концепций современной математики - теории групп.

Теория групп - Полугруппа

Самая простая структура в теории групп - это полугруппа. Полугруппа - это некое множество, для которого задана ассоциативная бинарная операция, принимающая на вход два элемента этого множества и возвращающая третий. Здесь и далее все примеры будут приведены на языке программирования TypeScript.

interface Semigroup<T> {
  combine: (a: T, b: T) => T;
}

Примером полугруппы может служить множество натуральных чисел с операцией сложения:

const additionSemigroup: Semigroup<number> = { combine: (a, b) => a + b };

Множество натуральных чисел с операцией умножения:

const multiplicationSemigroup: Semigroup<number> = { combine: (a, b) => a * b };

Или множество строк с операцией конкатенации:

const concatenationSemigroup: Semigroup<string> = { combine: (a, b) => a + b };

Операция над элементами полугруппы обязательно должна обладать свойством ассоциативности. Давайте протестируем это с Jest:

const checkAssociativity = <T>(semigroup: Semigroup<T>, a: T, b: T, c: T) =>
  expect(semigroup.combine(semigroup.combine(a, b), c)).toEqual(
    semigroup.combine(a, semigroup.combine(b, c))
  );

checkAssociativity(additionSemigroup, 1, 2, 3);
checkAssociativity(multiplicationSemigroup, 1, 2, 3);
checkAssociativity(concatenationSemigroup, "a", "b", "c");

Каких-либо особо интересных свойств у полугруппы нет. Правда даже на их примере мы видим удобство теории групп - возможность работать с множествами и операциями над ними с помощью абстрактного интерфейса.

Например, мы можем написать функцию редукции массива значений полугруппы:

const reduceSemigroup = <T>(
  array: T[],
  semigroup: Semigroup<T>,
  initialValue: T
) => array.reduce((acc, value) => semigroup.combine(acc, value), initialValue);

Теперь мы можем использовать эту функцию для редукции массива:

const sum = reduceSemigroup([1, 2, 3, 4], additionSemigroup, 0);
expect(sum).toEqual(10);

const product = reduceSemigroup([1, 2, 3, 4], multiplicationSemigroup, 1);
expect(product).toEqual(24);

Использование функции редукции полугрупп плавно подводит нас к следующей, уже гораздо более интересной структуре из теории групп - моноиду.

Теория групп - Моноид

Моноид - это полугруппа с заданным нейтральным элементом.

interface Monoid<T> extends Semigroup<T> {
  unit: T;
}

Нейтральный элемент - это такой элемент, комбинирование с которым никак не меняет любой другой элемент. Для сложения натуральных чисел таким нейтральным элементом, конечно же, служит ноль, так как сложение любого числа с нулём даёт то же самое число.

const additionMonoid: Monoid<number> = {
  combine: (a, b) => a + b,
  unit: 0,
};

Проверим это свойство моноида с помощью Jest:

const checkUnitCombination = <T>(monoid: Monoid<T>, value: T) =>
  expect(monoid.combine(value, monoid.unit)).toEqual(value);

checkUnitCombination(additionMonoid, 10);

Нейтральным элементом моноида умножения натуральных чисел служит единица, так как любое число умноженное на единицу даёт то же самое число.

const multiplicationMonoid: Monoid<number> = {
  combine: (a, b) => a * b,
  unit: 1,
};

checkUnitCombination(multiplicationMonoid, 25);

Соответственно, нейтральным элементом моноида конкатенации строк служит пустая строка.

const concatenationMonoid: Monoid<string> = {
  combine: (a, b) => a + b,
  unit: "",
};

checkUnitCombination(concatenationMonoid, "a");

И теперь мы подходим к самому интересному свойству моноидов - для работы с ними можно использовать операцию свёртки - усовершенствованную версию функции reduceSemigroup из предыдущего раздела.

const fold = <T>(monoid: Monoid<T>, values: T[]): T =>
  values.reduce(monoid.combine, monoid.unit);

С помощью fold нам открываются совершенно волшебные способности:

const sum = fold(additionMonoid, [1, 2, 3, 4]);
expect(sum).toEqual(10);

const product = fold(multiplicationMonoid, [1, 2, 3, 4]);
expect(product).toEqual(24);

const concatenated = fold(concatString, ["a", "b", "c", "d"]);
expect(concatenated).toEqual("abcd");

Также мы можем определить моноиды для операций сравнения чисел.

const minMonoid: Monoid<number> = {
  combine: (a, b) => Math.min(a, b),
  unit: Infinity,
};

const maxMonoid: Monoid<number> = {
  combine: (a, b) => Math.max(a, b),
  unit: -Infinity,
};

const minFoldResult = fold(minMonoid, [1, 9, 6, 4]);
expect(minFoldResult).toEqual(1);

const maxFoldResult = fold(maxMonoid, [1, 9, 6, 4]);
expect(maxFoldResult).toEqual(9);

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

const functionMonoid: Monoid<(x: number) => number> = {
  combine: (f, g) => (x) => f(g(x)),
  unit: (x) => x,
};

const addOne = (x: number) => x + 1;
const double = (x: number) => x * 2;

// Обратите внимание, что первой выполняется операция double, а не addOne
const functionFoldResult = fold(functionMonoid, [addOne, double]);
expect(functionFoldResult(1)).toEqual(3);

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

Помните, в школе нам рассказывали, что любое число в нулевой степени равняется единице, но никогда не объясняли почему?

x^0=1

Это свойство становится очевидным при первом же взгляде на моноид умножения. Возведение в степень - это множественное умножение, например два в третьей степени - это умножение двойки на двойку и ещё раз на двойку, то есть два вызова функции combine у моноида умножения.

const twoInPowerThree = multiplicationMonoid.combine(
  multiplicationMonoid.combine(2, 2),
  2
);

Но что такое нулевая степень? Это полное отсутствие вызовов функции combine. Так какое же значение мы должны получить в результате такой операции? Без использования функции combine, нам остается лишь одно свойство моноида - нейтральный элемент unit, равный в случае умножения единице.

Теория групп - Группа

Группа - это моноид, для каждого элемента которого определен обратный элемент из этого же множества.

interface Group<T> extends Monoid<T> {
  inverse: (a: T) => T;
}

Классическим примером группы служит опять же множество целых чисел по операции сложения:

const additionGroup: Group<number> = {
  combine: (a, b) => a + b,
  unit: 0,
  inverse: (a) => -a,
};

Основное свойство группы состоит в том, что комбинирование элемента с его обратным элементом всегда дает в результате нейтральный элемент группы:

const checkInversionCombination = <T>(group: Group<T>, value: T) =>
  expect(group.combine(value, group.inverse(value))).toEqual(group.unit);

checkInversionCombination(additionGroup, 5);

Можно сказать, что группа - это математическая структура, которая абстрагирует понятие симметрии. Именно с помощью этой структуры физики изучают свойства пространства, времени, энергии и элементарных частиц - в основании математического аппарата теории относительности и квантовой механики лежит теория групп. С её помощью в 1918 году Эмми Нётер доказала свои знаменитые теоремы о том, что любой закон сохранения, будь то закон сохранения энергии, импульса или заряда, исходит из фундаментальных физических симметрий.

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

Монадология

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

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

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

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

Давайте рассмотрим базовые понятия теории категорий.

Теория категорий - Стрелка

Стрелкой (или морфизмом) в теории категорий называется связь между двумя категориями - соответствие каждого элемента первой категории какому-либо элементу второй. Возьмем к примеру две простейших категории - натуральные числа и строки из буквы "a".

0 - a
1 - aa
2 - aaa
3 - aaaa
4 - aaaaa
5 - aaaaaa
6 - aaaaaaa
7 - aaaaaaaa
...

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

const mapNumberToAString = (num: number) => "a".repeat(number) Необязательно, чтобы элементу из первой категории соответствовал уникальный элемент второй. Например, для следующей стрелки из категории натуральных чисел в категорию истинности во второй категории всего два элемента, но каждый элемент первой отображается в один из элементов второй:

0 - false
1 - false
2 - false
3 - true
4 - true
5 - true
...
n - true

Стрелочная функция в данном случае может быть описана функцией как:

const mapNumberToBoolean = (number: number) => number >= 3;

Теория категорий - Функтор и эндофунктор

Мы можем оборачивать элементы любой категории в некие абстрактные контейнеры. Если у нас есть категории A и B, и у нас есть некий контейнер F, который может содержать в себе один или несколько элементов категорий A или B, то мы получаем две новые категории F(A) и F(B).

Например, если у нас есть категория натуральных чисел и категория строк, и у нас есть некий контейнер, который может содержать их значения, например, массив, то мы получаем две новые категории - массив чисел и массив строк. В TypeScript эти связи отражаются в системе типов:

const number: number = 1;
const stringValue: string = "a";

const numbers: Array<number> = [1, 2, 3];
const strings: Array<string> = ["a", "b", "c"];

В теории категорий описываются отображения между категориями элементов и категориями контейнеров, которые при преобразовании сохраняют структуру. Такие отображения называют функторами. Само отображение при этом называют map от английского слова "map" - карта, ведь карта - это буквально отображение какой-то территории на листе бумаги.

Существует несколько разных типов функторов. Самый используемый из них - это эндофунтор, в котором преобразование происходит внутри одной и той же категории контейнера F(A) -> F(B).

interface Functor<A> {
  map: <B>(arrow: (element: A) => B) => Functor<B>;
}

const createFunctorMapping =
  <A, B>(arrow: (element: A) => B) =>
  (functor: Functor<A>) =>
    functor.map(arrow);

Классическим примером эндофунктора в TypeScript служит массив элементов. Например, возьмем стрелочную функцию из числа в истину/ложь из предыдущего параграфа и применим её к массиву чисел, то получим массив истин:

const mapNumberToBoolean = (number: number) => number >= 3;
const mapping = createFunctorMapping(mapNumberToBoolean);

const numbers: Array<number> = [1, 2, 3, 4];
const booleans: Array<boolean> = mapping(numbers); // [false, false, true, true]

Таким образом, если стрелочная функция A->B отображает категорию А в категорию B, то с помощью эндофунктора можно построить стрелочную функцию F(A)->F(B). Хотя в большинстве случаев мы просто напрямую передаваем стрелочную функцию внутрь map:

const numbers: Array<number> = [1, 2, 3, 4, 5];
const booleans: Array<boolean> = numbers.map((number) => number >= 3);

Для функторов должны соблюдаться несколько законов.

Первый закон - Закон идентичности:

const id = <T>(x: T): T => x;
const identityLaw = <A>(container: Functor<A>) =>
  expect(container.map(id)).equalTo(container);

Второй закон - Закон композиции

const compositionLaw = <A, B, C>(
  container: Functor<A>,
  f: (a: A) => B,
  g: (b: B) => C
) => expect(container.map((x) => g(f(x)))).equalTo(container.map(f).map(g));

Теория категорий - Монада

interface Monad<A> extends Functor<A> {
  flatMap: <B>(arrow: (element: A) => Monad<B>) => Monad<B>;
}

Кроме того, монаде нужен метод of, который оборачивает значение в монаду. Классическим примером монады в TypeScript служит всё тот же массив:

const numbers = Array.of(1, 2, 3);
const flatMappedNumbers = numbers.flatMap((number) => [number, number + 1]); // [ 1, 2, 2, 3, 3, 4 ]

Другими известными примерами TypeScript-монад могут служить Promise и Option, хотя все они как и Array сделаны в JavaScript не совсем правильно с математической точки зрения. А в более близких к чистому функциональному подходу языках и библиотеках есть ещё множество других монад. Ведь по сути, монада - это просто абстракция вычислений как таковых.

Для монад должны выполняться несколько специальных монадических законов, которые, однако, приводить здесь я не буду, так как пора завершать этот уже и без того длинный пост. Хочу лишь заметить, что самое главное преимущество монад состоит в том, что они позволяют упорядочивать исполнение изолированных вычислений. Примером такого упорядочивания в TypeScript может служить превращение Promise-монад в последовательность вызовов "await", вдохновленное "do"-синтаксисом языка Haskell.

Заключение

В заключение я хотел бы сказать, что теория групп и теория категорий лежат в основе всей известной человеку математики, информатики и физики. Это буквально язык мироздания - самый выразительный и самый поэтически прекрасный. Его бы я выучил только за то, что им разговаривал Бог!