This is part 3 of the miniseries about solving a simple constraint-satisfaction problem:
s e n d + m o r e --------- m o n e yusing monads in C++. Previously: The State Monad
A constraint satisfaction problem may be solved by brute force, by trying all possible substitutions. This may be done using the imperative approach with loops, or a declarative approach with the list monad. The list monad works by fanning out a list of “alternative universes,” one for each individual substitution. It lets us explore the breadth of the solution space. The universes in which the substitution passes all the constraints are then gathered together to form the solution.
We noticed also that, as we are traversing the depth of the solution space, we could avoid testing unnecessary branches by keeping track of some state. Indeed, we start with a list of 10 possibilities for the first character, but there are only 9 possibilities for the second character, 8 for the third, and so on. It makes sense to start with a list of ten digits, and keep removing digits as we make our choices. At every point, the list of remaining choices is the state we have to keep track of.
Again, there is the imperative approach and the functional approach to state. The imperative approach makes the state mutable and the composition of actions requires backtracking. The functional approach uses persistent, immutable data structures, and the composition is done at the level of functions — plans of action that can be executed once the state is available. These plans of action form the state monad.
The functional solution to our problem involves the combination of the list monad and the state monad. Mashing two monads together is not trivial — in Haskell this is done using monad transformers — but here I’ll show you how to do it manually.
State List
Let’s start with the state, which is the list of digits to choose from:
using State = List<int>;
In the state monad, our basic data structure was a function that took a state and returned a pair: a value and a new state. Now we want our functions to generate, as in quantum mechanics, a whole list of alternative universes, each described by a pair: a value and a state.
Notice that we have to vary both the value and the state within the list. For instance, the function that selects a number from a list should produce a different number and a different list in each of the alternative universes. If the choice is, say, 3, the new state will have 3 removed from the list.
Here’s the convenient generic definition of the list of pairs:
template<class A> using PairList = List<pair<A, State>>;
And this is our data structure that represents a non-deterministic plan of action:
template<class A> using StateList = function<PairList<A>(State)>;
Once we have such a non-deterministic plan of action, we can run it. We give it a state and get back a list of results, each paired with a new state:
template<class A>
PairList<A> runStateList(StateList<A> st, State s)
{
return st(s);
}
Composing Non-Deterministic Plans
As we’ve seen before, the essence of every monad is the composition of individual actions. The higher-order function mbind that does the composition has the same structure for every monad. It takes two arguments. One argument is the result of our previous activity. For the list monad, it was a list of values. For the state monad it was a plan of action to produce a value (paired with the leftover state). For the combination state-list monad it will be a plan of action to produce a list of values (each combined with the leftover state).
The second argument to mbind is a continuation. It takes a single value. It’s supposed to be the value that is encapsulated in the first argument. In the case of the list monad, it was one value from the list. In the case of the state monad, it was the value that would be returned by the execution of the plan. In the combined state-list monad, this will be one of the values produced by the plan.
The continuation is supposed to produce the final result, be it a list of values or a plan. In the state-list monad it will be a plan to produce a list of values, each with its own leftover state.
Finally, the result of mbind is the composite: for the list monad it was a list, for the state monad it was a plan, and for the combination, it will be a plan to produce a list of values and states.
We could write the signature of mbind simply as:
template<class A, class B> StateList<B> mbind(StateList<A>, function<StateList<B>(A)>)
but that would prevent the C++ compiler from making automatic type deductions. So instead we parameterize it with the type A and a function type F. That requires some additional footwork to extract the return type from the type of F:
template<class A, class F>
auto mbind(StateList<A> g, F k)
-> decltype(k(g(State()).front().first))
The implementation of mbind is a combination of what we did for the list monad and for the state monad. To begin with, we are supposed to return a plan, so we have to create a lambda. This lambda takes a state s as an argument. Inside the lambda, given the state, we can run the first argument — the plan. We get a list of pairs. Each pair contains a value and a new state. We want to execute the continuation k for each of these values.
To do that, we run fmap over this list (think std::transform, but less messy). Inside fmap, we disassemble each pair into value and state, and execute the continuation k over the value. The result is a new plan. We run this plan, passing it the new state. The result is a list of pairs: value, state.
Since each item in the list produces a list, the result of fmap is a list of lists. Just like we did in the list monad, we concatenate all these lists into one big list using concatAll.
template<class A, class F>
auto mbind(StateList<A> g, F k)
-> decltype(k(g(State()).front().first))
{
return [g, k](State s) {
PairList<A> plst = g(s);
// List<PairList<B>>
auto lst2 = fmap([k](pair<A, State> const & p) {
A a = p.first;
State s1 = p.second;
auto ka = k(a);
auto result = runStateList(ka, s1);
return result;
}, plst);
return concatAll(lst2);
};
}
To make state-list into a full-blown monad we need one more ingredient: the function mreturn that turns any value into a trivial plan to produce a singleton list with that value. The state is just piped through:
template<class A>
StateList<A> mreturn(A a)
{
return [a](State s) {
// singleton list
return PairList<A>(make_pair(a, s));
};
}
So that would be all for the state-list monad, except that in C++ we have to special-case mbind for the type of continuation that takes a void argument (there is no value of type void in C++). We’ll call this version mthen:
template<class A, class F>
auto mthen(StateList<A> g, F k) -> decltype(k())
{
return [g, k](State s) {
PairList<A> plst = g(s);
auto lst2 = fmap([k](pair<A, State> const & p) {
State s1 = p.second;
auto ka = k();
auto result = runStateList(ka, s1);
return result;
}, plst);
return concatAll(lst2);
};
}
Notice that, even though the value resulting from running the first argument to mthen is discarded, we still have to run it because we need the modified state. In a sense, we are running it only “for side effects,” although all these functions are pure and have no real side effects. Once again, we can have our purity cake and eat it too, simulating side effects with pure functions.
Guards
Every time we generate a candidate substitution, we have to check if it satisfies our constraints. That would be easy if we could access the substitution. But we are in a rather peculiar situation: We are writing code that deals with plans to produce substitutions. How do you test a plan? Obviously we need to write a plan to do the testing (haven’t we heard that before?).
Here’s the trick: Look at the implementation of mthen (or mbind for that matter). When is the continuation not executed? The continuation is not executed if the list passed to fmap is empty. Not executing the continuation is equivalent to aborting the computation. And what does mthen return in that case? An empty list!
So the way to abort a computation is to pass an argument to mthen that produces an empty list. Such a poison pill of a plan is produced by a function traditionally called mzero.
template<class A>
StateList<A> mzero()
{
return[](State s) {
return PairList<A>(); // empty list
};
}
In functional programming, a monad that supports this functionality is called a “monad plus” (it also has a function called mplus). It so happens that the list monad and the state-list monad are both plus.
Now we need a function that produces a poison pill conditionally, so we can pass the result of this function to mthen. Remember, mthen ignores the individual results, but is sensitive to the size of the list. The function guard, on success, produces a discardable value — here, a nullptr — in a singleton list. This will trigger the execution of the continuation in mthen, while discarding the nullptr. On failure, guard produces mzero, which will abort the computation.
StateList<void*> guard(bool b)
{
if (b) {
return [](State s) {
// singleton list with discardable value
return List<pair<void*, State>>(make_pair(nullptr, s));
};
}
else
return mzero<void*>(); // empty list
}
The Client Side
Everything I’ve described so far is reusable code that should be put in a library. Equipped with the state-list monad library, all the client needs to do is to write a few utility functions and combine them into a solution.
Here’s the function that picks a number from a list. Actually, it picks a number from a list in all possible ways. It returns a list of all picks paired with the remainders of the list. This function is our non-deterministic selection plan.
template<class A>
PairList<A> select(List<A> lst)
{
if (lst.isEmpty())
return PairList<A>();
A x = lst.front();
List<A> xs = lst.popped_front();
auto result = List<pair<A, State>>();
forEach(select(xs), [x, &result](pair<A, List<A>> const & p)
{
A y = p.first;
List<A> ys = p.second;
auto y_xys = make_pair(y, ys.pushed_front(x));
result = result.pushed_front(y_xys);
});
return result.pushed_front(make_pair(x, xs));
}
Here’s a little utility function that converts a list (actually, a vector) of digits to a number:
int asNumber(vector<int> const & v)
{
int acc = 0;
for (auto i : v)
acc = 10 * acc + i;
return acc;
}
And here’s the final solution to our puzzle:
StateList<tuple<int, int, int>> solve()
{
StateList<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));
});
});
});});});});});});});});
}
It starts by creating the basic plan called sel for picking numbers from a list. (The list is the state that will be provided later.) It binds this selection to a very large continuation that produces the final result — the plan to produce triples of numbers.
Here, sel is really a plan to produce a list, but the continuation expects just one number, s. If you look at the implementation of mbind, you’ll see that this continuation is called for every single pick, and the results are aggregated into one list.
The large continuation that is passed to the first mbind is itself implemented using mbind. This one, again, takes the plan sel. But we know that the state on which this sel will operate is one element shorter than the one before it. This second selection is passed to the next continuation, and so on.
Then the pruning begins: There is an mthen that takes a guard that aborts all computations where either s or m is zero. Then three numbers are formed from the selected digits. Notice that all those digits are captured by the enclosing lambdas by value (the [=] clauses). Yet another mthen takes a guard that checks the arithmetics and, if that one passes, the final plan to produce a singleton triple (send, more, money) is returned.
In theory, all these singletons would be concatenated on the way up to produce a list of solutions, but in reality this puzzle has only one solution. To get this solution, you run the plan with the list of digits:
List<int> lst{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
cout << evalStateList(solve(), lst);
The function evalStateList works the same way as runStateList except that it discards the leftover state. You can either implement it or use runStateList instead.
What’s Next?
One of the advantages of functional programming (other than thread safety) is that it makes refactoring really easy. Did you notice that 8 lines of code in our solution are almost identical? That’s outrageous! We have to do something about it. And while we’re at it, isn’t it obvious that a substitution should be represented as a map from characters to digits? I’ll show you how to do it in the next installment.
All this code and more is available on github.
Bartosz Milewski's Programming Cafe 