[Перевод] Использование монад в С++. Часть 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
auto for_each(List lst, F k) -> decltype(k(lst.front()))
{
using B = decltype(k(lst.front()).front());
// ограничения, налагаемые на тип F должны были бы быть выражены с помощью концептов,
// если бы их наконец включили в стандарт языка С++
static_assert(std::is_convertible<
F, std::function(A)>>::value,
"for_each requires a function type List(A)");
List> lstLst = fmap(k, lst);
return concatAll(lstLst);
}
Функция fmap аналогична стандартной std: transform — она применяет «продолжение» k к каждому элементу списка lst. Поскольку k само по себе возвращает список, результатом будет список списков, lstLst. Функция concatAll объединяет все элементы всех этих списков в один большой список.
Мои поздравления! Вы только что посмотрели на монаду. Она называется монадой списка и может быть использована, в частности, для моделирования недетерминистических процессов. Монада на самом деле определена двумя функциями. Одна из них это вышеуказанная for_each, а вот и вторая:
template
List yield(A a)
{
return List (a);
}
Это функция yield, которая возвращает список из одного элемента. Мы используем yield на том этапе, когда уже закончим «размножение вселенных» и дойдём до момента, когда мы хотим вернуть одно значение. Мы используем её, чтобы создать «продолжение» содержащеё всего одно значение. Оно представляет собой одинокую скучную жизнь, полностью предопределённую и лишенную любого выбора.
Позже я переименую эти функции в mbind и mreturn, поскольку они определяют монаду в общем, а не только монаду списка.
Имена вроде for_each и yield имеют достаточно «императивное» звучание. Это, конечно, потому, что в функциональном программировании монады в некотором смысле слова выполняют роль императивного кода. Но ни for_each ни yield не являются структурами данных — они являются функциями. Точнее, for_each, которая звучит и работает как цикл, является функцией высшего порядка, как и fmap, которая используется в её реализации. Конечно, на каком-то уровне код станет императивным — тот же fmap может быть написан рекурсивно или с использование цикла, но на верхнем уровне мы имеем лишь декларации функций. Ну и вот оно — декларативное программирование!
Есть существенное отличие между циклом и функцией, вроде for_each: for_each принимает в качестве аргумента весь список, в то время как цикл может генерировать необходимые значения (в нашем случае целые числа) на лету. Это не проблема в функциональном языке с поддержкой ленивых вычислений, вроде Хаскеля — список будет рассчитываться по мере надобности. Аналогичное поведение может быть реализовано и на С++ с использованием потоков или ленивых итераторов. Я не буду делать это здесь, поскольку списки, с которыми мы имеет дело в этой задаче относительно коротки, но вы можете прочесть больше об этом подходе вот в этой статье.
Мы пока ещё не готовы написать полное решение нашего пазла, но я покажу набросок того, как оно будет выглядеть. Представьте, что StateL — это просто список. Посмотрите, какой смысл приобретает общая картина:
StateL> solve()
{
StateL sel = &select;
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
