Категорії Клейсли

Композиція логування

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

Щось, що імперативний мовою, швидше за все, буде реалізовано за допомогою мутації деякого глобального стану, наприклад:
string logger;

bool negate(bool b) {
logger += "Not so! ";
return !b;
}

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

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

На щастя для нас, можна зробити цю функцію чистою. Потрібно просто передати лог в явному вигляді в функцію. Давайте зробимо це шляхом додавання рядка аргументу, і повернення пари з основного результату і рядка, що містить оновлений журнал:
pair<bool, string> negate(bool b, string logger) {
return make_pair(!b, logger + "Not so! ");
}

Ця функція чиста, вона не має жодних побічних ефектів, вона повертає однакову пару кожен раз, коли її викликають з однаковими аргументами, і її результати можна закешувати, якщо потрібно. Однак, враховуючи накопичувальний характер лода, вам доведеться закешувати всі можливі історії, які можуть призвести до даного викликом. Там буде окрема закешированная запис:
negate(true, "It was the best of times. ");

і
negate(true, "It was the worst of times. ");

і так далі.

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

Чи є спосіб зробити те ж саме менш нав'язливо? Чи є спосіб розділити проблеми? У цьому простому прикладі, основна мета функції negate — перетворити один Boolean в інший. Логування вдруге. Звичайно, повідомлення, яке логируется, є специфічним для функції, але агрегування повідомлень в один безперервний лог — окрема задача. Ми все ще хочемо, що функція повертала рядок, але ми хотіли б звільнити її від завдання створення лода. Ось компромісне рішення:
pair<bool, string> negate(bool b) {
return make_pair(!b "Not so! ");
}

Ідея в тому, що лог буде агрегуватися між викликами функції.

Щоб побачити, як це можна зробити, давайте перейдемо до трохи більш реалістичного наприклад. У нас є одна функція з рядка в рядок, яка перетворює малі літери у верхній регістр:
string toUpper(string s) {
string result;
int (*toupperp)(int) = &toupper; // toupper is overloaded
transform(begin(s), end(s), back_inserter(result), toupperp);
return result;
}

і інша, яка розбиває рядок на вектор рядків, розбиваючи її на прогалин:
vector<string> toWords(string s) {
return words(s);
}

Основна робота робиться в допоміжній функції words:
vector<string> words(string s) {
vector<string> result{""};
for (auto i = begin(s); i != end(s); ++i)
{
if (isspace(*i))
result.push_back("");
else
result.back() += *i;
}
return result;
}

Ми хочемо змінити функції toUpper і toWords так, щоб вони чіпляли рядок повідомлення поверх їхніх звичайних значень.
image
Ми збагатимо» повернення значень цих функцій. Давайте зробимо це в загальному вигляді шляхом визначення шаблону Writer, який інкапсулює пару, перший компонент якої — значення довільного типу А, а другий компонент — рядок:
template < class A>
using Writer = pair<A, string>;

Ось збагачені функції:
Writer<string> toUpper(string s) {
string result;
int (*toupperp)(int) = &toupper;
transform(begin(s), end(s), back_inserter(result), toupperp);
return make_pair(result, "toUpper ");
}

Writer<vector < string>> toWords(string s) {
return make_pair(words(s), "toWords ");
}

Ми хочемо скомпонувати ці функції в іншу збагачену функцію, яка зводить рядок у верхній регістр і розбиває її на слова, при цьому логируя ці дії. Ось як ми можемо це зробити:
Writer<vector < string>> process(string s) {
auto p1 = toUpper(s);
auto p2 = toWords(p1.first);
return make_pair(p2.first, p1.second + p2.second);
}

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

А тепер уявіть собі всю програму, написану в цьому стилі. Це кошмар повторюваного і схильного до помилок коду. Але ми програмісти. Ми знаємо, як боротися з повторюваним кодом: ми його абстрагуємо! Це, однак, не ваші звичайні абстракції: ми повинні абстрагувати саму композицію функцій. Але композиція — суть теорії категорій, тому перед тим, як писати код далі, давайте проаналізуємо цю проблему з категорной точки зору.

Категорія Writer

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

Наприклад, припустимо, що ми хочемо збагатити функцію isEven, яка перетворює int в bool. Ми перетворимо її в морфизм, який представлений збагаченої функцією. Важливо те, що цей морфизм досі вважається стрілкою між об'єктами int і bool, хоча прикрашена функція повертає пару:
pair<bool, string> isEven(int n) {
return make_pair(n % 2 == 0, "isEven ");
}

За законами категорії, ми повинні бути в змозі скомпонувати цей морфизм з іншим морфизмом, який йде з bool до чого завгодно. Зокрема, ми повинні бути в змозі поєднувати його з нашою попередньою функцією negate:
pair<bool, string> negate(bool b) {
return make_pair(!b "Not so! ");
}

Очевидно, що ми не можемо скласти ці два морфизма так само, як ми складаємо звичайні функції, з-за невідповідності входу/виходу. Їх композиція повинна виглядати приблизно так:
pair<bool, string> isOdd(int n) {
pair<bool, string> p1 = isEven(n);
pair<bool, string> p2 = negate(p1.first);
return make_pair(p2.first, p1.second + p2.second);
}

Отже, ось рецепт для композиції двох морфізмів у цій новій категорії, яку ми будуємо:
  1. Виконайте збагачену функцію, яка відповідає першому морфизму
  2. Вийміть перший компонент пари-результату і передайте його в збагачену функцію, відповідну другого морфизму
  3. З'єднайте другий компонент (рядок) першого результату і другий компонент (теж рядок) другого результату
  4. Поверніть нову пару, що об'єднує перший компонент кінцевого результату з конкатенированной рядком.
Якщо ми хочемо абстрагувати цю композицію у вигляді функції вищого порядку в C++, ми повинні використовувати шаблон, параметризований трьома типами, що відповідають трьом об'єктам у нашій категорії. Слід взяти дві збагачені функції, які компонуемы згідно з нашими правилами, і повернути третю збагачену функцію:
template < class A, class B, class C>
function<Writer<C>(A)> compose(function<Writer<B>(A)> m1, 
function<Writer<C>(B)> m2)
{
return [m1, m2](A x) {
auto p1 = m1(x);
auto p2 = m2(p1.first);
return make_pair(p2.first, p1.second + p2.second);
};
}

Тепер ми можемо повернутися до нашого прикладу і реалізувати композицію toUpper і toWords за допомогою цього шаблону:
Writer<vector < string>> process(string s) {
return compose<string, string, vector<string>>(toUpper, toWords)(s);
}

Тут все ще багато шуму з передачею типів шаблон compose. Цього можна уникнути, якщо у вас є С++14-сумісний компілятор, що підтримує узагальнені лямбда-функції з дедукцією повертається типу (спасибі Еріку Ниблеру за код):
auto const compose = [](auto m1, auto m2) {
return [m1, m2](auto x) {
auto p1 = m1(x);
auto p2 = m2(p1.first);
return make_pair(p2.first, p1.second + p2.second);
};
};

У цьому новому визначенні, реалізація process спрощується:
Writer<vector < string>> process(string s){
return compose(toUpper, toWords)(s);
}

Але ми ще не закінчили. Ми визначили композицію в нашій новій категорії, але які поодинокі морфизмы? Це не наші регулярні функції тотожності! Вони повинні бути морфизмами типу A назад в тип А, значить, вони збагачені функції виду:
Writer<A> identity(A);

Вони повинні вести себе як одиниці по відношенню до композиції. Якщо ви подивіться на наше визначення композиції, ви побачите, що тотожний морфизм, повинен передати свій аргумент без зміни, а тільки додати порожній рядок в лог:
template < class A>
Writer<A> identity(A x) {
return make_pair(x, "");
}

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

Проникливий читач може помітити, що можна легко узагальнити цю конструкцію на будь-моноїд, а не тільки рядка. Ми хотіли б використовувати mappend всередині compose і mempty всередині identity (на місці + і ""). Дійсно, немає ніяких підстав обмежувати себе логированием тільки рядків. Хороший письменник бібліотек повинен бути в змозі визначити необхідний мінімум обмежень, які необхідні бібліотеці для роботи — тут єдина вимога бібліотеки логування полягає в тому, що у лода є моноидальные властивості.

Writer на Haskell

Та ж конструкція на Haskell буде набагато більш лаконічна, і компілятор допоможе нам набагато більше. Давайте почнемо з визначення типу Writer:
type Writer a = (a, String)

Тут я просто визначаю псевдонім типу, еквівалент typedef (або using) в C++. Тип Writer параметризирован змінної типу і еквівалентний парі a String. Синтаксис для пар мінімальний: всього два імені в дужках, через кому.

Наші морфизмы — функції з довільного типу до певного типу Writer:
a -> Writer b

Ми оголосимо композицію як забавний инфиксный оператор, який іноді називають «риба»:
(>=>) :: (a -> Writer b) -> (b> Writer c) -> (a -> Writer c)

Це функція від двох аргументів, кожен з яких сам по собі функція, і вона повертає функцію. Перший аргумент має тип (a -> Writer b), другий (b -> Writer c) і результат (a -> Writer c).

Ось визначення цього инфиксного оператора — два аргументи m1 і m2, з'являються по обидві сторони від рибного символу:
m1 >=> m2 = \x -> 
let (y, s1) = m1 x
(z, s2) = m2 y
in (z, s1 ++ s2)

У результаті виходить лямбда функція одного аргументу x. Лямбда записується у вигляді риски — можна думати про неї, як про грецької букви λ з ампутованою ногою.

Слово let дозволяє оголосити допоміжні змінні. Тут результат виклику m1 сматчен з парою змінних (у, s1), а результат виклику m2 з аргументом y з першого патерну, буде сматчен з (z, s2).

В Haskell матчинг пар — звичайна заміна використанню геттеров, як ми це робили в С++. Крім цього є досить просте відповідність між двома реалізаціями.

Значення let вираження міститься після in: тут це пара, чий перший компонент z, а другий компонент — об'єднання двох рядків s1 ++ s2.

Я також визначу одиничний морфизм для нашої категорії, але з причин, які стануть зрозумілі значно пізніше, я буду називати його return.
return :: a -> a Writer
return x = (x, "")

Для повноти давайте напишемо Haskell версії, збагачених функцій upCase (прим. перекладача: малося на увазі toUpper з C++ прикладу, але функція з таким ім'ям вже є в стандартному модулі Prelude) і toWords:
upCase :: String -> Writer String
upCase s = (map toUpper s, "upCase ")

toWords :: String -> Writer [String]
toWords s = (words s, "toWords ")

Функція map відповідає функції transform в C++. Вона застосовує функцію на символах toUpper до рядку s. Допоміжна функція words визначена в стандартній бібліотеці Prelude.

Нарешті, композиція цих двох функцій будується з допомогою оператора риби:
process :: String -> Writer [String]
process = upCase >=> toWords

Категорії Клейсли

Ви, напевно, здогадалися, що я не придумав цю категорію на льоту. Це приклад так званої категорії Клейсли — категорії на основі монади. Ми поки не готові обговорювати монади, але я хотів показати, що вони можуть робити. Для наших обмежених цілей, категорія Клейсли має типи, як об'єкти. Морфизмы типу A, типу B — це функції, які йдуть від A до типу, отриманому з B з допомогою особливого збагачення. Кожна категорія Клейсли визначає свій власний спосіб композиції таких морфізмів, а також тотожні морфизмы по відношенню до цієї композиції. (Пізніше ми побачимо, що неточний термін «збагачення» відповідає поняттю эндофунктора в категорії.

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

Теорія категорій для програмістів: передмова
Категорія: суть композиції
Типи та функції
Категорії, великі і малі
Категорії Клейсли

Джерело: Хабрахабр

0 коментарів

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