Твори та котвори
Іди за стрілками
Цей процес можна порівняти з пошуком у мережі. Запит користувача – це наш шаблон. Якщо запит не дуже специфічний, то у відповідь пошукова система видасть безліч відповідних документів, тільки частина з яких є релевантними. Щоб унеможливити нерелевантні відповіді, користувач уточнює запит, що збільшує точність пошуку. Зрештою, пошукова система проранжує збіги і, якщо пощастить, шуканий результат буде на самому початку списку.
Початковий (ініціативний) об'єкт
Розглянемо кілька прикладів. Початковий об'єкт у частково впорядкованій множині — це найменший елемент. Деякі частково впорядковані множини, такі як всі цілі числа (і позитивні, і негативні), не мають початкового об'єкта.
Термінальний об'єкт
отже, всі вимоги до термінального об'єкта виконані.
Зауважимо, що в даному випадку умова єдиності критично важлива, оскільки існують і інші множини (насправді всі множини крім порожнього), які мають вхідні морфізми з будь-якого іншого типу. Наприклад, існує функція зі значеннями типу Bool (предикат), визначена для будь-якого типу аргументу:
Однак Bool не є термінальним об'єктом, тому що існує принаймні ще одна функція з будь-якого типу Bool :
Вимога єдиності морфізмів дає нам необхідну точність, звужуючи набір відповідних термінальних об'єктів до одного.
Подвійність
Ізоморфізми
Програмісти добре знають, що визначити рівність не так просто. Що означає, що два об'єкти рівні? Чи повинні вони займати ту саму область пам'яті (рівність покажчиків)? Чи достатньо того, що значення всіх їх компонентів збігаються? Чи вважаютьсярівними два комплексні числа, якщо одне з них задано дійсною та уявною компонентами, а інше — аргументом та модулем? Можна було б сподіватися, що математики мають сакральне знання про визначення рівності, але це не так. У математиці також існує безліч видів рівності, а також слабше поняття ізоморфізму і ще слабше — еквівалентності.
Поняття оборотності виражається у термінах композиції та одиничного морфізму: морфізм g є оберненим до f, якщо їх композиція є одиничним морфізмом. Насправді це не одна, а дві умови, оскільки є два способи композиції пари морфізмів:
Композиція g∘f має бути морфізмом з i1 до i1. Але i1 є початковим об'єктом, так що існує рівно один морфізм з i1 в i1 і оскільки початок і кінець стрілки збігаються, ця вакансія вже зайнята одиничним морфізмом. Отже, вони мають збігатися: морфізм g∘f є поодиноким. Аналогічно морфізм f∘g також збігається з одиничним, оскільки може бути лише один морфізм з i2 до i2. Таким чином, f і g взаємно зворотні, а два початкові об'єкти ізоморфні.
Зауважимо, що наш доказ єдиності початкового об'єкта з точністю до ізоморфізму суттєво використав єдиність морфізму з ініціального об'єкта до самого себе. Однак чи важливо те, що морфізм f і g також єдині? Справа в тому, що насправді ми довели суворіше твердження: початковий об'єкт єдиний з точністю до єдиного ізоморфізму. Взагалі, між двома об'єктами може бути більше одного ізоморфізму, але не в цьому випадку. "Єдиність з точністю до єдиного ізоморфізму" - важлива властивість всіх універсальних конструкцій.
Твори
З декартовим твором пов'язані дві функції(проектори), що діють з множини-твору у відповідну множину-множник. У Haskell ці функції називаються fst та snd і вибирають перший та другий елементи пари відповідно:
Тут функції визначені за допомогою зіставлення аргументу зі зразком: зразок відповідає будь-якій парі (x, y) і виділяє її компоненти змінні x і y.
Ці визначення можна спростити за допомогою прочерків:
У C++ скористаємося шаблонними функціями, наприклад:
Наприклад візьмемо як множників два типи, саме Int і Bool , і розглянемо вибірку кандидатів у тому твір.
Ось перший з них: Int. Чи може Int розглядатися як кандидат у твір Int та Bool? Так, може, ось відповідні проектори:
Виглядає підозріло, але цілком відповідає шаблону.
Ось ще кандидат: (Int, Int, Bool). Це кортеж із трьох елементів. Ось відповідна пара проектують морфізмів (ми знову використовуємо зіставлення зі зразком):
Уважний читач міг помітити, що перший кандидат занадто малий - він покриває тільки Int-компоненту твору, а другий занадто великий, тому що включає явно фіктивну Int-компоненту.
Ми поки що розглянули лише першу складову універсальної конструкції — шаблон, але нічого не сказали про другу — ранжування. Нам потрібен спосіб, що дозволяє порівняти двох кандидатів, що відповідають шаблону, а саме об'єкт c з проекторами p і q та об'єкт c' з проекторами p' та q'. Хотілося б покласти, що c краще c', якщо існує морфізм m з c' c, але це занадто слабка умова. Потрібно ще й зажадати, щоб проектори p і q були кращими (універсальнішими), ніж p' і q'. Це означає, що p' і q' можуть бути відновлені p і q за допомогою m:
Фахівець з теорії чисел сказав би, що m є дільником (фактором) p' та q'. Уявіть собі натуральні числа замість морфізмів та множення замість композиції: тоді m виявиться спільним дільником p' та q'. Далі у подібних ситуаціях ми говоритимемо, що m факторизує p' і q'.
Для тренування інтуїції покажемо, що пара (Int, Bool) з двома канонічними проекторами fst і snd безперечно краще, ніж розглянуті вище кандидати.
Відображення m для першого кандидата має вигляд:
Дійсно, обидва проектори p і q можуть бути відновлені як:
Морфізм m для другого прикладу також визначений єдиним чином:
Ми показали, що (Int, Bool) краще за обох кандидатів. Покажемо, що протилежне не так. Чи можна знайти деякий морфізм m', який дозволить відновити fst і snd p і q?
У першому прикладі q завжди повертає True, проте в той же час існують пари, в яких другим компонентом є False. Тож відновити snd по q не можна.
У другому прикладі справи інакше: у нас достатньо інформації після p і q, щоб відновити fst і snd, проте морфізм m', що факторизує, визначений неоднозначно. Дійсно, оскільки і p , і q ігнорують другий елемент кортежу, морфізм m' може помістити туди що завгодно:
Підсумовуючи сказане вище, для даного типу c з проекторами p і q існує єдиний морфізм m з c в декартове твір (a, b), який факторизує p і q. Насправді m просто комбінує їх у пару:
Твор об'єктів a і b — це такий обладнаний двома проекторами об'єкт c, що для будь-якого іншого оснащеного проекторами об'єкта c' існує єдиний морфізм m з c' в c, що факторизує ці проектори.
Функція (вищогопорядку), яка будує факторизуючий морфізм за двома проекторами, іноді називається факторизатором. У нашому випадку вона має вигляд:
Котвори
Нам також слід звернути порядок ранжування: тепер об'єкт c буде вважатися кращим за об'єкт c', оснащений вкладеннями i' і j', якщо існує морфізм m з c в c', що факторизує вкладення:
Котвір об'єктів a та b — це такий оснащений двома вкладеннями об'єкт c, що для будь-якого іншого оснащеного вкладеннями об'єкта c' існує єдиний морфізм m з c в c', що факторизує ці вкладення.
Для програміста копії — це позначене поєднання двох типів. C++ підтримує непомічені об'єднання; Завдання відстеження, який із членів об'єднання валідний, лежить на плечах програміста. Щоб створити позначене об'єднання, потрібно визначити мітку — перерахування — і скомбінувати її з об'єднанням. Наприклад, позначене об'єднання int і char const може виглядати так:
Два вкладення може бути реалізовані або як конструктори, або як функції. Наприклад, ось перше вкладення у вигляді функції PhoneNum:
Ця функція вкладає int у Contact.
Позначене об'єднання називається variant , узагальнена реалізація якого є у бібліотеці boost ( boost::variant ).
У Haskell можна скласти позначене об'єднання будь-яких типів даних, розділяючи конструктори вертикальною рисою. Розглянутий вище Contact записується так:
На відміну від канонічної реалізації твору, вбудованої в синтаксис Haskell як примітивна пара, канонічна реалізація копії є не спеціальною мовною конструкцією, а рядовим типом даних Either зі стандартної бібліотеки:
Цей тип даних параметризований двоматипами a і b і має два конструктори: Left, що приймає тип a, і Right, що приймає тип b.
За аналогією з факторизатором для твору можна визначити і факторизатор для копії. Для даного кандидата в котвори у вигляді типу c з двома вкладеннями i і j побудуємо факторизуючий морфізм:
Асиметрія
Зауважимо, що незважаючи на те, що з порожньої множини виходить єдина стрілка в будь-яке інше безліч (функція absurd), немає жодного морфізму, що входить до нього. Сінглтон (множина з одного елемента) має не тільки єдину стрілку, що входить до нього з будь-якої множини, але і вихідні стрілки в кожну непорожню множину. Як ми бачили раніше, ці стрілки, що виходять з термінального об'єкта, відіграють важливу роль у виборі елементів інших множин (у порожній безлічі немає елементів, так що нічого і вибирати).
Взаємини з синглтоном - це те, чим відрізняється твір від копії. Розглянемо синглтон, що складається з одного елемента () як об'єкт, що відповідає шаблону твору. Оснастимо його двома проекторами: нехай p і q - функції із синглтона в кожну з компонентів твору. Обидві вони вибирають фіксовані елементи у відповідних множинах. Оскільки твір є універсальним, існує (єдиний) морфізм m з синглтона в твір. Цей морфізм вибирає елемент із безлічі твору, тобто фіксовану пару, і факторизує проектори:
Якщо підставити на ці рівняння єдиний елемент синглтона () , то отримаємо:
Оскільки m () - це елемент твору, що вибирається морфізмом m, ці рівняння означають, що елемент p (), що вибирається проектором p з першого множини, є першою компонентою пари, що вибирається m. Аналогічно, q() дорівнює другій компоненті. Цеповністю узгоджується з трактуванням елементів множини-твору як пар елементів з множин-множників.
Функція повинна бути визначена для кожного елемента своєї області визначення (у програмуванні така функція називається тотальною), але не повинна покривати область значень цілком. Наприклад, функції синглтона потрапляють всього в один елемент з області значень. Виродженим випадком є функції з порожньої множини - вони взагалі не набувають жодного з значень. У протилежній ситуації, коли значення функції покривають усі доступні значення, функція називається сюр'єктивною.
Ще одним джерелом асиметрії є те, що функція може склеїти багато елементів з області визначення один елемент з області значень. Наприклад, функції синглтон склеюють всі елементи вихідної множини в один () . Вище розглядалася поліморфна функція unit. Якщо під впливом функції образи всіх елементів різні, то функція називається инъективной.
Вправи
- Покажіть, що термінальний об'єкт є єдиним з точністю до єдиного ізоморфізму.
- Що є твір у частково впорядкованому множині? Підказка: скористайтесь універсальною конструкцією.
- Що являє собою копію в частково впорядкованому множині?
- Реалізуйте аналог Either з Haskell вашою улюбленою мовою програмування (але не Haskell).
- Покажіть, що Either є більш відповідним копію, ніж int, оснащений двома вкладеннями:
Підказка: визначте функцію
яка факторизує i та j.