[Перевод] Использование монад в С++. Часть 2: монада состояния26.06.2015 13:18

К монаде состояния обычно пригалаются две вспомогательные функции. Функция getState даёт прямой доступ к состоянию, копируя его в возвращаемое значение:

Plan getState()
{
    return [](State s) { return make_pair(s, s); };
}

Используя getState вы можете проверить состояние по ходу выполнения плана и динамически выбрать одну из веток вашего кода. Это делает монады очень гибкими, но в то же время усложняет композицию нескольких монад. Мы увидим это на этапе объединения монады состояния и монады списка.

Вторая вспомогательная функция используется для модификации (полного замещения) состояния.

Plan putState(State newState)
{
    return [=](State s) { return make_pair(nullptr, newState); };
}

Она не вычисляет ничего полезного, так что возвращает она значение типа void* и это значение — nullptr. Единственное её предназначение это инкапсуляция побочных эффектов. Да, вы можете сделать это и всё ещё сохранить функциональную чистоту вашего кода.

Пример

А вот и небольшая демонстрация работы монады состояния. Мы начнём с простого плана, который всего лишь берёт первое число из списка (список будет нашим состоянием):

pair> select(List lst)
{
    int i = lst.front();
    return make_pair(i, lst.popped_front());
}

Метод popped_front персистентного списка возвращает список без его первого элемента. Поскольку список персистентный, данный метода не модифицирует оригинальный список. В то же время он и не создаёт его копию — просто возвращает указатель на хвост списка, начинающийся со второго элемента.

Вот наш первый план:

Plan sel = &select;

Теперь мы создадим более сложный план для генерации пар целых чисел:

Plan> pl = 
    mbind(sel, [=](int i) { return
    mbind(sel, [=](int j) { return
    mreturn(make_pair(i, j));
}); });

Давайте проанализируем этот код. Первый mbind принимает план sel, который выбирает первый элемент из списка (список будет предоставлен позже, во время выполнения плана). Он привязывается к «продолжению», которое принимает выбранное целое число i и генерирует план, создающий пару целых чисел. Вот это «продолжение»:

[=](int i) { return
    mbind(sel, [=](int j) { return
    mreturn(make_pair(i, j));
}); });

Оно привязывает план sel к другому, меньшему «продолжению», которое принимает выбранный элемент j и генерирует план для создания пары целых чисел. Вот это меньшее «продолжение»:

[=](int j) { return
    mreturn(make_pair(i, j));
});

Оно комбинирует первое целое число i, которое было захвачено лямбдой со второым целым числом j, которое было передано лямбде аргументом и создаёт тривиальный план, возвращающий пару:

mreturn(make_pair(i, j));

Обратите внимание, что мы используем один и тот же план sel дважды. Но когда этот план выполняется внутри нашего финального плана, он вернёт два различных элемента начального списка. Когда выполняется mbind, она сначала передаёт состояние (список целых чисел) в первый sel. Назад она получает модифицированное состояние — список без первого элемента. Затем она использует этот укороченный список для выполнения плана, созданного «продолжением». Таким образом второй sel выбирает первый элемент из уже укороченного списка (второй элемент оригинального списка). Здесь список снова укорачивается и передаётся mreturn, которая больше его не модифицирует.

Теперь мы можем запустить финальный план, передав ему список целых чисел:

List st{ 1, 2, 3 };
cout << runPlan(pl, st) << endl;

Мы всё ещё не готовы решить исходный пазл, но решение уже очень близко. Всё, что нам нужно сделать, это скомбинировать монадо списка и монаду состояния. И мы сделаем это в следующей части.
А пока ещё раз взглянём на финальное решение:

StateL> solve()
{
    StateL sel = &select;

    return mbind(sel, [=](int s) {
    return mbind(sel, [=](int e) {
    return mbind(sel, [=](int n) {
    return mbind(sel, [=](int d) {
    return mbind(sel, [=](int m) {
    return mbind(sel, [=](int o) {
    return mbind(sel, [=](int r) {
    return mbind(sel, [=](int y) {
        return mthen(guard(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 mthen(guard(send + more == money), [=]() {
                return mreturn(make_tuple(send, more, money));
            });
        });
    });});});});});});});});
}

В этот раз я не переименовывал mbind в for_each, а mreturn в yield.

Теперь, когда мы рассмотрели монаду состояния, вы можете увидеть, что один sel, переданный аргументов в mbind, будет генерировать разные числа (при условии, что в исходном списке были разные цифры).

Перед тем как вы напишете комментарий

Я знаю о чём вы сейчас думаете: зачем мне нужно усложнять свою жизнь монадами, если существует значительно более простой императивный стиль работы с состоянием? Какая выгода от функционального подхода? Немедленной выгодой является потокобезопасность. В императивном программировании изменяемое разделяемое состояние — источник бесконечных ошибок. Монада состояния и использование персистентных структур данных исключает возможность гонок и делает это без какой бы то ни было синхронизации (кроме подсчета ссылок в умных указателях).

Я совершенно согласен, что С++ не лучший языка для функционального стиля программирования и монады на С++ выглядят сложно. Но, давайте посмотрим правде в лицо, код на С++ вообще редко выглядит простым. То, что я здесь описывал, является деталями компонентов, которые должны быть инкапсулированы в простую для использования библиотеку.

Задачи на дом

• Реализуйте select из примера в тексте, используя getState и putState
• Реализуйте evalPlan, версию runPlan, которая возвращает только финальное значение, без состояния
• Реализуйте mthen — версию mbind, где «продолжение» не принимает никаких аргументов. Оно игнорирует результат плана, который является первым аргументов mthen (но всё же запускает его и использует модифицированное состояние)
• Используйте монаду состояния для написания простого калькулятора выражений в обратной польской записи. Состояние в этом случае будет стеком (списком) элементов

  enum ItemType { Plus, Minus, Num };
  
  struct Item
  {
      ItemType _type;
      int _num;
      Item(int i) : _type(Num), _num(i) {}
      Item(ItemType t) : _type(t), _num(-1) {}
  };
  
  

  Реализуйте функцию calc (), которая реализует элементарный калькулятор. Вот пример, на выходе должно получится -1:

  List stack{ Item(Plus)
                 , Item(Minus)
                 , Item(4)
                 , Item(8)
                 , Item(3) };
  cout << evalPlan(calc(), stack) << endl;
  
  

  
  (Решение доступно на Гитхабе)