Using monads in C ++. Part 2: state monad
Part 1
Part 2
What do you do if you win the lottery tomorrow? Buy a sports car, quit your job and go on a tour of the USA? Or maybe become the founder of your own company, multiply the state and buy a personal plane?
We all love to make plans, and most often they rely on our financial condition. Such plans can be described by function. For example, the plan for buying a car is:
')
At the entrance we have a certain amount of money ( Cash ), and at the exit a new car ( Car ) and some amount (not a fact that is positive!) Of the remaining finances ( Cash ). In general, a financial plan is a function that accepts money and returns the result, plus the remaining amount of money. It can be described by the pattern:
You can combine small plans to get big. For example, you can use the funds left after buying a car for your trip or invest in a business. If you have things that already belong to you, they can become part of your plans:
What does all these dreams have to do with solving our puzzle ? I said earlier that we need to save a state somewhere, and this is the way programmers in functional languages ​​work with state. Instead of explicitly modifying the state, they write code that generates a plan of action.
In our case, the programmer in the imperative language can write something like the procedure for buying a car, which transfers the object of the bank account and the cost of the car. Or (horror!) The object of a bank account can be global.
In functional programming, each individual plan is a function: the state arrives at the input and the new state returns at the output associated with anything that the function deems necessary to return as the result of its work. These small plans are going to larger plans. In the end, the Main Plan is executed - that function, at the input of which the present input state comes and whose result should represent the final entity we are looking for. In modern C ++, we can do things like this with lambdas.
To find a solution to our puzzle, we will generate substitutions by selecting numbers from a list of integers. The list of integers will be our state.
We will use a persistent list, so we don’t need to worry about rolling back. Persistent lists never change - all their versions are persistent and we can return to them without fear that they might change. We need them when we combine our state calculations with the list monad to get the final solution. For now, consider one substitution.
We will create plans that take the current state and create a new one:
We can always start a plan by giving it some initial state:
As you can remember from the previous article, the feature of each monad is that it can combine smaller entities to create larger ones. In the case of a state monad, we need the ability to create action plans.
Imagine, for example, that you know how to generate a plan for a tour of the United States, provided you have a car and some budget. But you do not have a car. No problem, we can create a plan for buying a car. Having both of them is not difficult to generate a general plan for buying a car and planning a trip.
Pay attention to two components: one of them is a plan for buying a car: Plan <Car> . The second component is the function that receives the car and generates the trip plan, Plan <Trip> . This function is a “continuation” that leads you to the ultimate goal: functions like Plan <Trip> (Car) . And the “continuation” in itself can consist of a large number of small plans.
And here is the mbind function that binds the plan pl to the “continuation” k . Continuing uses the output of the plan pl to generate a new plan. The mbind function should return the new master plan, that is, it should return the lambda. Like any other plan, this lambda takes a state and returns a pair: value and state. We implement this lambda in the most common way.
The logic is simple. Inside the lambda state is available to us, which means we can run a plan pl . At its output, we get a pair: the value of type A and the new state. We transfer this value to the “continuation” k and get a new plan. In the end, we run this plan with a new state and that's it.
Note that this entire launch of the plans inside mbind does not happen immediately. It occurs only when lambda is performed, i.e. when a larger plan is launched (perhaps as part of a larger plan launch). So all that mbind does is create a new plan that will be executed sometime in the future.
And, as for any monad, there is a function that takes the usual input data and turns it into a trivial plan. Let's call it mreturn.
Two auxiliary functions usually come close to the state monad. The getState function gives direct access to the state by copying it to the return value:
Using getState, you can check the status as the plan runs and dynamically select one of the branches of your code. This makes the monads very flexible, but at the same time complicates the composition of several monads. We will see this at the stage of combining the monad of the state and the monad of the list.
The second auxiliary function is used to modify (complete replacement) the state.
It does not calculate anything useful, so it returns a value of type void * and this value is nullptr . Its only purpose is to encapsulate side effects. Yes, you can do this and still maintain the functional purity of your code.
And here is a small demonstration of the work of the state monad. We will start with a simple plan that just takes the first number from the list (the list will be our state):
The popped_front method of a persistent list returns a list without its first element. Since the list is persistent, this method does not modify the original list. At the same time, it does not create a copy of it — it simply returns a pointer to the tail of the list, starting from the second element.
Here is our first plan:
Now we will create a more complex plan for generating pairs of integers:
Let's analyze this code. The first mbind accepts the sel plan, which selects the first item from the list (the list will be provided later during the execution of the plan). It binds to the "continuation", which takes the selected integer i and generates a plan that creates a pair of integers. Here is the "continuation":
It binds the sel plan to another, smaller “extension”, which accepts the selected element j and generates a plan to create a pair of integers. Here is a smaller "continuation":
It combines the first integer i , which was captured by a lambda with the second integer j , which was passed to the lambda argument and creates a trivial plan that returns a pair:
Please note that we use the same sel plan twice. But when this plan is executed within our final plan, it will return two different elements of the initial list. When mbind is executed , it first passes the state (a list of integers) to the first sel . Back she gets a modified state - a list without the first element. She then uses this short list to fulfill the plan created by the continuation. Thus, the second sel selects the first item from the already shortened list (the second item of the original list). Here the list is shortened again and passed to mreturn , which no longer modifies it.
Now we can run the final plan, giving it a list of integers:
We are still not ready to solve the original puzzle, but the solution is already very close. All we have to do is combine the list monad and state monad. And we will do it in the next part.
In the meantime, take a look at the final decision:
This time I did not rename mbind to for_each , but mreturn to yield .
Now that we have reviewed the state monad, you can see that the single sel passed to the arguments in mbind will generate different numbers (assuming that there were different numbers in the original list).
I know what you are thinking now: why do I need to complicate my life with monads, if there is a much simpler imperative style of working with the state? What are the benefits of a functional approach? Immediate benefit is thread safety. In imperative programming, the mutable shared state is the source of endless errors. The state monad and the use of persistent data structures exclude the possibility of racing and does so without any synchronization (except for reference counting in smart pointers).
I completely agree that C ++ is not the best language for a functional programming style and C ++ monads look complicated. But let's face it, C ++ code rarely looks simple at all. What I have described here is the details of the components that should be encapsulated in an easy-to-use library.
Part 2
What do you do if you win the lottery tomorrow? Buy a sports car, quit your job and go on a tour of the USA? Or maybe become the founder of your own company, multiply the state and buy a personal plane?
We all love to make plans, and most often they rely on our financial condition. Such plans can be described by function. For example, the plan for buying a car is:
')
pair<Car, Cash> buyCar(Cash cashIn) At the entrance we have a certain amount of money ( Cash ), and at the exit a new car ( Car ) and some amount (not a fact that is positive!) Of the remaining finances ( Cash ). In general, a financial plan is a function that accepts money and returns the result, plus the remaining amount of money. It can be described by the pattern:
template<class A> using Plan = function<pair<A, Cash>(Cash)>; You can combine small plans to get big. For example, you can use the funds left after buying a car for your trip or invest in a business. If you have things that already belong to you, they can become part of your plans:
template<class A> Plan<A> got_it(A a) { return [a](Cash s) { return make_pair(a, s); }; } What does all these dreams have to do with solving our puzzle ? I said earlier that we need to save a state somewhere, and this is the way programmers in functional languages ​​work with state. Instead of explicitly modifying the state, they write code that generates a plan of action.
In our case, the programmer in the imperative language can write something like the procedure for buying a car, which transfers the object of the bank account and the cost of the car. Or (horror!) The object of a bank account can be global.
In functional programming, each individual plan is a function: the state arrives at the input and the new state returns at the output associated with anything that the function deems necessary to return as the result of its work. These small plans are going to larger plans. In the end, the Main Plan is executed - that function, at the input of which the present input state comes and whose result should represent the final entity we are looking for. In modern C ++, we can do things like this with lambdas.
State monad
To find a solution to our puzzle, we will generate substitutions by selecting numbers from a list of integers. The list of integers will be our state.
using State = List<int>; We will use a persistent list, so we don’t need to worry about rolling back. Persistent lists never change - all their versions are persistent and we can return to them without fear that they might change. We need them when we combine our state calculations with the list monad to get the final solution. For now, consider one substitution.
We will create plans that take the current state and create a new one:
template<class A> using Plan = function<pair<A, State>(State)>; We can always start a plan by giving it some initial state:
template<class A> pair<A, State> runPlan(Plan<A> pl, State s) { return pl(s); } As you can remember from the previous article, the feature of each monad is that it can combine smaller entities to create larger ones. In the case of a state monad, we need the ability to create action plans.
Imagine, for example, that you know how to generate a plan for a tour of the United States, provided you have a car and some budget. But you do not have a car. No problem, we can create a plan for buying a car. Having both of them is not difficult to generate a general plan for buying a car and planning a trip.
Pay attention to two components: one of them is a plan for buying a car: Plan <Car> . The second component is the function that receives the car and generates the trip plan, Plan <Trip> . This function is a “continuation” that leads you to the ultimate goal: functions like Plan <Trip> (Car) . And the “continuation” in itself can consist of a large number of small plans.
And here is the mbind function that binds the plan pl to the “continuation” k . Continuing uses the output of the plan pl to generate a new plan. The mbind function should return the new master plan, that is, it should return the lambda. Like any other plan, this lambda takes a state and returns a pair: value and state. We implement this lambda in the most common way.
The logic is simple. Inside the lambda state is available to us, which means we can run a plan pl . At its output, we get a pair: the value of type A and the new state. We transfer this value to the “continuation” k and get a new plan. In the end, we run this plan with a new state and that's it.
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! }; } Note that this entire launch of the plans inside mbind does not happen immediately. It occurs only when lambda is performed, i.e. when a larger plan is launched (perhaps as part of a larger plan launch). So all that mbind does is create a new plan that will be executed sometime in the future.
And, as for any monad, there is a function that takes the usual input data and turns it into a trivial plan. Let's call it mreturn.
template<class A> Plan<A> mreturn(A a) { return [a](State s) { return make_pair(a, s); }; } Two auxiliary functions usually come close to the state monad. The getState function gives direct access to the state by copying it to the return value:
Plan<State> getState() { return [](State s) { return make_pair(s, s); }; } Using getState, you can check the status as the plan runs and dynamically select one of the branches of your code. This makes the monads very flexible, but at the same time complicates the composition of several monads. We will see this at the stage of combining the monad of the state and the monad of the list.
The second auxiliary function is used to modify (complete replacement) the state.
Plan<void*> putState(State newState) { return [=](State s) { return make_pair(nullptr, newState); }; } It does not calculate anything useful, so it returns a value of type void * and this value is nullptr . Its only purpose is to encapsulate side effects. Yes, you can do this and still maintain the functional purity of your code.
Example
And here is a small demonstration of the work of the state monad. We will start with a simple plan that just takes the first number from the 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()); } The popped_front method of a persistent list returns a list without its first element. Since the list is persistent, this method does not modify the original list. At the same time, it does not create a copy of it — it simply returns a pointer to the tail of the list, starting from the second element.
Here is our first plan:
Plan<int> sel = &select; Now we will create a more complex plan for generating pairs 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 accepts the sel plan, which selects the first item from the list (the list will be provided later during the execution of the plan). It binds to the "continuation", which takes the selected integer i and generates a plan that creates a pair of integers. Here is the "continuation":
[=](int i) { return mbind(sel, [=](int j) { return mreturn(make_pair(i, j)); }); }); It binds the sel plan to another, smaller “extension”, which accepts the selected element j and generates a plan to create a pair of integers. Here is a smaller "continuation":
[=](int j) { return mreturn(make_pair(i, j)); }); It combines the first integer i , which was captured by a lambda with the second integer j , which was passed to the lambda argument and creates a trivial plan that returns a pair:
mreturn(make_pair(i, j)); Please note that we use the same sel plan twice. But when this plan is executed within our final plan, it will return two different elements of the initial list. When mbind is executed , it first passes the state (a list of integers) to the first sel . Back she gets a modified state - a list without the first element. She then uses this short list to fulfill the plan created by the continuation. Thus, the second sel selects the first item from the already shortened list (the second item of the original list). Here the list is shortened again and passed to mreturn , which no longer modifies it.
Now we can run the final plan, giving it a list of integers:
List<int> st{ 1, 2, 3 }; cout << runPlan(pl, st) << endl; We are still not ready to solve the original puzzle, but the solution is already very close. All we have to do is combine the list monad and state monad. And we will do it in the next part.
In the meantime, take a look at the final decision:
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 did not rename mbind to for_each , but mreturn to yield .
Now that we have reviewed the state monad, you can see that the single sel passed to the arguments in mbind will generate different numbers (assuming that there were different numbers in the original list).
Before you write a comment
I know what you are thinking now: why do I need to complicate my life with monads, if there is a much simpler imperative style of working with the state? What are the benefits of a functional approach? Immediate benefit is thread safety. In imperative programming, the mutable shared state is the source of endless errors. The state monad and the use of persistent data structures exclude the possibility of racing and does so without any synchronization (except for reference counting in smart pointers).
I completely agree that C ++ is not the best language for a functional programming style and C ++ monads look complicated. But let's face it, C ++ code rarely looks simple at all. What I have described here is the details of the components that should be encapsulated in an easy-to-use library.
Home tasks
- Implement select from example in text using getState and putState
- Implement evalPlan , a runPlan version that returns only the final value, without state
- Implement mthen , the mbind version, where the “continuation” takes no arguments. It ignores the result of the plan, which is the first argument mthen (but still runs it and uses the modified state)
- Use the state monad to write a simple expression calculator in the reverse Polish notation . The state in this case will be a stack (list) of elements.
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 calc () function, which implements an elementary calculator. Here is an example, the output should be -1:List<int> stack{ Item(Plus) , Item(Minus) , Item(4) , Item(8) , Item(3) }; cout << evalPlan(calc(), stack) << endl;
(Solution is available on Github )
Source: https://habr.com/ru/post/261145/
All Articles