Використання монад в С++. Частина 1: монада списку

Іноді програмісти на С++ просять навести приклад задачі, яка не може бути вирішена без використання монад. Почнемо з того, що це питання невірний сам по собі — це все одно, що питати, чи існує задача, яка не може бути вирішена без циклів. Очевидно, якщо у вашій мові є підтримка оператора goto, ви можете обійтися без використання операторів циклу. Що монади (і цикли) можуть зробити для вас, це спростити ваш код і допомогти краще його структурувати. Використання циклів перетворює спагетті-код в нормальний, так і використання монад може перетворити ваш код в імперативному стилі в декларативний. Ця трансформація може допомогти легше писати, розуміти, підтримувати і розширювати ваш код.

Ну і ось вам задачка, яка може попастися на співбесіді. Вона не зовсім тривіальна, можливо кілька підходів до вирішення і кращий з них не відразу очевидна — якраз те, над чим варто подумати.
Вам пропонується такий пазл:

s e n d
+ m o r e
---------
m o n e y


Кожна буква відповідає цифри від 0 до 9. Потрібно написати програму, яка підбере такі відповідності, щоб написана операція додавання була вірною. Перед тим, як продовжити читання статті — подумайте хвилинку, як би ви вирішили цю задачу?

Аналіз



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

Якщо ви спробуєте вирішити цю задачу за допомогою ручки і паперу, ви швидко знайдете кілька евристик. Приміром, відразу зрозуміло, що m 1, тому що немає двох таких чотиризначних чисел, які б при складанні дали б число більше 19998. Потім ви з'ясуєте, що s повинно бути дорівнює 8 або 9, тому що інакше ми не отримаємо перенесення розряду для отримання п'ятизначного числа і т. д. Маючи достатню кількість часу ви, можливо, напишіть експертну систему, з достатньо великою кількістю правил, здатну вирішити цю проблему (а може і інші подібні). До речі, згадка експертної системи може дати вам пару зайвих очок на співбесіді.

Є й інший підхід — варто відзначити, що завдання має досить невелику розмірність — ми працюємо з 4-5 значними цілими числами, яких не так багато. Интервьювер може попросити вас попросити кількість перестановок, які потрібно буде перебрати — їх 10!/(10-8)! = 1814400 штук. Зовсім небагато для сучасного комп'ютера. Таким чином, рішення задачі зводиться до генерації цих перестановок і перевірку їх на відповідність обмежень вихідної задачі.

Рішення «в лоб»



Класичний імперативний підхід відразу породжує код з 8-ю вкладеними циклами (у нас є 8 унікальних літер s, e, n, d, m, o, r, y). Вийде щось типу такого:

for (int s = 0; s < 10; ++s)
for (int e = 0; e < 10; ++e)
for (int n = 0; n < 10; ++n)
for (int d = 0; d < 10; ++d)
...
і так до останньої літери


І тут нам потрібно перевірити умову. Але не то умова суми, з вихідної завдання — насамперед нам потрібно перевірити, що всі цифри в нашій перестановці різні, а інакше в ній і сенсу немає.

e != s
n != s && n != e
d != s && d != e && d != n


і так далі, в останньому рядку буде 7 порівнянь, а всього їх буде 28 штук. І лише після цього можна скласти з цифр числа "send", "more" і перевірити, чи вийшло у суму "money".

Загалом-то, задача вирішена і интервьювер не зможе сказати, що невірно. Але хвилиночку — хіба ми не можемо придумати щось краще?

Розумне рішення

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

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

Проблема може бути сформульована як сукупність двох проблем меншого розміру. Одна з них стосується глибини, а друга — ширини пошуку рішення.

Давайте спочатку подивимося на проблему глибини. Уявімо собі завдання створення лише однієї підстановки чисел замість літер вихідного пазла. Це може бути описано як вибір 8 цифр зі списку 0, 1, ...9, по одній цифрі за раз. Як тільки цифра вибрана — ми прибираємо її зі списку. Ми не хочемо жорстко забивати список в наш код, так що ми зробимо його параметром нашого алгоритму. Зауважте, що з цим підходом алгоритм буде працювати навіть для списку з дублікатами або для списку, в якому для елементів не можуть бути визначені оператори порівняння та рівності (наприклад, список з std::future).

Тепер давайте розглянемо проблему ширини: нам потрібно повторити вищевказаний процес для всіх можливих перестановок. Це як раз те, що роблять 8 вкладених циклів у коді вище. Є одна проблемка: кожен крок по вибірці чергового елемента зі списку деструктивний — він змінює список. Це відома проблема при переборі простору рішень та її стандартне рішення — відкат (backtracking). Як тільки ви обробили певного кандидата, ви ставите елемент назад в список і пробуєте наступний. Це означає, що вам потрібно відстежувати свій поточний стан, або неявно, зберігаючи його в стеку викликів функції, або явно — в деякій структурі даних.

Секундочку! Хіба ми не зібралися говорити про функціональному програмуванні? Так до чого ж всі ці розмови про модифікаціях і стані? Ну, а хто ж сказав, що у нас не може бути стану у функціональному програмуванні? Програмісти на функціональних мовах використовували монаду стану ще з часів, коли по Землі ходили динозаври. І модифікації — не проблема, якщо ви використовуєте персистентные структури даних. Так що пристебніть ремені і приведіть спинку крісла у вертикальне положення, ми злітаємо.

Монада списку



Ми почнемо з невеликої відсилання до квантової механіки. Як ви можете пам'ятати зі школи, квантові процеси не детерминистичны. Ви можете виконати один і той же експеримент кілька разів і отримати різні результати в кожному разі. Є дуже цікава точка зору на квантову механіку, звана "Многомировой інтерпретацією", в якій кожен експеримент породжує кілька альтернативних історичних ліній, у кожній з яких він дає свій результат, а ми просто потрапляємо в одну з цих «всесвітів» і спостерігаємо один конкретний (невідомий заздалегідь) результат експерименту.

Ми використовуємо той же підхід до вирішення нашого пазла. Ми створимо альтернативні всесвіти» для кожної перестановки цифр, що відповідає нашим буквах. Таким чином, ми почнемо з 10 всесвітів для літери s: у першій вона буде мати значення 0, у другій — 1 і т. д. Далі кожну з цих всесвітів ми розділимо ще на 10 за буквою e і т. д. Більшість з цих всесвітів не будуть задовольняти наші умови, так що ми будемо змушені їх знищити. Такий простий підхід до знищення всесвітів може здатися марнотратним і ресурсоємним, але у функціональному програмуванні це не проблема: швиденько створили альтернативну реальність і так само швидко знищили. Так відбувається тому, що нові всесвіти не так вже відрізняються від тих, на базі яких вони були породжені і вони можуть використовувати більшість даних спільно зі своїми «батьками». Це і є ідея персистентних структур даних. У нас є незмінна структура даних, яка може породити нову шляхом клонування. Нова структура даних поділяє більшість даних з батьком, крім невеликої «дельти». Ми будемо використовувати персистентные списки, описані ось в цьому пості.

Як тільки ви усвідомлюєте цей підхід з «численними всесвітами», реалізація стає досить простий. По-перше, нам потрібна функція, яка буде створювати нові всесвіти. Оскільки ми домовилися, що вона повинна бути «дешевої», генерувати ми будемо тільки ті частини, які будуть відрізнятися. Чим відрізняються всі породжені по змінної s всесвіти? Тільки значенням змінної s. Всього є 10 таких всесвітів, відповідних значень s від 0 до 9 (той факт, що s не може бути дорівнює 0 ми розглянемо пізніше). Таким чином, все, що нам потрібно, це функція, яка генерує список з 10 цифр. Ну і ось вони — наші 10 всесвітів у всій своїй чистій первозданній красі.

І ось ми опиняємося в одній з цих альтернативної всесвітів (взагалі-то у всіх відразу, але конкретно зараз розглядаємо потрапляння в одну з них). Треба якось жити далі. У функціональному програмуванні вся ваша залишилася життя — це виклик функції, яка називається "продовження". Я знаю, що це звучить як страшний спрощення. Всі ваші дії, емоції і надії зводяться до всього-лише викликом однієї функції. Ну, давайте думати, що «продовження» описує лише якусь частину вашого життя в цьому всесвіті, її «обчислювальну» складову, а все інше відбувається десь окремо.

Отже, до чого ж зводиться наше життя в цьому всесвіті і що вона породжує? Входом є сама всесвіт, в якій ми знаходимося, зокрема для нашого прикладу — одне із значень s, яке ми обрали при породженні цієї всесвіту. Але оскільки ми живемо в просторі квантових експериментів, на виході у нас буде набір нових всесвітів. Таким чином «продовження» отримує на вхід число, а породжує список. Це не обов'язково список чисел, а список чогось, що описує відмінності породжених всесвітів один від одного.

Ну і в чому ж сенс цього нового підходу? Це прив'язка вибору всесвіту до «продовження». Це те місце, де і відбуваються всі дії. Ця прив'язка, знову таки, може бути виражена у вигляді функції. Це функція, яка отримує на вхід список всесвітів і «продовження», яке породжує новий список всесвітів (більшого розміру). Ми назвемо цю функцію for_each і ми постараємося написати її настільки узагальнено, наскільки це можливо. Ми нічого не будемо припускати про типи переданих або породжуваних всесвітів. Ми також зробимо тип «продовження» параметром шаблону і визначимо тип значення, що повертається за допомогою auto та decltype:

template < class A, class F>
auto for_each(List<A> lst, F k) -> decltype(k(lst.front()))
{
using B = decltype(k(lst.front()).front());

// обмеження, що накладаються на тип F повинні були б бути виражені за допомогою концептів, 
// якщо б їх нарешті включили в стандарт мови С++
static_assert(std::is_convertible<
F, std::function<List<B>(A)>>::value,
"for_each requires a type function List<B>(A)");

List<List<B>> lstLst = fmap(k, lst);
return concatAll(lstLst);
}


Функція fmap аналогічна стандартної std::transform — вона застосовує «продовження» k до кожного елемента lst. Оскільки k саме по собі повертає список, результатом буде список списків, lstLst. Функція concatAll об'єднує всі елементи всіх цих списків в один великий список.

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

template < class A>
List<A> yield(A a)
{
return List<A> (a);
}


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

Пізніше я переименую ці функції у mbind та mreturn, оскільки вони визначають монаду в загальному, а не тільки монаду списку.

Імена на зразок for_each та yield мають досить «імперативне» звучання. Це, звичайно, тому, що у функціональному програмуванні монади в деякому сенсі слова виконують роль імперативного коду. Але ні for_each ні yield не є структурами даних — вони є функціями. Точніше, for_each, яка звучить і працює як цикл, є функцією вищого порядку, як і fmap, яка використовується в її реалізації. Звичайно, на якомусь рівні код стане імперативним — той же fmap може бути написаний рекурсивно або з використання циклу, але на верхньому рівні ми маємо лише декларації функцій. Ну і ось воно — декларативне програмування!

Є суттєва відмінність між циклом і функцією, на зразок for_each: for_each приймає в якості аргументу весь список, в той час як цикл може генерувати необхідні значення (у нашому випадку цілі числа) на льоту. Це не проблема у функціональному мовою з підтримкою ледачих обчислень, начебто Хаскеля — список буде розраховуватися по мірі потреби. Аналогічне поведінка може бути реалізовано і на с++ З використанням потоків або ледачих ітераторів. Я не буду робити це тут, оскільки списки, з якими ми маємо справу в цій задачі відносно короткі, але ви можете прочитати більше про це підході ось в цій статті.

Ми поки ще не готові написати повне рішення нашого пазла, але я покажу начерк того, як воно буде виглядати. Уявіть, що StateL — це просто список. Подивіться, який сенс набуває загальна картина:

StateL<tuple<int, int, int>> solve()
{
StateL<int> sel = &select<int>;

return for_each(sel, [=](int s) {
return for_each(sel, [=](int e) {
return for_each(sel, [=](int n) {
return for_each(sel, [=](int d) {
return for_each(sel, [=](int m) {
return for_each(sel, [=](int o) {
return for_each(sel, [=](int r) {
return for_each(sel, [=](int y) {
return yield_if(s != 0 && m!= 0, [=]() {
int send = asNumber(vector{s, e, n, d});
int more = asNumber(vector{m, o, r, e});
int money = asNumber(vector{m, o, n, e, y});
return yield_if(send + more == money, [=]() {
return yield(make_tuple(send, more money));
});
});
});});});});});});});});
}


Перший виклик for_each приймає вибірку цілих чисел, sel (поки не будемо замислюватися про їх унікальності), і «продовження» — лямбда-функцію, яка приймає один интежер, s і генерує список рішень — кортежів з трьох цілих чисел. Це «продовження», у свою чергу, викликає for_each з вибіркою для наступної букви, e, і т. д.

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

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

Завдання для самостійної роботи



  • Реалізувати for_each та yield для вектора замість списку. Використовувати std::transform замість fmap
  • Використовуючи монаду списку (або реалізовану на попередньому кроці їй «векторну» модифікацію) написати функцію, яка буде генерувати назви всіх кліток шахової дошки (набори пар символ від 'a' до 'h' — число від 1 до 8)
  • Реалізувати версію функції for_each (назвемо її repeat), яка візьме «продовження» k типу function<List<B>()> (зверніть увагу на відсутність аргументів). Функція повинна послідовно викликати k для кожного елемента списку lst.

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

0 коментарів

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