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

Часть 1
Часть 2

Что вы сделаете, если завтра выиграете в лотерею? Купите спортивную машину, бросите работу и поедете в турне по США? А может быть станете основателем собственной компании, приумножите состояние и купите личный самолёт?

Мы все любим делать планы, и чаще всего они опираются на наше финансовое состояние. Такие планы могут быть описаны функцией. К примеру, план покупки машины это:

pair<Car, Cash> buyCar(Cash cashIn)

На входе у нас некоторое количество денег (Cash), а на выходе новенькая машина (Car) и какое-то количество(не факт, что положительное!) оставшихся финансов (Cash).В общем, финансовый план — это функция, которая принимает деньги и возвращает результат, плюс оставшееся количество денег. Он может быть описан шаблоном:

template<class A>
using Plan = function<pair<A, Cash>(Cash)>;

Вы можете объединять маленькие планы чтобы получить большой. К примеру, вы можете пустить оставшиеся после покупки машины средства на свою поездку или инвестировать в бизнес. Если у вас есть вещи, уже вам принадлежащие, они могут стать часть ваших планов:

template<class A>
Plan<A> got_it(A a)
{
    return [a](Cash s) { return make_pair(a, s); };
}

Какое отношение имеют все эти мечты к решению нашего пазла? Ранее я говорил, что нам нужно где-то сохранять состояние, и это способ, которым программисты на функциональных языках работают с состоянием. Вместо явного модифицирования состояния они пишут код, который генерирует план действий.
Программист на императивном языке в нашем случае может написать что-то вроде процедуры покупки автомобиля, которой передаётся объект банковского счёта и стоимость автомобиля. Или (ужас!) объект банковского счёт может быть глобальным.

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

Монада состояния

Для поиска решения нашего пазла мы будем генерировать подстановки выбором цифр из списка целых чисел. Список целых чисел будет нашим состоянием.

using State = List<int>;

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

Мы будем создавать планы, которые принимают текущее состояние и создают новое:

template<class A>
using Plan = function<pair<A, State>(State)>;

Мы всегда можем запустить план, предоставив ему некоторое начальное состояние:

template<class A>
pair<A, State> runPlan(Plan<A> pl, State s)
{
    return pl(s);
}

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

Представьте, к примеру, что вы знаете как сгенерировать план турне по США, при условии наличия у вас автомобиля и некоторого бюджета. Но у вас нет автомобиля. Ничего страшного, мы можем создать план покупки автомобиля. Имея то и другое уже не составляет труда сгенерировать общий план по покупке автомобиля и планированию путешествия.

Обратите внимание на две компоненты: одна из них это план покупки автомобиля: Plan<Car>. Вторая компонента это функция, которая получает автомобиль и генерироует план поездки, Plan<Trip>. Эта функция является «продолжением», которое ведёт вас к конечной цели: функции типа Plan<Trip>(Car). И «продолжение» само по себе может состоять из болього количества маленьких планов.

А вот и функция mbind, которая привязывает план pl к «продолжению» k. «Продолжение» использует выходное значение плана pl для генерации нового плана. Функция mbind должна вернуть новый составной план, то есть она должна вернуть лямбду. Как и любой другой план, эта лямбда принимает состояние и возвращает пару: значение и состояние. Мы реализуем эту лямбду наиболее общным способом.

Логика проста. Внутри лямбды нам доступно состояние, а значит мы можем запустить план pl. На его выходе мы получаем пару: значение типа A и новое состояние. Мы передаём это значение в «продолжение» k и получаем новый план. В конце концов мы запускаем этот план с новым состоянимем и на этом всё.

template<class A, class F>
auto mbind(Plan<A> pl, F k) -> decltype(k(pl(State()).first))
{
    using B = decltype(k(pl(State()).first)(State()).first);

    // это должно было бы быть выражено с помощью концептов, если 
    // бы их поддержка была встроена в С++
    static_assert(std::is_convertible<
        F, std::function<Plan<B>(A)>> ::value,
        "mbind requires a function type Plan<B>(A)");

    return [pl, k](State s) {
        pair<A, State> ps = runPlan(pl, s);
        Plan<B> plB = k(ps.first);
        return runPlan(plB, ps.second); // new state!
    };
}

Обратите внимание, что весь этот запуск планов внутри mbind не случается немедленно. Он происходит лишь тогда, когда выполняется лямбда, т.е. когда запускается план большего размера (возможно, как часть запуска плана ещё большего размера). Таким образом всё, что делает mbind — это создаёт новый план, который будет выполнен когда-нибудь в будущем.

И, как для любой монады, существует функция, которая получает обычные входные данные и превращает их в тривиальный план. Назовём её mreturn.

template<class A>
Plan<A> mreturn(A a)
{
    return [a](State s) { return make_pair(a, s); };
}

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

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

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

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

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

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

Пример

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

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

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

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

Plan<int> sel = &select;

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

Plan<pair<int, int>> 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<int> st{ 1, 2, 3 };
cout << runPlan(pl, st) << endl;

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

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

    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<int>{s, e, n, d});
            int more  = asNumber(vector<int>{m, o, r, e});
            int money = asNumber(vector<int>{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<int> stack{ Item(Plus)
                 , Item(Minus)
                 , Item(4)
                 , Item(8)
                 , Item(3) };
  cout << evalPlan(calc(), stack) << endl;
  
  

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

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.