Теорія категорій на JavaScript. Частина 1. Категорія множин



Абстракція – це одна із основних технік у ІТ. Будь-яка мова програмування або моделювання, будь-яка парадигма програмування (процедурне, функціональна, ООП, ...) дають відповідь на питання, як і від чого потрібно абстрагуватися. Причому, адепти кожного підходу пропонують якийсь свій варіант абстракції.

Якщо ви хочете побачити дійсну, універсальну абстракцію, вступайте в нашу... вивчайте теорію категорій. У статті на прикладі категорії множин з картинками і JavaScript-кодом пояснюються основні поняття теорії категорій: межі, універсальне властивість. Розглядається обчислювальний аспект теорії категорій.

Також трохи йдеться про класи, домішки та суміші в JavaScript.

Приклади зі статті можна переглянути тут.

Введення

Я думаю, що всі чули про теорію категорій. Чули, що це крута silver-bullet теорія, за допомогою якої можна послідовно описувати дуже різні речі. Чули, що вона активно застосовується в функціональних мовах програмування. Хтось можливо навіть чув про мовах програмування або системах комп'ютерної алгебри, в значній мірі базуються на теорії категорій.

В Інтернеті багато книг і статей на цю тему. Але зазвичай вони орієнтовані або на математиків, або на ИТшников, що займаються наукою і дивними речами типу Haskell, ML (іронія – не треба мені ставити мінус в карму, як це зазвичай буває після згадки святого Haskell всує).

А для простих роботяг, які кожен день заробляють собі на шматок хліба фигаченьем на JavaScript, користь від теорії категорій мало зрозуміла. Я не обіцяю, що після прочитання цього циклу статей вона стане зрозуміліше. Але якщо все вийде, то можливо ми навіть запилим додаток, що буде робити щось корисне.

Відразу попереджаю, що у мене інженерне, а не математична освіта. Тому якщо ви очікуєте побачити у статті строгі визначення, докази теорем і т. п., то не побачите. Швидше навпаки, все буде описуватися «на пальцях». Якщо ви побачите якісь неточності, будь ласка, пишіть, я можу в чомусь помилятися.

Що таке категорія?

Категорія – це все що завгодно, для чого визначені:

  • клас об'єктів,
  • клас морфізмів (стрілок) між об'єктами (причому, для кожного об'єкта існує тотожний морфизм),
  • операція композиції морфізмів,
    • яка є асоціативною:
      (h ∘ g) ∘ f = h ∘ (g ∘ f)
    • для якої тотожні морфизмы є нейтральними елементами:
      f ∘ idA = idB ∘ f = f
Символ ∘ іноді опускають: (h g) f = h (g f)

Також замість композиції іноді використовують конкатенацию морфізмів, щоб у формулі вони йшли в тому ж порядку, що і на діаграмі: (f ; g) ; h = f ; (g ; h) Але такий запис не так зручна як здається, тому рідко зустрічається. Якщо ми будемо розглядати елементи в наступних статтях, то ви в цьому переконаєтеся.

Щоб сконструювати категорію чогось, необхідно

  • придумати які в цій категорії будуть об'єкти і морфизмы,
  • не забути про тотожні морфизмы,
  • придумати, що являє собою операція композиції морфізмів,
  • довести, що композиція володіє необхідними властивостями,
  • ...
  • profit.
Морфизмы повинні мати в точності один вихідний і цільовий об'єкт. Вони не можуть поєднувати 3 або більше об'єктів, не можуть «висіти в повітрі». Категорії вищих порядків ми не розглядаємо.)

Застосовувати операцію композиції можна тільки сумісними морфизмам. Нехай є морфизмы f : A → B, g : B → C і h : З → D. Композиція g ∘ f (або f; g) допустима. А такі композиції неприпустимі: h ∘ f, f ∘ f, f ∘ g.

Тепер розглянемо приклад категорії. Уявіть елементарний топос, він є категорією. Якщо представили, то навряд чи ви знайдете в цій статті для себе щось нове. Краще почитати що-небудь більш фундаментальне.

Приклад вільної категорії

Якщо все-таки продовжуєте читати, то спробуємо сконструювати більш зрозумілу категорію. Уявіть вашу сторінку вконтакте, а також сторінки, ваших друзів, передплатників і тих, на кого ви підписані – усіх, з ким ви безпосередньо пов'язані. Це буде клас об'єктів:


Для всіх, на кого ви підписані, намалюйте стрілку від вашої сторінки до сторінки цієї людини. Для всіх, хто підписаний на вас, намалюйте стрілку від їх сторінок до вашої. А для всіх ваших друзів намалюйте стрілки в обох напрямках:


Тепер зробіть те ж саме для інших сторінок:


Будемо вважати, що якщо одна людина підписаний на іншого, то 1-ий знає 2-го. Якщо дві людини підписані один на одного (друзі), то вони знають один одного. Тобто морфизм в нашій категорії – це відношення «знає».

Будемо вважати, що все знають самі себе і намалюємо тотожні морфизмы:


Визначимо операцію композиції морфізмів наступним чином.

Нехай f – це морфизм, що позначає, що A знає B, а g – це морфизм, що позначає, що B знає C. Тоді g ∘ f – це морфизм, який означає, що A опосередковано знає C.

Таким чином, клас морфізмів у нашій категорії включає в себе не тільки відношення «знає», але і «опосередковано знає».

Асоціативність операції композиції очевидна. Якщо А знає B, який знає C, який знає D, то як не группируй тут морфизмы, все одно A опосередковано знає D.

Те, що тотожні морфизмы є нейтральними елементами композиції теж очевидно. Якщо A знає B, то те, що вони знають самі себе, нічого не змінює.

Ми побудували вільну категорії. З одного боку, цей приклад показує, як з чого завгодно можна побудувати категорію. З іншого боку, показує, що категорії будуються за певними правилами.

Приклад предпорядка

У попередньому прикладі об'єкти і морфизмы відносно прості, ми вважаємо, що у них відсутня внутрішня структура.

Тепер уявіть, що всі сторінки (ваша і людей, з якими ви пов'язані) – це один об'єкт. Безліч сторінок, що мають відношення до іншої людини – це інший об'єкт і так далі:


Які морфизмы можуть бути у такої категорії?

Наприклад, відношення «підмножина». Якщо кожен друг, передплатник і т. п. A людини є також одним передплатником і т. п. людини B, то малюємо морфизм від A до B. У цьому випадку ми отримаємо предпорядок, який є категорією:


Або, наприклад, в якості морфізмів можемо використовувати функції, які в якості аргументів приймають сторінки і повертають для них деякі інші сторінки. В цьому випадку ми отримаємо категорії множин. Точніше, її підкатегорію, тому що категорія множин містить всі множини, а не тільки безлічі сторінок вконтакте.

Коммутативные діаграми

У розглянутих прикладах я ототожнював діаграми з категоріями. Але, взагалі, це різні речі. Строго кажучи, діаграма – це функтор. Що таке функтор нам поки неважливо.

В одній з попередніх статей ми вже відзначали, що модель і її уявлення в деякій нотації (діаграма, текстове представлення або ще якийсь) – це різні речі. Аналогічно з категоріями.

Поки будемо вважати, що діаграма – це певне візуальне представлення фрагмента категорії, в якому об'єкти зображуються в вигляді вузлів, а морфизмы – у вигляді стрілочок між вузлами. Втім, на діаграмі іноді можна зобразити всю категорію цілком, а не тільки її фрагмент. Бувають категорії, що містять всього один або декілька об'єктів і морфізмів.

Діаграми можуть бути комутативними або некомутативними.

Коммутативная діаграма – це діаграма, на якій для будь-якої пари об'єктів результат композиції морфізмів не залежить від вибору спрямованого шляху між цими об'єктами.

Особисто я не відразу зрозумів, як діаграма може бути некоммутативной. Подивіться на приклади вільної категорії і предпорядка вище. Якщо між двома об'єктами є кілька шляхів, то очевидно, що всі ці шляхи еквівалентні – вони починаються одним об'єктом і закінчуються одним об'єктом. Як ці шляхи можуть бути нееквівалентними?

Справа в тому, що в даних категоріях від деякого об'єкта A до деякого об'єкту B може йти максимум один морфизм. А, наприклад, в категорії множин між однією і тією ж парою об'єктів може бути кілька абсолютно різних морфізмів. Розглянемо в якості прикладу дуже просту діаграму з двома об'єктами і двома паралельними морфизмами. Коммутативна вона?


Вона буде коммутативна тоді і тільки тоді, коли виконується рівність f = g. Взагалі, в теорії категорій коммутативные діаграми часто використовуються як альтернатива запису систем рівнянь. Можна написати «наступні рівності виконуються» і перерахувати їх. А можна написати «наступна діаграма коммутативна» і намалювати діаграму, відповідну систему рівнянь.

Комутативність даної діаграми залежить від того які множини та функції стоять за намальованими об'єктами і морфизмами. Нехай об'єкт A – це множина чисел, об'єкт B – це безліч геометричних фігур, морфизм f – функція, яка для деякого числа повертає коло з радіусом рівним цього числа, морфизм g – це функція, яка для деякого числа повертає квадрат з довжиною сторони дорівнює цьому числу. Очевидно, що ці дві функції не рівні, а, отже, діаграма некоммутативна:


Нехай вас не бентежить, що в одній категорії змішуються безлічі чисел і безлічі фігур. До цієї ж категорії можуть бути безлічі сторінок вконтакте, безлічі множин, графів, котиків і чого завгодно – все це одна категорія множин. Розглянемо її більш детально, але спочатку трохи загальних відомостей про вихідному коді.

Загальна інформація по вихідного коду

Вихідні коди доступні тут, а приклади зі статті тут.

Відразу попереджаю, що більшу частину коду я писав 3 роки тому, коли ще не було ES6, і в стандартній бібліотеці не було нормальних колекцій. Мені довелося тоді реалізувати свій Set. І, в цілому, код напевно організований не дуже оптимально. Я, чесно, намагався розкласти все по модулям, прочитав статті і зрозумів, що теорія категорій виглядає набагато простіше, ніж вся ця жесть.

У файлі Helpers.js поряд з іншими допоміжними функціями визначені функції extend і combine. Функція extend вже давно придумана, вона дозволяє успадкувати один клас від іншого і докладно описана тут. Єдине, моя реалізація може додавати в клас домішки. Дуже рекомендую прочитати цю статтю про домішки, де вони розглядаються як фабрики підкласів, описується як їх можна компактно описувати ES6. Взагалі, погляд на домішки як на більш загальний випадок спадкування, при якому невідомий заздалегідь суперклас, досить цікавий.

Особисто я не хочу морочитися з Babel і т. п., тому вихідні коди написані на ES5 і знадобилися ці дві функції. Домішки не можна успадковувати як класи з допомогою extend, їх не можна змішувати з допомогою методу combine.

У файлі Category.js визначено абстрактний клас «категорія», від якого повинні успадковуватися специфічні категорії. Також у ньому визначено домішки «повна категорія» і «кополная категорія» і їх суміш «биполная категорія». Категорія множин, яку ми будемо розглядати далі, як-раз є биполной категорією і до неї «домішуються» деякі універсальні алгоритми, які можуть використовуватися в будь биполной категорії. Вони реалізовані саме у вигляді домішок, бо JavaScript не підтримує множинне успадкування. Далі все це пояснюється докладніше.

У файлі Set.js визначено 1) категорія множин, 2) самі множини, 3) функції і 4) деякі межі категорії множин. Теоретично клас Set можна замінити на Set з ES6. Функції реалізовані у вигляді так званих графиков, тобто у них в явному вигляді зберігаються:

  • допустима множина вхідних елементів – домен (область визначення);
  • допустиме безліч кінцевих елементів – кодомен (область значень);
  • безліч пар: вхідний елемент і відповідний йому результуючий елемент.
Домен і кодомен зберігаються в явному вигляді, щоб можна було перевіряти допустима композиція двох функцій. Вона допустима лише, якщо домен 1-ої функції збігається з кодоменом 2-ой. Також домен використовується при перевірці того дійсно функція є повною або частково визначена функція. Якщо ви подивіться код, там дуже багато подібних перевірок (виклики assert).

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

У файлі SetCategoryView.js рісовалка діаграм для категорії множин, заснована на d3. Майже всі ілюстрації у статті намальовані з її допомогою. До речі, в 4-ій версії d3 вдосконалили Force Layout, тепер там можна самостійно визначати власні сили. Удосконалили drag'n'drop, якщо я не помиляюся, то раніше він працював тільки для svg, а зараз легко підтримується і для canvas. У цій рисовалке ви теоретично можете знайти щось цікаве, але вона вимагає повного рефакторінгу.

У файлі Set.html всі приклади з даної статті.

Реалізація категорії множин

Далі я буду описувати різні конструкції з категорії множин і як вони реалізуються в коді. Сама вона реалізована у вигляді наступної фабрики:

function SetCategory() { }
extend(SetCategory, Category, BicompleteCategory);

SetCategory.prototype.object = function (elements) {
return new Set(elements);
};
SetCategory.prototype.morphism = function (A, B, mapping) {
return new TotalFunction(A, B, mapping);
};
SetCategory.prototype.id = function (A) {
return this.morphism(A, A).initId();
};
SetCategory.prototype.compose = function (g, f) {
return g.compose(f);
};

Категорія множин успадковується від абстрактної категорії і до неї домішується поведінка биполной категорії.

Дана фабрика дозволяє створювати

  • об'єкти (які є множинами);
  • морфизмы (які є функціями, які відображають елементи деякої множини A на елементи деякої множини B);
  • тотожні морфизмы (які є тотожними відображеннями деякої множини A на себе);
  • композиції двох морфізмів.
Чесно кажучи, я не відразу усвідомив чому категорії повинні бути фабриками. Скажімо, множини, списки, стеки, дерева, графи та інші структури зазвичай в явному вигляді зберігають всі свої елементи. Категорії – це ніби аналогічні математичні структури, але чому вони реалізуються інакше? Чому не можна реалізувати категорію як сховище її об'єктів і морфізмів? Тому, що в загальному випадку категорія містить нескінченну кількість об'єктів і морфізмів. Причому, з них нам потрібні всього лише кілька. І їх потрібно не стільки зберігати, скільки конструювати на їх основі нові об'єкти і морфизмы.

Створимо кілька об'єктів і морфізмів:

var setCat = new SetCategory();
var obj123 = setCat.object([1,2,3]);
var objAB = setCat.object(['a','b']);
var objABCD = setCat.object(['a','b','c','d']);
var f = setCat.morphism(obj123, objABCD, {1: 'c', 2: 'c', 3: 'd'});
var g = setCat.morphism(objABCD, objAB, {'a': 'a', 'b': 'b'});
var h = setCat.morphism(objAB, obj123, {'a': 1, 'b': 1});
showSetCategoryView('diagram1', setCat, {'A': obj123, 'B': objABCD, 'C': objAB},
{'f': {dom: 'A', codom: 'B', morphism: f},
'g': {dom: 'B', codom: 'C', morphism: g},
'h': {dom: 'C', codom: 'A', morphism: h}});


Шкода, що не можна вставляти в статтю виконується JavaScript код. Тому доведеться вставляти картинки, але повторюся, що посувати все це можна тут.

Эпиморфизм, мономорфізм, ізоморфізм

Ок, ми вміємо створювати об'єкти, морфизмы і красиво їх малювати. Що далі?

Об'єкти і морфизмы можуть володіти різними властивостями і значна частина теорії категорій присвячена опису і вивчення цих властивостей. Наша реалізація теорії категорій повинна вміти перевіряти ці властивості і повинна уміти конструювати об'єкти і морфизмы з певними властивостями. Почнемо з найпростіших властивостей.

Нагадаю, що морфизмы в категорії множин – це функції. Зі школи ви напевно пам'ятаєте, що функції можуть бути сюръекциями, ін'єкціями, биекциями. Я обіцяв, що не буде строгих визначень і все буде пояснювати на пальцях, тому отримуйте:

Сюръекция – це функція, яка приймає значення з області значень. Скажімо, функція зведення в квадрат, визначена на множині цілих чисел, що не є сюръекцией, тому що вона не приймає значення 2, 3, 5,…


Ін'єкція – це функція, яка відображає різні елементи вихідного безлічі в різні елементи результуючого безлічі. При цьому область значень функції може містити деякі додаткові елементи, у яких немає прообразу в області визначення.


Биекция – це відображення один-до-одного. Функція є биекцией тоді і тільки тоді, коли вона є одночасно сюръекцией та ін'єкцією.


Для інших математичних об'єктів (наприклад, графів) існують якісь аналоги сюръекций, ін'єкцій і биекций. Тому в теорії категорій, раз ця теорія про все, вирішили узагальнити ці поняття і ввели відповідно эпиморфизмы, мономорфизмы і изоморфизмы.

У чому ж полягає це узагальнення? В тому, що в теорії категорій ми повністю абстрагуємося від внутрішнього пристрою об'єктів і морфізмів. Замість того, щоб визначати ці види морфізмів через кружечки і стрілочки, як це зроблено на малюнках вище, вони визначені через співвідношення з іншими морфизмами.

Эпиморфизм – це морфизм e : A → B, такий що з усякого рівності f ∘ e = g ∘ слід e f = g (іншими словами, на e можна скорочувати праворуч).


Щоб було зрозуміло, про що йдеться, наведу приклад НЕ эпиморфизма:


Діаграма вище коммутативна (f ∘ h = g ∘ h). Щоб у цьому переконатися, ви можете пройти по стрілках від кожного елемента множини A і, незалежно від обраного шляху, ви завжди прийдете до одного і того ж елементу множини C. тобто функції f ∘ h і g ∘ h для однакових аргументів повертають однакові результати. Але(!) з цього не випливає рівність функцій f і g. Для елемента «1» вони повертають різні значення: «a» і «b». А, от, якби функція h була эпиморфизмом, то з комутативності діаграми слід було б рівність f і g.

Далі я не буду докладно описувати «переходи по стрілках через кружечки», просто майте на увазі, що, коли в категорії множин йдеться про комутативних діаграм, ви завжди можете перевірити цю комутативність таким способом.

Ще раз зазначу, що ми описали сюръективные функції тільки через співвідношення з іншими функціями, повністю абстрагуючись від деталей їх внутрішнього устрою. В цьому суть теорії категорій.

Мономорфізм – це морфизм m : A → B, такий що з усякого рівності m ∘ f = m ∘ g випливає f = g (іншими словами, на m можна скорочувати ліворуч).


Ізоморфізм – це морфизм f : A → B, для якого існує зворотний, тобто існує морфизм g : B → A, таку що f ∘ g = idB і g ∘ f = idA.


Ось тут невеликий сюрприз. Не у всіх категоріях з того, що морфизм є эпиморфизмом і мономорфизмом випливає, що він також є і изоморфизмом. Це демонструє те, що категорія множин звичайно хороша для візуалізації якихось понять, але може призводити до помилкових аналогій.

Кінцевий, початковий і нульовий об'єкт

Кінцевий об'єкт – це об'єкт T, такий що для будь-якого об'єкта X існує єдиний морфизм u : X → T.

У категорії множин кінцевий об'єкт – це сінглетон, а унікальний морфизм – це функція, що відображає будь-який елемент вихідного безлічі в єдиний елемент сінглетона. Термінальних об'єктів в категорії нескінченну кількість множин, проте, всі вони ізоморфні один одному. Це означає, що з точки зору теорії категорій неважливо, про який саме синглетоне йде мова, все, що вірно для одного з точністю до ізоморфізму буде вірно і для будь-якого іншого сінглетона.


Початковий об'єкт – це об'єкт I, такий що для будь-якого об'єкта X існує єдиний морфизм u : І → X.

У категорії множин початковий об'єкт – це пусте безліч, а унікальний морфзим, визначений на порожньому безлічі – це марна функція. Причому, існує єдине порожня множина, відповідно, в категорії множин єдиний початковий об'єкт.


Нульовий об'єкт – це об'єкт, який є одночасно початковим і кінцевим об'єктом.

У категорії множин нульових об'єктів немає, оскільки безліч не може одночасно бути порожнім і бути синглетоном.

Відзначимо кілька важливих моментів.

Початкові і кінцеві об'єкти – це дуальні поняття, вони еквівалентні з точністю до звернення напрямки морфізмів. Початковий об'єкт буде кінцевим об'єктом у двоїстій категорії (категорії з такими ж об'єктами і операцією композиції, але морфизмами, спрямованими в зворотному напрямку). Ідея дуальності або подвійності дуже важлива в теорії категорій. Далі ви побачите ще декілька прикладів подвійних понять.

До речі, кінцеві об'єкти можна називати коначальными, а початкові – коконечными, але тут ми вже потрапляємо в область одного фундаментально нової мови програмування. Якщо додати або прибрати у поняття приставку «ко-», то отримаємо дуальна поняття. Кококонечные об'єкти я не зустрічав, хоча фахівець з теорії категорій повинен зрозуміти, що мова йде про початкових об'єктах.

У визначеннях вище нічого не говориться про морфизмах, спрямованих від кінцевого об'єкта. А вони існують. Наприклад, якийсь морфизм f : {1} → {1,2,3,4} з графіком {(1,1)} або морфизм g з такою ж сигнатурою, але графіком {(1,2)}. Тобто вони мало того, що існують, але ще й не унікальні і, забігаючи вперед, відіграють досить важливу роль. Тому уявлення про кінцевих об'єктах як про об'єкти, морфизмы яких спрямовані тільки до них, не вірно.


Щодо морфізмів, спрямованих до початкових об'єктів, не можу нічого сказати. Я припускаю, що в категорії множин їх або немає, або це порожні унікальні функції. В принципі, чому б їм і не бути. Але тоді, кожне безліч буде изоморфно порожнього безлічі. Якщо хтось може прояснити цей момент, було б чудово.

Універсальне властивість і самий важливий момент

Зверніть увагу на фразу «… існує єдиний морфизм ...» у визначеннях вище. Вона повсюдно зустрічається в роботах по теорії категорій. Це називається «універсальна властивість».

Універсальне властивість дозволяє визначити поняття, абстрагуючись від деталей. Ви бачите, що початковий і кінцевий об'єкти визначені без згадки порожніх множин, синглетонов, так, і, взагалі, будь-яких структур. Ось це справжня абстракція! Я думаю, що в посібниках з теорії категорій для розробників треба говорити в першу чергу саме про такі речі, а не про декартів замкнутих категоріях або монадах.

Іншими словами, в теорії категорій ви визначаєте об'єкти, роблячи акцент не на описі їх внутрішньої реалізації, а на описі їх зовнішнього поведінки, того, як вони можуть «спілкуватися» з іншими об'єктами, фактично ви описуєте їх інтерфейс. Правда, трохи інакше, ніж це зазвичай робиться в мовах програмування, але цим теорія категорій і цікава.

Внаслідок абстрагування від деталей універсальне властивість визначає з точністю до ізоморфізму. Вище ми вже відзначали, що в категорії множин всі кінцеві об'єкти (синглетоны) ізоморфні. Але це вірно для будь-яких об'єктів, визначених через універсальне властивість. В принципі, це цілком логічно: якщо два об'єкта зовні ведуть себе однаково (для них виконується одне універсальне властивість), значить вони ізоморфні.

І, напевно, найважливіший момент, який лежить в основі всього цього циклу статей. За універсальними властивостями зазвичай коштує деяка оптимізаційна задача, що полягає в пошуку найкращих в деякому сенсі об'єктів або морфізмів. Ми повернемося до цього в розділі про уравнители.

Реалізація кінцевих і початкових об'єктів

Дуже багато теорії, подивимося, як кінцеві і початкові об'єкти реалізовані в коді.
SetCategory.prototype.terminal = function () {
return new SetTerminalObject(this).calculate();
};
function SetTerminalObject(cat) {
this.cat = function () { return cat; };
}
SetTerminalObject.prototype.calculate = function () {
this.obj = new Set([1]);
return this;
}
SetTerminalObject.prototype.univ = function (A) {
var mapping = {};
A. forEach(function (el) {
mapping[el] = 1;
});
return this.cat().morphism(A, this.obj, mapping);
}

SetCategory.prototype.initial = function () {
return new SetInitialObject(this).calculate();
};
function SetInitialObject(cat) {
this.cat = function () { return cat; };
}
SetInitialObject.prototype.calculate = function () {
this.obj = new Set();
return this;
}
SetInitialObject.prototype.univ = function (A) {
return this.cat().morphism(this.obj, A, {});
}

У вас, можливо, виникло питання: навіщо стільки коду для реалізації сінглетона і ПОРОЖНЬОГО безлічі???

Кінцевий і початковий об'єкти – це не просто якісь множини. Для них ще має виконуватися універсальне властивість, яке має не якийсь теоретичний характер, але воно активно використовується в обчисленнях. Наприклад, при обчисленні доповнення до кодекартову квадрату обчислюється універсальний морфизм для суми об'єктів. Ми повернемося до цього пізніше.

У нашій реалізації у конструкцій, що володіють універсальним властивістю, будуть методи:

  • calculate – створює деяку універсальну конструкцію або збирає її з інших конструкцій,
  • complement – створює універсальну конструкцію з не дуже типових компонентів,
  • univ – обчислює для даної конструкції універсальні морфизмы.

Твір

Продовжимо несуворі визначення на пальцях і розглянемо трохи більш складні об'єкти.

Твір об'єктів Xj – це об'єкт X і морфизмы πj : X → Xj, називаються канонічними проекціями, такі, що для будь-якого об'єкта Y і морфізмів fj : Y → Xj існує єдиний морфизм u : Y → X, такий що πj ∘ u = fj.

В теорії категорій замість написання рівностей виду πj ∘ u = fj можна намалювати таку діаграму і сказати, що вона коммутативна (приклад для двох об'єктів, але в загальному випадку може бути більше):


У категорії множин твір об'єктів – це декартів добуток множин.


На малюнку твір позначено як AxB, а його елементи – як пари елементів з вихідних множин. Але це зроблено для наочності і зовсім не обов'язково! Твір можна назвати як завгодно, а його елементами можуть бути

  • 1, 2, 3, ...
  • квадрат, коло, трикутник, ...
  • або що завгодно.
Твір визначено не як множина пар значень, а через співвідношення між морфизмами. Порівняйте визначення декартова твори множин і твори об'єктів в теорії категорій – вони не мають нічого спільного. Ви знову бачите приклад абстрагування від деталей в теорії категорій.

В коді твір реалізовано наступним чином.
SetCategory.prototype.product = function (A, B) {
return new SetProduct(this).calculate(A, B);
};
function SetProduct(cat) {
this.cat = function () { return cat; };
}
SetProduct.prototype.calculate = function (A, B) {
var obj = new Set();
var mapping1 = {};
var mapping2 = {};
A. forEach(function (x) {
B. forEach(function (y) {
var z = [x, y].toString();
obj.add(z);
mapping1[z] = x;
mapping2[z] = y;
});
});
this.obj = obj;
this.f = this.cat().morphism(this.obj, A, mapping1);
this.g = this.cat().morphism(this.obj, B, mapping2);
return this;
};
SetProduct.prototype.univ = function(m, n) {
assertEqualDom(m, n);
assertEqualCodom(this.f, m);
assertEqualCodom(this.g, n);
var obj = m.dom();
var mapping = {};
obj.forEach(function (x) {
var s1 = this.f.preimage(m.image(x));
var s2 = this.g.preimage(n.image(x));
mapping[x] = s1.intersection(s2).representative();
}.bind(this));
var u = this.cat().morphism(obj, this.obj, mapping);
assertCommutes(this.f.compose(u), m);
assertCommutes(this.g.compose(u), n);
return u;
};

Зверніть увагу, що в calculate обчислюється не тільки декартів добуток множин, але і два морфизма – канонічні проекції твори на вихідні об'єкти. У більшості обчислень саме вони відіграють основну роль і, грубо кажучи, вони набагато важливіше безлічі.

Функція univ обчислює універсальний морфизм (u – на діаграмі вище) для деякого об'єкта і пари морфізмів. Подивимося, чим може бути корисний універсальний морфизм твори.

На наступній діаграмі ви бачите об'єкти A і B, їх твір AxB, а також деякий довільний об'єкт C з морфизмами f1 f2.


Ви бачите, що елемент «1» множини C відображається на елемент «1» множини A і на елемент a множини B. Точно також як елемент «1,a» безлічі AxB. При обчисленні універсального морфизма ми встановлюємо цей факт і конструюємо універсальний морфизм таким чином, щоб він відображав елемент «1» множини C на елемент «1,a» безлічі AxB.

Елементи «4» і «5» множини C відображаються морфизмами f1 f2 на одні і ті ж елементи. Тому універсальний морфизм відображає їх на один елемент «2,b» безлічі AxB.

Для наочності уявімо, що C – це безліч мавпочок. f1 кожну мавпочку відносить до однієї з категорій: гарна чи негарна, а f2 – до однієї з категорій: розумна чи дурна. Тоді універсальний морфизм u відносить кожну мавпочку до однієї з чотирьох категорій: красива і розумна, гарна і дурна, негарна і розумна, негарна і дурна.

Фактично, універсальний морфизм для твору – це твір морфізмів.

Твір в різному вигляді реалізовано в різних мовах програмування. Це і структури, і кортежі, і всілякі join'и в SQL, LINQ і т. п. Почитайте про типи-твори.

В JavaScript канонічні проекції твору можна розглядати як деструктори або акцессоры:

monkeyKind.a
monkeyKind.b

а універсальні морфизмы – як конструктори:

let u = x => { a : isBeautiful(x), b : isSmart(x) }

В теорії категорій акцессоры часто називають деструкторами, тому що вони дозволяють розібрати складний об'єкт на складові частини, вони дуальни конструкторам. При виклику такої деструктора об'єкт зовсім не обов'язково повинен знищуватися.

Сума

Сума об'єктів Xj – це об'єкт X і морфизмы ij : Xj → X, звані канонічними вкладеннями, такі, що для будь-якого об'єкта Y і морфізмів fj : Xj → Y існує єдиний морфизм u : X → Y, такий що u ∘ ij = fj.

Приклад комутативних діаграм для двох об'єктів:


У категорії множин сума об'єктів – це дизъюнктивное об'єднання множин. Тобто якщо у об'єднуються множинах є спільні об'єкти, то ці об'єкти не будуть зливатися, а, грубо кажучи, деяким чином відзначені, щоб можна було зрозуміти з якого безлічі кожен об'єкт.


В теорії множин елементи дизъюнктивного об'єднання зазвичай позначають деяким тегами або індексами, наприклад, 1A, 2A, 3A, aB, bB. Але в нашому прикладі елементи суми – це просто числа від 1 до 5, які пов'язані з елементами вихідного безлічі морфизмами f і g. І саме ці морфизмы «позначають» елементи суми. Як і для твору саму множину без морфізмів не грає особливої ролі.

Очевидно, що добуток і сума – це дуальні поняття. Вони сформульовані аналогічно з точністю до звернення морфізмів.

Але на цьому узагальнення не закінчуються. Добуток і сума дуже схожі на кінцевий і початковий об'єкти відповідно. Для творів і кінцевих об'єктів можна від кожного категорії об'єкта, що задовольняє певним умовам, побудувати універсальний морфизм – такі конструкції називають межами. Для суми і початкового об'єкта можна до кожного об'єкту категорії, що задовольняє певним умовам, побудувати універсальний морфизм – такі конструкції називають копределами. Далі ви побачите ще декілька прикладів меж і копределов.

В загальному випадку (ко)межі – це (ко)конуси, визначені для деякої діаграми. Як я вже говорив, діаграма – це функтор з деякою індексного категорії в поточну категорію. Якщо грубо, то індексний категорія визначає «форму», «вид» діаграми і в підсумку визначає якою (ко)межа ми отримаємо (кінцевий об'єкт, твір, ...). Якщо далі розвивати цю думку, то ми ризикуємо викликати какодемона.



Коротше, ідея в тому, що навіть такі загальні поняття, які ми розглянули вище, можна узагальнити ще сильніше.

Щоб запам'ятати, ніж межі відрізняються від копределов, зверніть увагу на те, що універсальні морфизмы завжди спрямовані (прагнуть) до певного «граничного» об'єкту. Так само як і межі послідовностей і функцій прагнуть до деякого значення.

Реалізація суми об'єктів аналогічна реалізації інших (ко)меж.
SetCategory.prototype.coproduct = function (A, B) {
return new SetCoproduct(this).calculate(A, B);
};
function SetCoproduct(cat) {
this.cat = function () { return cat; };
}
SetCoproduct.prototype.calculate = function (A, B) {
this.obj = new Set();
var elementCount = 1;
function createInjection(set, obj) {
var mapping = {};
set.forEach(function (x) {
obj.add(elementCount);
mapping[x] = elementCount;
elementCount++;
});
return mapping;
}
this.f = this.cat().morphism(A, this.obj, createInjection(A, this.obj));
this.g = this.cat().morphism(B, this.obj, createInjection(B, this.obj));
return this;
};
SetCoproduct.prototype.univ = function(m, n) {
assertEqualCodom(m, n);
assertEqualDom(this.f, m);
assertEqualDom(this.g, n);
var obj = m.codom();
var mapping = {};
function addMappings(f, h) {
h.dom().forEach(function (x) {
mapping[f.image(x)] = h.image(x);
});
}
addMappings(this.f, m);
addMappings(this.g, n);
var u = this.cat().morphism(this.obj, obj, mapping);
assertCommutes(u.compose(this.f), m);
assertCommutes(u.compose(this.g), n);
return u;
};

Спробуємо розібратися, що робить універсальний морфизм суми об'єктів.


Нагадаю, що канонічні проекції твору можна розглядати як деструктори твори об'єктів, а універсальний морфизм – як конструктор. Сума – це дуальна поняття.

Відповідно, канонічні вкладення можна розглядати як конструктори суми об'єктів, а універсальний морфизм – як деструктор. Почитайте про типи-суми. В тому чи іншому вигляді вони реалізовані в дуже різних мовах програмування. Як правило, в якості прикладів наводять алгебраїчні типи даних і зіставлення зі зразком. Але в JavaScript цього немає, тому наведу трохи інший приклад.

Нехай у нас є два види мавпочок – шимпанзе і горили – з відповідними конструкторами:

function Chimpanzee() { }
function Gorilla() { }

Нехай для шимпанзе нам потрібно обчислювати деяку функцію p, а для горил – q, при цьому область значень обох функцій – це деякий безліч C. Наприклад, C – це перерахування: маленька, середня, велика. Функція p обчислює категорію, до якої відноситься шимпанзе в залежності від розміру, а функція q обчислює категорію для горили:

let u = x => switch (typeof x) {
case 'Chimpanzee': return p(x);
case 'Gorilla': return q(x);
}

Віднімання (додаток до суми)

Якщо ви щось читали по теорії категорій, то навряд чи побачили вище для себе щось нове. А чи чули ви, наприклад, про вирахування об'єктів в теорії категорій? Ідея абсолютно очевидна, правда, в англомовних статтях зазвичай говорять про обчислення coproduct complement. На російську мову можна перевести як обчислення доповнення до суми об'єктів. Але, по суті, це операція віднімання.

Нехай є сума об'єктів A+B, один з доданків A об'єктів і відповідне йому канонічне вкладення i1. Або просто канонічне вкладення i1, домен якого є A, а кодоменом – A+B. Якщо ми обчислимо інший канонічний морфизм i2, то фактично віднімемо з суми одне з доданків:


Реалізовано це наступним чином.
SetCategory.prototype.coproductComplement = function (f) {
return new SetCoproduct(this).complement(f);
};
SetCoproduct.prototype.complement = function (f) {
this.obj = f.codom();
this.f = f;
this.g = this.cat().morphism(f.codom().diff(f.image()), this.obj).initId();
return this;
};

В загальному випадку сума об'єктів може бути N-арної, а не тільки бінарної. Однозначно обчислити додаток можна тільки для бінарної суми. Доповнення до сум нам знадобляться пізніше для обчислення доповнень до кодекартовым квадратах.

Зрівнювач

Вище ми вже розглянули (ко)межі для порожніх діаграм (кінцеві і початкові об'єкти) і для дискретних об'єктів (добуток і сума). Тепер розглянемо (ко)межі для пари паралельних морфізмів, тобто морфізмів з загальними доменом і кодоменом.

Зрівнювач паралельних морфізмів f, g : X → Y – це об'єкт E і морфизм eq : E → X, що f ∘ eq = g ∘ eq і для будь-якого об'єкта O і морфизма m : O → X якщо f ∘ m = g ∘ m, то існує унікальний морфизм u : O → E, такий що eq ∘ u = m, тобто наступна діаграма коммутативна.


Охх… свого часу я прочитав кілька підручників з теорії категорій. І десь на цьому місці переставав розуміти про що взагалі йде мова. Це відбувалося з двох причин. По-перше, я лінувався малювати множини та функції на папері і при цьому, не будучи Георгієм Перельманом, не міг сконструювати все це в уяві. Як наслідок, я не розумів ці конструкції навіть для категорії множин, не кажучи про інших категоріях. Далі будуть діаграми, на яких візуально видно сенс вирівнювача. По-друге, навіть більш прості твір та об'єктів суму я розумів тільки на інтуїтивному рівні, не розуміючи сенс універсальної властивості. Загалом і в цій статті я поки не розглядав толком універсальне властивість. Розберемося з ним більш детально на прикладі вирівнювача.

Спочатку розберемося з умовою f ∘ eq = g ∘ eq. Для зручності зобразимо об'єкт X і морфизм eq двічі, щоб морфизмы f і g не накладалися один на одного.


Морфизмы f і g відображають елемент «1» множини X на елемент a множини Y. Отже, якщо морфизм eq буде відображати якийсь елемент «1» множини E пункт «1» множини X, то буде виконано рівність f(eq(1)) = g(eq(1)) = a. На малюнку видно, що шляхи, що починаються з елемента «1» у множині E, закінчуються одними і тим же елементом в безлічі Y.

Морфизм f відображає елемент «2» пункт «a», а морфизм g відображає елемент «2» на елемент «b». Отже, як не реалізуй відображення eq, при проходженні через елемент «2» в множині X шляхи розійдуться. Тобто який елемент не постав замість знака питання f(eq(?)) = a ніколи не буде дорівнює g(eq(?)) = b, тому що елемент a не дорівнює b.

Продовжуємо ці міркування для решти елементів множин X і Y і таким чином завершуємо формування E і eq. Тільки елементи «1» і «3» відображаються функціями f і g однаково.

Це має бути відносно зрозуміло, при обчисленні E і eq ми дійсно знаходимо щось спільне між f і g. Але навіщо у визначенні об'єкт O і морфизмы m і u? Справа в тому, що безліч E і морфизм eq, які ми побудували, не унікальні. Додамо на діаграму O m, для яких теж виконується f ∘ m = g ∘ m.


Виходить, що m зрівнює f і g не гірше, ніж eq. Чим взагалі eq краще m? Таких зрівнювачів ми можемо побудувати нескінченну кількість. Очевидно, що E і eq простіше, ніж O m і тому, напевно, краще. Але в теорії категорій ми не можемо сказати, що морфизм вирівнювача повинен містити найменшу кількість елементів, тому що, як я вже зазначав, ми максимально абстрагуємося від внутрішнього пристрою об'єктів і морфізмів. В якійсь іншій категорії немає ніяких множин і функцій, тому прив'язуючись до кількості елементів, ми дуже сильно обмежили б застосовність зрівнювачів.

Отже, як з усіх потенційних зрівнювачів вибрати кращий? На допомогу приходить універсальне властивість. Від E об'єкта до об'єкта O можна провести два морфизма h, для яких виконується умова m ∘ h = eq, це {(1,1),(3,3)} і {(1,2),(3,3)}. А, отже, O, m не є зрівнювачем, так як для них не виконується універсальне властивість.

А, от, для E і eq універсальне властивість як-раз виконується. Ми можемо обчислити універсальний морфизм для O, m і отримаємо u = {(1,1),(2,1),(3,3)}. Для інших O m, для яких виконується f ∘ m = g ∘ m, універсальний морфизм буде інший, але все одно унікальний.

А що якщо O m будуть відповідно такого ж розміру як E і eq? Який зрівнювач буде краще? Вони ізоморфні, з точки зору теорії категорій не суттєво який вибрати.

І тільки скажіть, що теорія категорій не потрібна простому роботязі, фигачящему на JavaScript! Потрібна, вона дозволяє побачити справжнє абстрагування, а не те, що називають абстрагированием всякі ООПшники і іже з ними (іронія).

Реалізація в коді не особливо складніше реалізації (ко)меж, розглянутих раніше.
SetCategory.prototype.equalizer = function (f, g) {
return new SetEqualizer(this).calculate(f, g);
};
function SetEqualizer(cat) {
this.cat = function () { return cat; };
}
SetEqualizer.prototype.calculate = function (f, g) {
assertParallel(f, g);

this.f = function () { return f };
this.g = function () { return g };

var dom = new Set();
var codom = f.dom();
this.q = this.cat().morphism(dom, codom);
f.dom().forEach(function (x) {
if (f.image(x) == g.image(x)) {
dom.add(x);
this.q.push(x, x);
}
}.bind(this));

this.obj = this.q.dom();

assertCommutes(f.compose(this.q), g.compose(this.q));
return this;
}
SetEqualizer.prototype.univ = function (m) {
assertEqualCodom(this.q, m);
assertCommutes(this.f().compose(m), this.g().compose(m));
var mapping = {};
m.forEach(function (x, y) {
mapping[x] = this.q.preimage(y).representative();
}.bind(this));
var u = this.cat().morphism(m.dom(), this.obj, mapping);
assertCommutes(this.q.compose(u), m);
return u;
};

Відзначимо ще один момент. У підручниках по теорії категорій написано, що будь-зрівнювач – це мономорфізм. Уважний читач напевно помітив, що умова f ∘ eq = g ∘ eq для вирівнювача дуже схоже на умову f ∘ m = g ∘ m для… эпиморфизма. Стоп, чому эпиморфизма, а не мономорфизма? В даному випадку схожість рівнянь призводить до виникнення помилкових аналогій.

Рівність для эпиморфизма можна скоротити на эпиморфизм і при цьому буде виконуватися рівність f = g. А, от, якщо скоротити рівність на зрівнювач, то морфизм f не дорівнює g. Швидше навпаки, зрівнювач, як правило, застосовується до нерівних морфизмам. У цьому легко переконатися, якщо ще раз подивитися на малюнки вище. Морфизмы f і g не рівні, а зрівнювач eq не є сюръекцией (эпиморфизмом в категорії множин).

Гаразд, але чому він тоді є мономорфизмом? Це випливає з універсального властивості. Будь-які два морфизма від деякого об'єкта O до об'єкту E будуть рівні. З іншого боку, видно, що в нашому прикладі зрівнювач – це ін'єкція (мономорфізм в категорії множин), і універсальне властивість гарантує, що це завжди буде ін'єкція.

Навіщо я описую всю цю жесть? Щоб ще раз показати, що для «простих» категорій можна зрозуміти зміст різних конструкцій чи теорем, представляючи які реальні речі (множини, функції) за всім цим стоять. Ви ніколи не зрозумієте, що все це значить, якщо не будете малювати подібні картинки.

Коуравнитель

Коуравнитель паралельних морфізмів f, g : X → Y – це об'єкт Q і морфизм q : Y → Q, такі що q ∘ f = q ∘ g і для будь-якого об'єкта O і морфизма m : Y → O якщо m ∘ f = m ∘ g, то існує унікальний морфизм u : Q → O, такий що u ∘ q = m, тобто наступна діаграма коммутативна.


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

Розглянемо це на прикладі конкретних множин і функцій.


Обидва морфизма f і g, для яких ми обчислюємо коуравнитель, відображають елемент «1» множини X на елемент a множини Y. Щоб виконувалося рівність q(f(1)) = q(g(1)), достатньо, щоб морфизм q просто відображав елемент «a» на деякий елемент a множини Q.

Морфизм f відображає елемент «2» на елемент «b», а морфизм g відображає елемент «2» пункт «c». Щоб виконувалося рівність q(f(2)) = q(g(2)), морфизм q повинен відображати елементи «b» і «c» на якийсь елемент «b» множини Q. Іншими словами, ми об'єднали елементи «b» і «c» в один клас еквівалентності «b».

Морфизм f відображає елемент «3» пункт «c», а морфизм g відображає елемент «3» пункт «d». Як і раніше, це означає, що «c» і «d» необхідно об'єднати в один клас еквівалентності. Однак «c» вже належить до класу «b», тому ми не створюємо новий клас, а просто відносимо елемент «d» до класу «b».

Аналогічно створюємо клас еквівалентності «e» для елементів «e» і «f». І завершуємо формування коуравнителя Q з морфизмом q.

Проте, керуючись такою логікою, ми можемо побудувати певний об'єкт O з морфизмом m, для яких так само як і для коуравнителя виконується умова m ∘ f = m ∘ g. Причому, O, m будуть навіть простіше, ніж Q і q.


Але O m не будуть коуравнителем, тому що для них не виконується універсальне властивість, і тому вони в деякому сенсі гірше, ніж Q і q. Гірше тим, що вони занадто прості, вони не розрізняють класи «a» і «b», змішуючи їх у клас «1».

Зверніть увагу на те, що універсальне властивість вирівнювача дозволяє відібрати найменші об'єкт і морфизм серед усіх потенційно підходящих. А універсальне властивість коуравнителя – дозволяє відібрати найбільші об'єкт і морфизм. Напевно, багато подібні задачі структурної оптимізації можна звести до пошуку (ко)меж у тій чи іншій категорії.

Ось, як коуравнители реалізовані в коді.
SetCategory.prototype.coequalizer = function (f, g) {
return new SetCoequalizer(this).calculate(f, g);
};
function SetCoequalizer(cat) {
this.cat = function () { return cat; };
}
SetCoequalizer.prototype.calculate = function (f, g) {
assertParallel(f, g);

this.f = function () { return f };
this.g = function () { return g };

var dom = f.codom();
var codom = new Set();
var eq = {};
f.dom().forEach(function (x) {
var fx = f.image(x);
var gx = g.image(x);
eq[fx] = eq[gx] = has(eq, fx) ? eq[fx] : has(eq, gx) ? eq[gx] : fx;
});
this.q = this.cat().morphism(dom, codom);
dom.forEach(function (s) {
var t = eq[s] || s;
codom.add(t);
this.q.push(s, t);
}.bind(this));

this.obj = this.q.codom();

assertCommutes(this.q.compose(f), this.q.compose(g));
return this;
}
SetCoequalizer.prototype.univ = function (m) {
assertEqualDom(this.q, m);
assertCommutes(m.compose(this.f()), m.compose(this.g()));
var mapping = {};
m.dom().forEach(function (x) {
mapping[this.q.image(x)] = m.image(x);
}.bind(this));
var u = this.cat().morphism(this.q.codom(), m.codom(), mapping);
assertCommutes(u.compose(this.q), m);
return u;
};

Коуравнитель – це дуже корисна з точки зору ІТ конструкція. Він дозволяє вирішувати різні завдання уніфікації: уніфікації типів у мовах програмування, уніфікації виразів в системах комп'ютерної алгебри, уніфікації графів. З тієї ж області завдань злиття моделей або вихідного коду. Ми повернемося до цього в наступних статтях.

Декартов квадрат (расслоенное твір)

Зрівнювач обчислюється для двох паралельних морфізмів. А що, якщо обчислити межа для двох морфізмів, у яких збігається тільки кодомен? Ми отримаємо ще один вид межі – декартов квадрат.

Декартов квадрат морфізмів f : X → Z і g : Y → Z – це об'єкт P і морфизмы p : P → X і q : P → Y, такі, що f ∘ p = g ∘ q і для будь-якого об'єкта Q і морфізмів m : Q → X і n : Q → Y, якщо f ∘ m = g ∘ n, то існує унікальний морфизм u : Q → P, такий, що p ∘ u = m і q ∘ u = n, тобто наступна діаграма коммутативна.


Виглядає складно, але в категорії множин це всього-навсього расслоенное твір:


На малюнку видно, що множина P містить пари елементів з множин X і Y, але не всі можливі, як у випадку з декартовым твором, а тільки такі, складові елементи яких функцій f і g відображаються на одні і ті ж елементи множини Z.

Якщо ви спробуєте у вихідному коді знайти реалізацію декартова квадрата для категорії множин, то не зможете, тому що він реалізований для будь повної категорії, а не тільки категорії множин.

Універсальна реалізація декартова квадрата для довільної повної категорії.
CompleteCategory.prototype.pullback = function (f, g) {
return new Pullback(this).calculate(f, g);
};
function Pullback(cat) {
this.cat = function () { return cat; };
}
Pullback.prototype.calculate = function (f, g) {
assertEqualCodom(f, g);
this.f = f;
this.g = g;

var prod = this.cat().product(f.dom(), g.dom());
this.product = function () { return prod; };

var eq = this.cat().equalizer(f.compose(prod.f), g.compose(prod.g));
this.equalizer = function () { return eq; };

this.p = prod.f.compose(eq.q);
this.q = prod.g.compose(eq.q);
this.obj = eq.obj;
assertCommutes(this.f.compose(this.p), this.g.compose(this.q));
return this;
}
Pullback.prototype.univ = function (m, n) {
assertEqualDom(m, n);
assertEqualCodom(m, this.p);
assertEqualCodom(n, this.q);
var u = this.equalizer().univ(this.product().univ(m, n));
assertCommutes(this.p.compose(u), m);
assertCommutes(this.q.compose(u), n);
return u;
};

Декартов квадрат обчислюється наступним чином. Спочатку отримуємо твір об'єктів X і Y, а потім обчислюємо зрівнювач для двох паралельних морфізмів f ∘ π1 і g ∘ π2. Об'єкт вирівнювача – це і є об'єкт P декартова квадрата. Морфизм p обчислюється як π1 ∘ eq, а q – як π2 ∘ eq. Універсальна властивість декартова квадрата обчислюється на основі універсальних властивостей твори і вирівнювача.


Причому, цей алгоритм застосуємо в будь повної категорії: категорії топологічних просторів, груп, кілець і т. п. Я поняття не маю, що це за категорія топологічних просторів, але я знаю, що вона повна і значить в ній буде працювати цей алгоритм. Це приклад профіту, що отримується завдяки абстрагування від внутрішнього представлення об'єктів і морфізмів. Більш того, в повній категорії можна обчислювати і більш складні межі з довільною діаграмою на основі найпростіших меж, розглянутих в даній статті.

Кодекартов квадрат (універсальний квадрат)

Кодекартов квадрат морфізмів f : Z → X і g : Z → Y – це об'єкт P і морфизмы p : X → P та q : Y → P, такі, що p ∘ f = q ∘ g і для будь-якого об'єкта Q і морфізмів m : X → Q і n : Y → Q, якщо m ∘ f = n ∘ g, то існує унікальний морфизм u : P → Q, такий що u ∘ p = m і u ∘ q = n, тобто наступна діаграма коммутативна.


Кодекартов квадрат дуален декартову квадрату і може бути обчислений у будь кополной категорії як коуравнитель морфізмів i1 ∘ f і i2 ∘ g, де i1 i2 – це канонічні включення суми об'єктів X і Y. Морфизмы p і q обчислюються як h ∘ i1 і h ∘ i2 відповідно, де h – морфизм коуравнителя:


Іншими словами, безліч P – це дизъюнктивное об'єднання множин X та Y, причому ті елементи, у яких однакові прообрази в множині Z, об'єднані:


Кодекартов квадрат аналогічно коуравнителю використовується в задачах уніфікації. На діаграмі ви бачите, що елементи «a» і «b» з множин X і Y були уніфіковані в множині P елементи «1» і «2» відповідно. Елемент «c» з множини X був уніфікований з елементом «d» з безлічі Y. А елемент «c» з множини Y не був ні з чим уніфікований.

З допомогою кодекартова квадрата можна вирішувати і більш цікаві завдання. Нехай відомі морфизмы g і q. Якщо ми обчислимо морфизмы f і p, то фактично отримаємо об'єкт X видаленням з P усього, що притаманне тільки Y. Це називається обчисленням доповнення до кодекартову квадрату. В наступних статтях на прикладі графів це буде більш наочно.

Ще раз звертаю вашу увагу на те, що обчислення кодекартова квадрата (як, до речі, і доповнення до нього) реалізовано незалежно від множин, функцій та інших деталей внутрішнього устрою тій чи іншій категорії:

Універсальна реалізація кодекартова квадрата для довільної кополной категорії.
CocompleteCategory.prototype.pushout = function (f, g) {
return new Pushout(this).calculate(f, g);
};
function Pushout(cat, f, g) {
this.cat = function () { return cat; };
}
Pushout.prototype.calculate = function (f, g) {
assertEqualDom(f, g);
this.f = f;
this.g = g;

var cp = this.cat().coproduct(f.codom(), g.codom());
this.coproduct = function () { return cp; };

var ceq = this.cat().coequalizer(cp.f.compose(f), cp.g.compose(g));
this.coequalizer = function () { return ceq; };

this.p = ceq.q.compose(cp.f);
this.q = ceq.q.compose(cp.g);
this.obj = ceq.obj;
assertCommutes(this.p.compose(this.f), this.q.compose(this.g));
return this;
}
Pushout.prototype.univ = function (m, n) {
assertEqualCodom(m, n);
assertEqualDom(m, this.p);
assertEqualDom(n, this.q);
var u = this.coequalizer().univ(this.coproduct().univ(m, n));
assertCommutes(u.compose(this.p), m);
assertCommutes(u.compose(this.q), n);
return u;
};

Що почитати

Фактично, моя стаття є плагіатом ідей з цієї книги, єдине, замість JavaScript вони використовують ML:
D. E. Rydeheard, R. M. Burstall. Computational Category Theory, 1988

Також я сплагіатив багато ідей звідси, але про це вже в наступних частинах:
Hans Jürgen Schneider. Graph Transformations. An Introduction to the Categorical Approach, 2011

Сам не читав, тільки гортав, але, начебто, непогана книга з безліччю прикладів, написана простою мовою:
Peter Smith, Category Theory. A Gentle Introduction, 2016

Має бути цікаво тим, хто пише на функціональних мовах програмування:
Maarten M. Fokkinga. A Gentle Introduction to Category Theory — the розрахункові approach, 1994

Ще пара не дуже простих книг для тих, хто пише на функціональних ЯП:
Andrea Asperti, Giuseppe Longo. Categories, Types and Structures. Category Theory for the working computer scientist, 1991
Michael Barr, Charles Wells. Category Theory for Computing Science, 1998

Звичайно, варто почитати цикл статей «Теорія категорій для програмістів» оригінал — Bartosz Milewski), але, на мій погляд, він орієнтований переважно на людей, які пишуть на ФЯП. У нас трохи інший підхід, повернемося до цього в ув'язненні.

У даній статті ми максимально абстрагувалися від елементів множин. Але, взагалі, у теорії категорій є поняття елемент об'єкта. Воно більше загальне, але за змістом схоже на елемент множини. Також в теорії категорій є узагальнення ідеї підмножин — подобъекты. Я сподіваюся, ми повернемося до них в наступних статтях, а поки можна подивитися наступну книгу. Хоча вона і розрахована на математиків, але, принаймні, у 1-му розділі мова відносно простий:
Michael Barr, Charles Wells. Toposes, Triples and Theories, 1985

Тим, хто цікавиться базами даних, рекомендую почитати статті чола по імені David I. Spivak. Я сам тільки гортав, але виглядає дуже цікаво.

Цікава стаття про додаток теорії категорій до нейронних мережах:
Michael J. Healy. Category Theory Applied to Neural Modeling and Graphical Representations, 2000

Висновок

У статті ви побачили обчислювальний аспект теорії категорій. Зазвичай, коли говорять про обчисленнях, то згадують декартів замкнуті категорії або монади Але в теорії категорій за більшістю конструкцій стоять ті чи інші обчислення, а не тільки за монадами. Теорія категорій більшою мірою про обчисленнях на структурах, ніж про самих структурах.

Я зустрічав два способи пояснити ИТшнику, що таке теорія категорій. Деякі автори розглядають як категорії систему типів і функції деякої мови програмування. Наприклад, в Haskell така категорія називається Hask. У даній статті використовується інший підхід. Ми розглянули категорію множин як є, не пов'язуючи безлічі з типами даних, а морфизмы з функціями деякого ЯП. Для кожної розглянутої конструкції ми побачили її обчислювальний аспект і реалізували його. Таким чином можна реалізувати будь-яку категорію на будь-якій мові програмування. Зовсім не обов'язково намагатися якимось чином вбудувати теорію категорій в цю мову.

У статті ви побачили приклади абстрагування від деталей внутрішнього обладнання об'єктів і морфізмів. Наприклад, побачили, як можна визначити сюръективные функції або декартовий добуток, нічого не кажучи про множинах. Абстрагування в програмуванні дуже схоже на абстрагування в теорії категорій. У мене навіть відчуття, що той, хто придумав ООП, черпав натхнення з теорії категорій.

Після прочитання статті ви повинні розуміти, що універсальне властивість – це, по суті, абстрактне представлення деякої задачі на пошук оптимальної структури.

Також ви побачили профіт від застосування теорії категорій.

По-перше, вона допомагає правильно організовувати код, правильно називати класи та функції. Наприклад, я міг би назвати метод обчислення декартова твори множин calcCartesianProduct(), міг би придумувати якісь функції типу multiplyFunctions(). Але завдяки теорії категорій я розумію, що твори об'єктів бувають і в інших категоріях і не зводяться тільки до декартову твору, а твір функцій — це універсальний морфизм твори. Тобто в абсолютно різних категорій буде єдиний інтерфейс.

По-друге, теорія категорій дозволяє писати універсальні алгоритми, типу обчислення декартова квадрата, які можуть повторно використовувати для різних категорій.

-третє, теорія категорій дозволяє писати код, дуже добре покритий перевірками. Зверніть увагу, що в багатьох функціях перевіряються різні передумови та постусловия (виклики assert на початку і в кінці функцій відповідно). Причому, мені не потрібно якось штучно придумувати ці перевірки, вони випливають із визначень!

І, взагалі, зверніть увагу на той написаний весь код в статті. Спочатку ми описуємо деяку зовнішню поведінку об'єкта, його співвідношення з іншими об'єктами, у декларативному вигляді описуємо різні універсальні властивості, інваріанти, які повинні виконуватися для даного об'єкта. А потім думаємо, як це декларативне опис реалізувати в коді. При цьому реалізація виходить «правильна», універсальна і покрита перевірками.

Можливо, ви дізналися щось цікаве про домішки і сумішах в JavaScript.

попередній статті я трохи говорив про застосуванні теорії категорій для перетворення моделей. У наступних статтях ми будемо рухатися в цьому напрямку і розглянемо категорію графів, категорію графів з мітками і більш докладно зупинимося на кодекартовых квадратах.

Вихідні коди і приклади зі статті.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.