Переклад Чудо монад

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

Введення в монади

Контролюючи складність

Композиція – це ключ до контролю складності програмного забезпечення. У "The Structure and Interpretation of Computer Programs" Абельсон і Зусман (Abelson and Sussman) стверджують, що композиція красиво висловлює складні системи простими патернами.

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

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

Наприклад, замість того, щоб застосовуватиgдо значенняxі потім застосовуватиfдо результату, можна з'єднатиfзgі потім застосувати результат до значенняx. Ключова відмінність в узагальненні залежності міжfтаg.

Для цієї функціїIdentity, композиція функцій має підпорядковуватися трьом законам:

1. Ліва тотожність>
2. Права тотожністьf.Compose( >
3. Асоціативністьf.Compose(g.Compose(h)) = (f.Compose(g)).Compose(h)

Найчастіше просто значень недостатньо. І їх розширюють типи, що конструюються. Тип IEnumerable представляє ліниво обчислюваний список значень типу T . Тип Nullable представляє значення типу T, яке може бути відсутнім. Тип Func, Answer> представляє функцію, яка повертає Answer (відповідь), що дається продовженням, яке приймає T та повертає Answer .

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

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

Вхідний та вихідний типи визначають сигнатуруфункції Bind. Отже, Bind приймає розширене значення типу M та функцію U -> M і повертає розширене значення типу M .

Реалізація Bind залежить від механіки розширених значень типу M. Кожен розширений тип вимагатиме своєї реалізації функції Bind.

На додаток до Bind визначимо функцію, яка набуває нерозширеного значення і розширює його. Назвемо цю функцію Unit.

Разом, розширений тип M , функція Bind та функція Unit уможливлюють композицію функцій з розширеними значеннями.

Зустрічайте монади

Вуаля, ми "винайшли" монади.

Монади – це трійка з типу, функції Unit та функції Bind. Крім того, щоб бути монадою, трійка повинна дотримуватися трьох законів:

1. Ліва тотожністьBind(Unit(e), k) = k(e)
2. Права тотожністьBind(m, Unit) = m
3. АсоціативністьBind(m, x => Bind(k(x), y => h(y)) = Bind(Bind(m, x => k(x)), y = >h(y))

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

Щоб визначити деяку монаду необхідно визначити вищеописану трійку і задати механіку розширених значень.

Монада Identity

Найпростіша монада – це монада Identity (тотожна монада). Тип є обгорткою навколо значення.

Функція Unit приймає значення та повертає новий екземпляр Identity, який містить це значення.

Функція Bind приймає екземпляр Identity , отримує значення і викликає делегат k з отриманим значенням. Результатом є новий екземпляр Identity.

Розглянемо просту програму, яка створює дві Identity -обгортки таздійснює операції над оберненими значеннями. Спочатку x зв'язується зі значенням в оболонці, що зберігає п'ять. Потім y зв'язується зі значенням оболонці, що зберігає число шість. Наприкінці x та y складаються. Результатом стає екземпляр Identity, що обертає число одинадцять.

Це працює, але виглядає дуже незграбно. Було б добре мати синтаксис до роботи з монадами. На щастя він у нас є.

C# 3.0 вводить розширення для запитів, які є замаскованим розширенням для монад. Ми можемо переписати тотожну (identity) монаду, використовуючи LINQ. Напевно, це можна назвати LINM (Language INtegrated Monads).

Перейменуємо метод Unit у ToIdentity, а Bind у SelectMany. Потім зробимо обох методів-розширень (extensions methods).

Зміни зачіпають і код, що викликає.

Аналогічні методи є частиною стандартних операторів запитів, визначених LINQ. Однак стандартні оператори запитів також включають і трохи інші версії SelectMany з міркувань продуктивності. Вони комбінують Bind з Unit, щоб не доводилося створювати довгі ланцюжки включених один до одного лямбд. Сигнатура така сама, за винятком додаткового аргументу — делегата, який приймає два аргументи і повертає значення. Делегат поєднує два значення разом. Ця версія SelectMany пов'язує x з оберненим значенням, застосовує k x , пов'язує y з результатом і застосовує об'єднуючу функцію s x і y . Результуюче значення обертається та повертається.

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

Боку, що викликає, тепер не потрібно включати лямбди один в одного.

З новим визначенням SelectMany програмісти можуть використовуватиC#'овий синтаксис запитів. from -запис пов'язує надану змінну зі значенням, оберненим виразом праворуч. Це дозволяє наступним виразам використовувати обернуті значення, обходячись без виклику SelectMany .

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

Монада Maybe

Монада Identity є прикладом монадичного контейнерного типу, в якому монада Identity обертає значення. Якщо ми змінимо визначення таким чином, щоб можна було містити як значення, так і відсутність значення, ми отримаємо монаду Maybe (монаду обчислень з відсутніми значеннями).

І знову нам потрібне визначення типу. Тип Maybe аналогічний типу Identity, але додає властивість, чи немає значення. Він також має зумовлений екземпляр Nothing , що представляє всі екземпляри, позбавлені значень.

Unit -функція набуває значення і конструює екземпляр Maybe, який обертає значення.

Bind -функція приймає екземпляр Maybe і якщо в нього є значення, застосовує делегат до значення, що зберігається. Інакше вона повертає Nothing .

Програміст може використовувати синтаксис розширень для роботи з монадою Maybe. Наприклад, створити екземпляр Maybe , що містить п'ять і додати до нього Nothing .

Результат - "нічого" (Nothing). Ми розповсюдили null-значення nullable-типу, не використовуючи явну підтримку мови.

Монада List

Інший важливий контейнерний тип - це обліковий (list) тип.Фактично спискова монада – серце LINQ. Тип IEnumerable означає ліниво обчислюваний список.

Unit -функція приймає значення і повертає список, що містить лише це значення.

Bind-функція приймає IEnumerable і делегат, який приймає T і повертає IEnumerable, і повертає IEnumerable.

Тепер, програміст може писати знайомі висловлювання запитів з IEnumerable.

Пам'ятайте, саме ця монада містить магію.

Монада Continuation

Монада Continuation (монада продовження) відповідає на питання, яке я розмістив наприкінці свого попереднього посту: як можна було б писати CPS-код приємнішим шляхом? (Continuation-Passing Style, тобто стиль передачі продовження, про нього можна детально прочитати в перекладі блогу Еріка Ліпперта (або в оригіналі) - прим. ред.)

Тип монади продовження K - це делегат, при отриманні продовження, що приймає аргумент і повертає відповідь, повертає відповідь.

Тип K фундаментально відрізняється від типів Identity, Maybe та IEnumerable. Всі вони є контейнерні типи і дозволяють обчисленням визначатися в термінах значень, а не контейнерів, але монада Continuation нічого не містить. Вірніше, вона поєднує разом продовження, написані користувачем.

Щоб це було монадою, необхідна Unit -функція, що приймає T і повертає K деякого типу відповіді.

Що ж вона має робити? Якщо вам важко відповідати, подивіться на типи. Метод приймає T та повертає функцію, яка приймає функцію T -> Answer, і повертає Answer. Отже, метод повинен повернути функцію та єдиним аргументом цієї функції має бути функція T -> Answer. Назвемо цей аргумент c.

Тіло лямбди має повертати значення типу Answer. Доступнізначення типу Func та T . Застосуємо c до значення та отримаємо результат типу Answer.

Щоб це було монадою, Bind-функція повинна приймати K та функцію T -> K та повертати K .

Але що щодо тіла? Результат має бути типу K, але як сформувати результат коректного типу?

Розгорнемо визначення K, щоб отримати якесь розуміння.

Застосовуючи k значення типу T ми повинні отримати значення типу K , але в нас не доступно ніякого значення типу T . Побудуємо значення, що повертається прямим конструюванням функції, що приймає функцію U -> Answer. Назвемо її аргумент c.

Тіло має бути типу Answer, тому що повертається тип Bind-функції - K. Напевно, m має бути використане функції T -> Answer. Результатом буде значення типу Answer.

Вираз усередині виклику m має бути типу Func. Оскільки тут немає такого типу, конструюватимемо функцію, створюючи лямбду з одним параметром - x типу T .

Тіло цієї лямбди має бути типу Answer. Значення типів T , Func та Func , Answer>> ще були використані. Застосуємо k x .

Отримуємо як результат значення типу Func, Answer> . Застосовуємо результат до c.

Монада продовження вивертає обчислення навиворіт. Можна використовувати синтаксис розширень для конструювання продовжень.

Сконструюємо обчислення, яке викликає продовження із числом сім. Передамо це обчислення іншому обчисленню, яке викликає продовження із числом шість. Передамо це продовження іншому обчисленню, яке викликає продовження з результатом додавання результатів перших двох продовжень. На завершення передамо продовження, яке замінює "1" на "a", в отриманий результат.

Монада продовження дає важку артилерію конструюванняпродовжень.

Монадична магія

Красива композиція розширених значень потребує монади. Монади Identity, Maybe та IEnumerable демонструють міць монад як контейнерних типів. Монада продовження K показує, як монади можуть легко висловлювати складні обчислення.

---