This is the second part of the cycle “Using Monads in C++ to Solve Constraints” in which I’m illustrating functional techniques using the example of a simple puzzle:

s e n d + m o r e --------- m o n e yPreviously, I talked about using the list monad to search the breadth of the solution space.

What would you do if you won a lottery? Would you buy a sports car, drop your current job, and go on a trip across the United States? Maybe you would start your own company, multiply the money, and then buy a private jet?

We all like making plans, but they are often contingent on the state of our finances. Such plans can be described by functions. For instance, the car-buying plan is a function:

pair<Car, Cash> buyCar(Cash cashIn)

The input is some amount of `Cash`

, and the output is a brand new `Car`

and the leftover `Cash`

(not necessarily a positive number!).

In general, a financial plan is a function that takes cash and returns the result paired with the new value of cash. It can be described generically using a template:

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

You can combine smaller plans to make bigger plans. For instance, you may use the leftover cash from your car purchase to finance your trip, or invest in a business, and so on.

There are some things that you already own, and you can trivially include them in your plans:

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

What does all this daydreaming have to do with the solution to our puzzle? I mentioned previously that we needed to keep track of state, and this is how functional programmers deal with state. Instead of relying on side effects to silently modify the state, they write code that generates plans of action.

An imperative programmer, on the other hand, might implement the car-buying procedure by passing it a bank object, and the withdrawal of money would be a side effect of the purchase. Or, the horror!, the bank object could be global.

In functional programming, each individual plan is a function: The state comes in, and the new state goes out, paired with whatever value the function was supposed to produce in the first place. These little plans are aggregated into bigger plans. Finally, the master plan is executed — that’s when the actual state is passed in and the result comes out together with a new state. We can do the same in modern C++ using lambdas.

You might be familiar with a similar technique used with expression templates in C++. Expression templates form the basis of efficient implementation of matrix calculus, where expressions involving matrices and vectors are not evaluated on the spot but rather converted to parse trees. These trees may then be evaluated using more efficient techniques. You can think of an expression template as a plan for evaluating the final result.

## The State Monad

To find the solution to our puzzle, we will generate substitutions by picking digits from a list of integers. This list of integers will be our state.

using State = List<int>;

We will be using a persistent list, so we won’t have to worry about backtracking. Persistent lists are never mutated — all their versions persist, and we can go back to them without fearing that they may have changed. We’ll need that when we combine our state calculations with the list monad to get the final solution. For now, we’ll just consider one substitution.

We’ll be making and combining all kinds of plans that rely on, and produce new state:

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

We can always run a plan, provided we have the state available:

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

You may recall from the previous post that the essence of every monad is the ability to compose smaller items into bigger ones. In the case of the state monad we need the ability to compose plans of action.

For instance, suppose that you know how to generate a plan to travel across the United States on a budget, as long as you have a car. You don’t have a car though. Not to worry, you have a plan to get a car. It should be easy to generate a composite plan that involves buying the car and then continuing with your trip.

Notice the two ingredients: one is the plan to buy a car: `Plan<Car>`

. The second ingredient is a function that takes a car and produces the plan for your trip, `Plan<Trip>`

. This function is the *continuation* that leads to your final goal: it’s a function of the type `Plan<Trip>(Car)`

. And the continuation itself may in turn be a composite of many smaller plans.

So here’s the function `mbind`

that binds a plan `pl`

to a continuation `k`

. The continuation uses the output of the plan `pl`

to generate another plan. The function `mbind`

is supposed to return a new composite plan, so it must return a lambda. Like any other plan, this lambda takes a state and returns a pair: value, state. We’ll implement this lambda for the most general case.

The logic is simple. Inside the lambda we will have the state available, so we can run the plan `pl`

. We get back a pair: the value of type `A`

and the new state. We pass this value to the continuation `k`

and get back a new plan. Finally, we run that plan *with the new state* and we’re done.

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); // this should really be done with concepts 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! }; }

Notice that all this running of plans inside `mbind`

doesn’t happen immediately. It happens when the lambda is executed, which is when the larger plan is run (possibly as part of an even larger plan). So what `mbind`

does is to create a new plan to be executed in the future.

And, as with every monad, there is a function that takes regular input and turns it into a trivial plan. I called it `got_it`

before, but a more common name would be `mreturn`

:

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

The state monad usually comes with two helper functions. The function `getState`

gives direct access to the state by turning it into the return value:

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

Using `getState`

you may examine the state *when the plan is running*, and dynamically select different branches of your plan. This makes monads very flexible, but it also makes the composition of different monads harder. We’ll see this in the next installment, when we compose the state monad with the list monad.

The second helper function is used to modify (completely replace) the state.

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

It doesn’t evaluate anything useful, so its return type is `void*`

and the returned value is `nullptr`

. Its only purpose is to encapsulate a side effect. What’s amazing is that you can do it and still preserve functional purity. There’s no better example of having your cake and eating it too.

## Example

To demonstrate the state monad in action, let’s implement a tiny example. We start with a small plan that just picks the first number from a list (the list will be our state):

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

Persistent list method `popped_front`

returns a list with its first element popped off. Typical of persistent data structures, this method doesn’t modify the original list. It doesn’t copy the list either — it just creates a pointer to its tail.

Here’s our first plan:

Plan<int> sel = &select;

Now we can create a more complex plan to produce a pair of integers:

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

Let’s analyze this code. The first `mbind`

takes a plan `sel`

that selects the first element from a list (the list will be provided later, when we execute this plan). It binds it to the continuation (whose body I have grayed out) that takes the selected integer `i`

and produces a plan to make a pair of integers. Here’s this continuation:

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

It binds the plan `sel`

to another, smaller continuation that takes the selected element `j`

and produces a plan to make a pair of integers. Here’s this smaller continuation:

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

It combines the first integer `i`

that was captured by the lambda, with the second integer `j`

that is the argument to the lambda, and creates a trivial plan that returns a pair:

mreturn(make_pair(i, j));

Notice that we are using the same plan `sel`

twice. But when this plan is executed inside of our final plan, it will return two different elements from the input list. When `mbind`

is run, it first passes the state (the list of integers) to the first `sel`

. It gets back the modified state — the list with the first element popped. It then uses this shorter list to execute the plan produced by the continuation. So the second `sel`

gets the shortened list, and picks *its* first element, which is the second element of the original list. It, too, shortens the list, which is then passed to `mreturn`

, which doesn’t modify it any more.

We can now run the final plan by giving it a list to pick from:

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

We are still not ready to solve the puzzle, but we are much closer. All we need is to combine the list monad with the state monad. I’m leaving this task for the next installment.

But here’s another look at the final solution:

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)); }); }); });});});});});});});}); }

This time I didn’t rename `mbind`

to `for_each`

and `mreturn`

to `yield`

.

Now that you’re familiar with the state monad, you may appreciate the fact that the same `sel`

passed as the argument to `mbind`

will yield a different number every time, as long as the state list contains unique digits.

## Before You Post a Comment

I know what you’re thinking: Why would I want to complicate my life with monads if there is a much simpler, imperative way of dealing with state? What’s the payoff of the functional approach? The immediate payoff is thread safety. In imperative programming mutable shared state is a never-ending source of concurrency bugs. The state monad and the use of persistent data structures eliminates the possibility of data races. And it does it without any need for synchronization (other than reference counting inside shared pointers).

I will freely admit that C++ is not the best language for functional programming, and that monadic code in C++ looks overly complicated. But, let’s face it, in C++ everything looks overly complicated. What I’m describing here are implementation details of something that should be encapsulated in an easy to use library. I’ll come back to it in the next installment of this mini-series.

## Challenges

- Implement
`select`

from the example in the text using`getState`

and`putState`

. - Implement
`evalPlan`

, a version of`runPlan`

that only returns the final value, without the state. - Implement
`mthen`

— a version of`mbind`

where the continuation doesn’t take any arguments. It ignores the result of the`Plan`

, which is the first argument to`mthen`

(but it still runs it, and uses the modified state). - Use the state monad to build a simple RPN calculator. The state is the stack (a
`List`

) of items: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) {} };

Implement the function

`calc()`

that creates a plan to evaluate an integer. Here’s the test code that should print -1:List<int> stack{ Item(Plus) , Item(Minus) , Item(4) , Item(8) , Item(3) }; cout << evalPlan(calc(), stack) << endl;

(The solution is available on github.)

November 23, 2015 at 9:30 am

[…] https://bartoszmilewski.com/2015/05/14/using-monads-in-c-to-solve-constraints-2-the-state-monad/ […]