4.2: Збагачені профунктори
- Page ID
- 66239
У цьому розділі ми розберемося, як проблеми ко-дизайну формують категорію. По дорозі ми розробимо деякі абстрактні машини, які дозволять нам замінити попереднє замовлення дизайнерських просторів іншими збагаченими категоріями.
Техніко-економічні зв'язки як Bool -profunctors
Теорія спільного проектування базується на попередніх замовленнях: кожен ресурс, наприклад, швидкість, крутний момент або $ структурується як попереднє замовлення. Порядок x ≤ y представляє доступність x заданого y, тобто коли у вас є y, у вас також є x. Наприклад, у нашому попередньому порядку потужності, якщо 5W ≤ 10W, це означає, що всякий раз, коли нам надається 10W, ми неявно також маємо 5 Вт. Вище ми називали це порядком від менш корисного до більш корисного: якщо x завжди доступний за заданим y, то x менш корисний, ніж у.
Ми знаємо з розділу 2.3.2, що попередній порядок X можна розглядати як категорію Bool. За даними x, y\(\in\) X, ми маємо X (x, y)\(\in\)\(\mathbb{B}\); це значення відповідає твердженню «x доступний за заданим y», позначаючи його або істинним, або хибним.
Наша мета полягає в тому, щоб розглядати відносини техніко-економічних можливостей як Bool -profunctors, які є окремим випадком чогось збагаченого profunctors. Дійсно, сподіваємося, що ця глава дасть вам деяку інтуїцію для профункторів, що випливають з таблиці
Оскільки збагачені профунктори трохи абстрактні, ми спочатку конкретно обговорюємо Bool -profunctors як відносини доцільності.
Нагадаємо, що якщо X = (X, ≤) є попереднім порядком, то його протилежний X\(^{op}\) = (X, ≥) має x ≥ y iff y ≤ x.
Нехай X = (X, ≤ X) і Y = (Y, ≤ Y) будуть попередніми замовленнями. Співвідношення доцільності для X заданого Y - це монотонна карта.
Φ: X\(^{op}\) × Y → бул. (4.3)
Позначимо це Φ: X\(\rightarrow\) Y.
Задано x\(\in\) X і y\(\in\) Y, якщо Φ (x, y) = істинно, ми говоримо, що x можна отримати за заданим y.
Як згадувалося у вступі, вимога, що Φ є монотонним, говорить про те, що якщо \(_{X}\)x ′ ≤ x і \(_{Y}\)y ≤ y ′ то Φ (x, y) ≤\(_{Bool}\) Φ (x ′, y ′) . Іншими словами, якщо x можна отримати за заданим y, а якщо x ′ доступний задано x, то x ′ можна отримати за заданим y. І якщо крім того y доступний з урахуванням y ′, то x ′ також можна отримати з урахуванням y ′.
Вправа 4.4.
Припустимо, у нас є попередні замовлення
1. Намалюйте діаграму Хассе для попереднього порядку X\(^{op}\) × Y
2. Запишіть профунктор\(\bigwedge\): X\(\rightarrow\) Y і, читаючи\(\bigwedge\) (x, y) = true, як «моя тітка може пояснити x дано y», дати інтерпретацію того факту, що преобраз істинного утворює верхній набір у X\(^{op}\) × Y ♦
Щоб узагальнити поняття співвідношення доцільності, ми повинні зауважити, що симетричний моноїдальний попередній порядок Бул має більше структури, ніж просто структура симетричного моноїдального попереднього порядку: як згадувалося у Вправі 2.93, Бул є кванталом. Це означає\(\bigvee\), що у нього є всі приєднання та операція закриття, яку ми напишемо ⇒:\(\mathbb{B}\) ×\(\mathbb{B}\) →\(\mathbb{B}\). За визначенням ця операція задовольняє властивість, яке для всіх b, c, d\(\in\)\(\mathbb{B}\) має
b\(\bigwedge\) c ≤ d iff b ≤ (c ⇒ d). (4,5)
Операція ⇒ наведена наступною таблицею:
Вправа 4.7.
Покажіть, що ⇒, як визначено в Eq. (4.6), дійсно задовольняє Eq. (4.5) . ♦
На абстрактному рівні це той факт, що Бул - це кванта, яка змушує все в цьому розділі працювати; будь-який інший (unital commutative) quantale також визначає спосіб інтерпретації діаграм спільного проектування. Наприклад, ми могли б використовувати квантову вартість, яка б описувала не те, чи доступний x задано y, а вартість отримання x заданої y; див. Приклад 2.37 та Визначення 2.46.
V -профунктори
Тепер ми готові переробити Eq. (4.3) в абстрактному вираженні. Згадайте поняття збагаченого продукту (визначення 2.74), збагаченого функтора (визначення 2.69) та кванталі (визначення 2.79).
Нехай V = (V, ≤, I,) - це (одинична комутативна) кількісна,\(^{1}\) а X і Y - V-категоріями.
V -профунктор від X до Y, позначається Φ: X Y, є V-функтором
Φ: X\(^{op}\) × Y → V.
Зауважте, що V-функтор повинен мати V-категорії для домену та кодомену, тому тут ми розглядаємо V як збагачений сам по собі; див. Зауваження 2.89.
Вправа 4.9.
Показати, що V-профунктор (визначення 4.8) такий же, як функція Φ: Ob (X) × Ob (Y) → V такий, що для будь-яких x, x ′\(\in\) X і y, y ′ \(\in\)Y наступна нерівність тримається в V:
X (x ′, x) Φ (x, y) Y (у, y ′) ≤ Φ (х ′, у ′) . ♦
Вправа 4.10.
Чи правда, що Bool -profunctor, як і в Definition 4.8, точно такий же, як і техніко-економічне відношення, як і у Визначенні 4.2, як тільки ви відклеїте всі жаргони? Або є якась тонка різниця? ♦
Ми знаємо, що визначення 4.8 є досить абстрактним. Але не бійтеся, ми проведемо вас через це на фотографіях.
Давайте обговоримо Defi-nition 4.8 у випадку V = Bool. Один із способів уявити Bool -profunctor Φ: X → Y - це будівництво мостів між двома містами. Нагадаємо, що попередній порядок (категорія Bool) може бути намальований за допомогою діаграми Хассе. Ми будемо думати про попередній порядок як місто, і кожна вершина в ньому як якась точка інтересу. Стрілка A → B на діаграмі Хассе означає, що існує спосіб дістатися з точки А в точку Б у місті. Так що ж таке профунктор?
Профунктор - це просто купа мостів, що з'єднують точки в одному місті з точками в іншому. Давайте подивимося на конкретний приклад. Ось картина бул-профунктора Φ: X → Y:
Обидва X і Y є попередніми порядками, наприклад, з W ≤ N і b ≤ a. З мостами, що надходять від профунктора синім кольором, тепер можна використовувати обидва шляхи всередині міст і мости, щоб дістатися від точок у місті X до точок у місті Y. Наприклад, так як є шлях від N до e і E до a, то маємо Φ (N, e) = істинно і Φ (E, a) = істинно. З іншого боку, оскільки шляху від W до d немає, ми маємо Φ (W, d) = false.
Насправді, можна поставити коробку навколо всієї цієї картинки і побачити нове попереднє замовлення з W ≤ N ≤ c ≤ a тощо Це називається колажем Φ; ми розглянемо це докладніше пізніше; див. Визначення 4.42.
Вправа 4.12.
Ми можемо висловити Φ як матрицю, де (m, n) -й запис - це значення Φ (m, n)\(\in\)\(\mathbb{B}\). Заповніть Bool -матрицю:
Ми будемо називати це матрицею здійсненності Φ.
Розглянемо тепер Cost -профунктори. Знову ми можемо розглядати їх як мости, але цього разу наші мости позначені їх довжиною. Нагадаємо з визначення 2.53 та Eq. (2.56), що категорії витрат - це метричні простори Ловера, і їх можна зобразити за допомогою зважених графіків. Ми будемо думати про такий зважений графік як діаграму відстаней між точками в місті, і створимо Cost -profunctor, будуючи кілька мостів між містами.
Ось зображення вартості -profunctor Φ: X Y:
Відстань від точки x у місті X до точки y у місті Y задається найкоротшим шляхом, який проходить від x до X, потім через один з мостів, а потім через Y до місця призначення y. Так, наприклад
Φ (В, х) = 11, Φ (А, з) = 20, Φ (С, у) = 17.
Вправа 4.15.
Заповніть матрицю «Вартість»:
Зауваження 4.16 (Обчислення профункторів за допомогою множення матриць). Ми можемо дати алгоритм для обчислення вищевказаної матриці відстані за допомогою множення матриці. По-перше, як і в еквалайзері (2.59), ми можемо почати з позначених графіків у Eq. (4.14) і зчитувати матриці міток стрілок для X, Y та Φ:
Нагадаємо з розділу 2.5.3, що матрицю відстаней d Y для Cost -категорії X можна отримати, взявши потужність матриці M X з найменшими записами, і аналогічно для Y.
Матриця відстаней для профунктора Φ буде дорівнює d\(_{X}\) ∗ M\(_{Φ}\) ∗ d\(_{Y}\).
Насправді, оскільки X має чотири елементи, а Y - три, ми також це знаємо\(\Phi=M_{X}^{3} * M_{\Phi} * M_{Y}^{2}\).
Вправа 4.17.
Обчисліть\(\Phi=M_{X}^{3} * M_{\Phi} * M_{Y}^{2}\), не забуваючи робити множення матриці за (min, +) -формулою множення матриці в кванті Вартість; див. Ур. (2.101).
Ваша відповідь повинна погодитися з тим, що ви отримали у Вправі 4.15; чи це? ♦
Повернутися до діаграм спільного проектування
Кожна коробка в діаграмі спільного проектування має ліву і праву сторони, які, в свою чергу, складаються з колекції портів, які, в свою чергу, позначені попередніми замовленнями. Наприклад, розглянемо коробку шасі нижче:
Його ліва сторона складається з двох портів, одного для навантаження та одного для швидкості, і це функціональність, яку виробляє шасі. Його права сторона складається з трьох портів, один для крутного моменту, один для швидкості, а один для $, і це ресурси, які вимагає шасі. Кожен з цих ресурсів повинен бути прийнятий як попереднє замовлення. Наприклад, load може бути попереднім порядком ([0, ∞], ≤), де елемент x\(\in\) [0, ∞] представляє ідею «Я можу обробляти будь-яке навантаження до x.», тоді як $ може бути попереднім замовленням з двох елементів {up_to_$100, more_than_$100}, де перший елемент цього набору менше другого.
Потім ми множимо - тобто ми беремо попереднє замовлення товару з усіх попередніх замовлень зліва, і аналогічно для тих, що знаходяться праворуч. Потім поле представляє співвідношення доцільності між результатами. Наприклад, коробка шасі вище представляє співвідношення доцільності
Шасі: (навантаження × швидкість) → (крутний момент × швидкість × $)
Давайте пройдемо через це трохи більш конкретно. Розглянемо дизайнерську проблему зйомок фільму, де ви повинні поставити тон і цінність розваг проти вартості.
Співвідношення доцільності, що описує цю ситуацію, деталізує, який тон та цінність розваг можна отримати за кожною вартістю; як таке, воно описується співвідношенням доцільності Φ: (T × E) → $. Представляємо це коробкою
де T, E та $ - попередні замовлення, намальовані нижче:
Можливе співвідношення доцільності потім описується профунктором.
Це говорить, наприклад, про те, що добродушний, але нудний фільм коштує $500K для виробництва (звичайно, продюсери також були б раді отримати $1M).
Для деталізації кожну стрілку на наведеній вище діаграмі слід інтерпретувати як кажучи: «Я можу надати джерело з урахуванням мети». Наприклад, є стрілки свідками кожного з «Я можу забезпечити $500K з урахуванням $1M», «Я можу забезпечити добродушний, але нудний фільм з урахуванням $500K», і «Я можу забезпечити середній і нудний фільм з урахуванням добродушного, але нудного фільму». Більше того, цей зв'язок є перехідним, тому шлях від (середнього, нудного) до $1M вказує також на те, що «я можу забезпечити середній і нудний фільм з урахуванням $1M».
Зверніть увагу на схожість і відмінність з мостовою інтерпретацією профункторів у прикладі 4.11: стрілки все ще вказують на можливість переміщення між джерелом і ціллю, але в цій спільній проектуванні керованої інтерпретації ми розуміємо їх як вказують на те, що можна дістатися до джерела від мішені.
На наведеній вище схемі вузол (g/n, смішний) не має пунктирною синьої стрілки, що виходить з нього. Чи дійсно це? Якщо так, то що це означає? ♦