Using monads in C ++. Part 1: list monad
- Transfer
- Tutorial
Part 1
Part 2
Sometimes C ++ programmers ask for an example of a problem that cannot be solved without the use of monads. To begin with, this question is incorrect in itself - it’s the same as asking if there is a problem that cannot be solved without cycles. Obviously, if your language has goto operator support, you can do without using loop statements. What monads (and loops) can do for you is to simplify your code and help you structure it better. Just as using loops turns spaghetti code into normal, so using monads can turn your imperative code into declarative code. This transformation can help you write, understand, maintain, and extend your code more easily.
Well, here's a puzzle for you that might get caught in an interview. It is not entirely trivial, several approaches to the solution are possible, and the best of them is not immediately obvious - just something to think about.
You are invited to the following puzzle:
Each letter corresponds to a number from 0 to 9. You need to write a program that selects such correspondence so that the written addition operation is correct. Before you continue reading the article - think for a moment, how would you solve this problem?
It never hurts to impress the interviewer with your knowledge by correctly classifying the problem. This task belongs to the class of “ constraint satisfaction problems ”. The obvious limitation is that the numbers obtained by substituting numbers instead of letters, when added, should give a number corresponding to a given one. There are less obvious limitations, for example, the summands must not start from zero.
If you try to solve this problem with a pen and paper, you will quickly find several heuristics. For example, it’s immediately clear that m must be equal to 1, because there are no two such four-digit numbers that, if added, would give a number greater than 19998. Then you find out that smust be equal to 8 or 9, because otherwise we will not receive a discharge transfer to get a five-digit number, etc. Having a sufficient amount of time, you may write an expert system with a sufficiently large number of rules that can solve this problem (and maybe other similar ones). By the way, mentioning an expert system can give you a couple of extra points at an interview.
There is another approach - it is worth noting that the task has a rather small dimension - we work with 4-5-digit integers, which are not so many. The interviewer may ask you to ask for the number of permutations that will need to be sorted out - there are 10! / (10-8)! = 1814400 pieces. Quite a bit for a modern computer. Thus, the solution of the problem is reduced to generating these permutations and checking them for compliance with the constraints of the original problem.
The classic imperative approach immediately generates code with 8 nested loops (we have 8 unique letters s, e, n, d, m, o, r, y ). It will turn out something like this:
And here we need to check the condition. But not the condition of the sum, from the original problem - the first thing we need to check is that all the numbers in our permutation are different, otherwise it makes no sense.
...
and so on, in the last line there will be 7 comparisons, and there will be 28 in total. And only after that it is possible to collect the numbers " send ", " more " from the numbers and check whether the sum is " money ".
In general, the problem is solved and the interviewer will not be able to say what is wrong. But wait a minute - can't we come up with something better?
Before continuing, I must say that everything that will be written further will be almost a direct translation from Haskell of a program written on the Justin Le blog . I strongly advise everyone to study Haskell and read similar articles in the original, and in this case I will work as a translator.
The problem in our “frontal” solution is in those 28 checks. Yes, our program worked, but it happened because of its small dimension. There are problems with huge dimensions and a significantly larger number of conditions, so it makes sense to come up with some kind of general approach to solving them.
A problem can be formulated as a combination of two smaller problems. One of them concerns the depth, and the second concerns the width of the search for a solution.
Let's look at the depth problem first. Imagine the task of creating just one substitution of numbers instead of the letters of the original puzzle. This can be described as selecting 8 digits from the list 0, 1, ... 9, one digit at a time. As soon as the number is selected, we remove it from the list. We do not want to hard drive the list into our code, so we will make it a parameter of our algorithm. Note that with this approach the algorithm will work even for a list with duplicates or for a list in which comparison and equality operators cannot be defined for elements (for example, a list from std :: future ).
Now let's look at the width problem: we need to repeat the above process for all possible permutations. This is exactly what 8 nested loops in the code above do. There is one problem: each step in selecting the next element from the list is destructive - it changes the list. This is a known problem in enumerating a solution space and its standard solution is backtracking. Once you have processed some candidate, you put the item back in the list and try the next one. This means that you need to track your current state, either implicitly, storing it in the stack of function calls, or explicitly in some data structure.
Wait a second! Aren't we going to talk about functional programming? So why all this talk about modifications and condition? Well, who said that we cannot have a state in functional programming? Functional language programmers have used the state monad since the time when dinosaurs walked the earth. And modifications are not a problem if you use persistent data structures. So fasten your seat belts and bring the chair back to a vertical position, we take off.
We begin with a small reference to quantum mechanics. As you can remember from school, quantum processes are not deterministic. You can do the same experiment several times and get different results in each case. There is a very interesting point of view on quantum mechanics, called the “ Many-World Interpretation ”, in which each experiment generates several alternative historical lines, in each of which it gives its result, and we just fall into one of these “universes” and observe one specific ( unknown in advance) outcome of the experiment.
We use the same approach to solving our puzzle. We will create “alternative universes” for each permutation of numbers corresponding to our letters. So we start with 10 universes for the letter s: in the first, it will have a value of 0, in the second - 1, etc. Next, we divide each of these universes by another 10 by the letter eetc. Most of these universes will not satisfy our conditions, so we will be forced to destroy them. Such a simple approach to the destruction of universes may seem wasteful and resource-intensive, but in functional programming this is not a problem: they quickly created an alternative reality and also quickly destroyed it. This is because the new universes are not so different from those on the basis of which they were generated and they can use most of the data with their “parents”. This is the idea of persistent data structures. We have an immutable data structure that can spawn a new one by cloning. The new data structure shares most of the data with the parent, except for a small “delta”. We will use persistent lists described in this post..
Once you become aware of this “multiple universe” approach, the implementation becomes quite simple. First, we need a function that will create new universes. Since we agreed that it should be “cheap”, we will only generate parts that will differ. What is the difference between all universes generated by the variable s ? Only the value of the s variable . In total there are 10 such universes corresponding to s values from 0 to 9 (the fact that s cannot be equal to 0 will be considered later). Thus, all we need is a function that generates a list of 10 digits. Well, here they are - our 10 universes in all their pure pristine beauty.
And now we find ourselves in one of these alternative universes (actually in all at once, but right now we are considering getting into one of them). We must somehow live on. In functional programming, the rest of your life is a call to a function called Continuation . I know this sounds like a terrible simplification. All your actions, emotions and hopes come down to just calling one function. Well, let's think that the “continuation” describes only some part of your life in this universe, its “computational” component, and everything else happens somewhere separately.
So, what does our life in this universe come down to and what does it give rise to? The input is the universe itself, in which we are, in particular for our example - one of the values sthat we have chosen when creating this universe. But since we live in a space of quantum experiments, the output will be a set of new universes. Thus, the “continuation” receives a number as input, and generates a list. This is not necessarily a list of numbers, but a list of something that describes the differences between the generated universes from each other.
Well, what's the point of this new approach? This is the link of the choice of the universe to the "continuation". This is the place where all the action takes place. This binding, again, can be expressed as a function. This is a function that receives a list of universes and an “extension” that generates a new list of universes (larger). We will call this function for_each and we will try to write it as generically as possible. We will not assume anything about the types of universes transmitted or generated. We will also make the “continue” type a template parameter and determine the return type using auto and decltype :
The fmap function is similar to the standard std :: transform - it applies a “continuation” k to each element of the lst list . Since k itself returns a list, the result is a list of lists, lstLst . The concatAll function combines all the elements of all these lists into one large list.
My congratulations! You just looked at the monad. It is called the list monad and can be used, in particular, for modeling non-deterministic processes. The monad is actually defined by two functions. One of them is the above for_each , and here is the second:
This is a yield function that returns a list of one item. We use yield at the stage when we have already finished the “multiplication of universes” and get to the point where we want to return a single value. We use it to create a “continuation” containing only one meaning. It represents a lonely boring life, completely predetermined and devoid of any choice.
Later I will rename these functions to mbind and mreturn , since they define the monad in general, and not just the list monad.
Names like for_each and yieldhave a fairly "imperative" sound. This, of course, is because in functional programming monads, in a sense, play the role of an imperative code. But neither for_each nor yield are data structures - they are functions. More precisely, for_each , which sounds and works like a loop, is a higher order function, like fmap , which is used in its implementation. Of course, at some level the code will become imperative - the same fmap can be written recursively or using a loop, but at the top level we only have function declarations. Well, here it is - declarative programming!
There is a significant difference between a loop and a function, like for_each: for_each takes the entire list as an argument, while the loop can generate the necessary values (in our case, integers) on the fly. This is not a problem in a functional language with support for lazy computing, like Haskell - the list will be calculated as needed. Similar behavior can be implemented in C ++ using streams or lazy iterators. I will not do this here because the lists we deal with in this task are relatively short, but you can read more about this approach in this article .
We are not yet ready to write a complete solution to our puzzle, but I will show you a sketch of how it will look. Imagine StateL- this is just a list. Look at the meaning of the big picture:
The first call to for_each takes a sample of integers, sel (until we think about their uniqueness), and "continue" is a lambda function that takes one integer, s and generates a list of solutions - tuples of three integers. This "continuation", in turn, calls for_each with a selection for the next letter, e, etc.
The innermost “continuation" is a conditional version of the yield function called yield_if . It checks the condition and generates either an empty list or a list consisting of one element - a decision. Inside, it calls yield_if again , which calls the final yield. In this final yield , when it is called (or if it does not work if all the above conditions have not worked), a solution will be generated - a triple of numbers satisfying the condition of the original puzzle. If there are more than one solutions, they will all be added to the resulting list created inside for_each .
In the second part of this series of articles, I will return to the problem of choosing unique numbers and consider the state monad. You can also take a look at the final code on the github .
Part 2
Sometimes C ++ programmers ask for an example of a problem that cannot be solved without the use of monads. To begin with, this question is incorrect in itself - it’s the same as asking if there is a problem that cannot be solved without cycles. Obviously, if your language has goto operator support, you can do without using loop statements. What monads (and loops) can do for you is to simplify your code and help you structure it better. Just as using loops turns spaghetti code into normal, so using monads can turn your imperative code into declarative code. This transformation can help you write, understand, maintain, and extend your code more easily.
Well, here's a puzzle for you that might get caught in an interview. It is not entirely trivial, several approaches to the solution are possible, and the best of them is not immediately obvious - just something to think about.
You are invited to the following puzzle:
s e n d
+ m o r e
---------
m o n e y
Each letter corresponds to a number from 0 to 9. You need to write a program that selects such correspondence so that the written addition operation is correct. Before you continue reading the article - think for a moment, how would you solve this problem?
Analysis
It never hurts to impress the interviewer with your knowledge by correctly classifying the problem. This task belongs to the class of “ constraint satisfaction problems ”. The obvious limitation is that the numbers obtained by substituting numbers instead of letters, when added, should give a number corresponding to a given one. There are less obvious limitations, for example, the summands must not start from zero.
If you try to solve this problem with a pen and paper, you will quickly find several heuristics. For example, it’s immediately clear that m must be equal to 1, because there are no two such four-digit numbers that, if added, would give a number greater than 19998. Then you find out that smust be equal to 8 or 9, because otherwise we will not receive a discharge transfer to get a five-digit number, etc. Having a sufficient amount of time, you may write an expert system with a sufficiently large number of rules that can solve this problem (and maybe other similar ones). By the way, mentioning an expert system can give you a couple of extra points at an interview.
There is another approach - it is worth noting that the task has a rather small dimension - we work with 4-5-digit integers, which are not so many. The interviewer may ask you to ask for the number of permutations that will need to be sorted out - there are 10! / (10-8)! = 1814400 pieces. Quite a bit for a modern computer. Thus, the solution of the problem is reduced to generating these permutations and checking them for compliance with the constraints of the original problem.
Forehead Solution
The classic imperative approach immediately generates code with 8 nested loops (we have 8 unique letters s, e, n, d, m, o, r, y ). It will turn out something like this:
for (int s = 0; s < 10; ++s)
for (int e = 0; e < 10; ++e)
for (int n = 0; n < 10; ++n)
for (int d = 0; d < 10; ++d)
...
и так до последней буквы
And here we need to check the condition. But not the condition of the sum, from the original problem - the first thing we need to check is that all the numbers in our permutation are different, otherwise it makes no sense.
e != s
n != s && n != e
d != s && d != e && d != n
...
and so on, in the last line there will be 7 comparisons, and there will be 28 in total. And only after that it is possible to collect the numbers " send ", " more " from the numbers and check whether the sum is " money ".
In general, the problem is solved and the interviewer will not be able to say what is wrong. But wait a minute - can't we come up with something better?
Smart decision
Before continuing, I must say that everything that will be written further will be almost a direct translation from Haskell of a program written on the Justin Le blog . I strongly advise everyone to study Haskell and read similar articles in the original, and in this case I will work as a translator.
The problem in our “frontal” solution is in those 28 checks. Yes, our program worked, but it happened because of its small dimension. There are problems with huge dimensions and a significantly larger number of conditions, so it makes sense to come up with some kind of general approach to solving them.
A problem can be formulated as a combination of two smaller problems. One of them concerns the depth, and the second concerns the width of the search for a solution.
Let's look at the depth problem first. Imagine the task of creating just one substitution of numbers instead of the letters of the original puzzle. This can be described as selecting 8 digits from the list 0, 1, ... 9, one digit at a time. As soon as the number is selected, we remove it from the list. We do not want to hard drive the list into our code, so we will make it a parameter of our algorithm. Note that with this approach the algorithm will work even for a list with duplicates or for a list in which comparison and equality operators cannot be defined for elements (for example, a list from std :: future ).
Now let's look at the width problem: we need to repeat the above process for all possible permutations. This is exactly what 8 nested loops in the code above do. There is one problem: each step in selecting the next element from the list is destructive - it changes the list. This is a known problem in enumerating a solution space and its standard solution is backtracking. Once you have processed some candidate, you put the item back in the list and try the next one. This means that you need to track your current state, either implicitly, storing it in the stack of function calls, or explicitly in some data structure.
Wait a second! Aren't we going to talk about functional programming? So why all this talk about modifications and condition? Well, who said that we cannot have a state in functional programming? Functional language programmers have used the state monad since the time when dinosaurs walked the earth. And modifications are not a problem if you use persistent data structures. So fasten your seat belts and bring the chair back to a vertical position, we take off.
List monad
We begin with a small reference to quantum mechanics. As you can remember from school, quantum processes are not deterministic. You can do the same experiment several times and get different results in each case. There is a very interesting point of view on quantum mechanics, called the “ Many-World Interpretation ”, in which each experiment generates several alternative historical lines, in each of which it gives its result, and we just fall into one of these “universes” and observe one specific ( unknown in advance) outcome of the experiment.
We use the same approach to solving our puzzle. We will create “alternative universes” for each permutation of numbers corresponding to our letters. So we start with 10 universes for the letter s: in the first, it will have a value of 0, in the second - 1, etc. Next, we divide each of these universes by another 10 by the letter eetc. Most of these universes will not satisfy our conditions, so we will be forced to destroy them. Such a simple approach to the destruction of universes may seem wasteful and resource-intensive, but in functional programming this is not a problem: they quickly created an alternative reality and also quickly destroyed it. This is because the new universes are not so different from those on the basis of which they were generated and they can use most of the data with their “parents”. This is the idea of persistent data structures. We have an immutable data structure that can spawn a new one by cloning. The new data structure shares most of the data with the parent, except for a small “delta”. We will use persistent lists described in this post..
Once you become aware of this “multiple universe” approach, the implementation becomes quite simple. First, we need a function that will create new universes. Since we agreed that it should be “cheap”, we will only generate parts that will differ. What is the difference between all universes generated by the variable s ? Only the value of the s variable . In total there are 10 such universes corresponding to s values from 0 to 9 (the fact that s cannot be equal to 0 will be considered later). Thus, all we need is a function that generates a list of 10 digits. Well, here they are - our 10 universes in all their pure pristine beauty.
And now we find ourselves in one of these alternative universes (actually in all at once, but right now we are considering getting into one of them). We must somehow live on. In functional programming, the rest of your life is a call to a function called Continuation . I know this sounds like a terrible simplification. All your actions, emotions and hopes come down to just calling one function. Well, let's think that the “continuation” describes only some part of your life in this universe, its “computational” component, and everything else happens somewhere separately.
So, what does our life in this universe come down to and what does it give rise to? The input is the universe itself, in which we are, in particular for our example - one of the values sthat we have chosen when creating this universe. But since we live in a space of quantum experiments, the output will be a set of new universes. Thus, the “continuation” receives a number as input, and generates a list. This is not necessarily a list of numbers, but a list of something that describes the differences between the generated universes from each other.
Well, what's the point of this new approach? This is the link of the choice of the universe to the "continuation". This is the place where all the action takes place. This binding, again, can be expressed as a function. This is a function that receives a list of universes and an “extension” that generates a new list of universes (larger). We will call this function for_each and we will try to write it as generically as possible. We will not assume anything about the types of universes transmitted or generated. We will also make the “continue” type a template parameter and determine the return type using auto and decltype :
template
auto for_each(List lst, F k) -> decltype(k(lst.front()))
{
using B = decltype(k(lst.front()).front());
// ограничения, налагаемые на тип F должны были бы быть выражены с помощью концептов,
// если бы их наконец включили в стандарт языка С++
static_assert(std::is_convertible<
F, std::function(A)>>::value,
"for_each requires a function type List(A)");
List> lstLst = fmap(k, lst);
return concatAll(lstLst);
}
The fmap function is similar to the standard std :: transform - it applies a “continuation” k to each element of the lst list . Since k itself returns a list, the result is a list of lists, lstLst . The concatAll function combines all the elements of all these lists into one large list.
My congratulations! You just looked at the monad. It is called the list monad and can be used, in particular, for modeling non-deterministic processes. The monad is actually defined by two functions. One of them is the above for_each , and here is the second:
templateList yield(A a) { return List (a); }
This is a yield function that returns a list of one item. We use yield at the stage when we have already finished the “multiplication of universes” and get to the point where we want to return a single value. We use it to create a “continuation” containing only one meaning. It represents a lonely boring life, completely predetermined and devoid of any choice.
Later I will rename these functions to mbind and mreturn , since they define the monad in general, and not just the list monad.
Names like for_each and yieldhave a fairly "imperative" sound. This, of course, is because in functional programming monads, in a sense, play the role of an imperative code. But neither for_each nor yield are data structures - they are functions. More precisely, for_each , which sounds and works like a loop, is a higher order function, like fmap , which is used in its implementation. Of course, at some level the code will become imperative - the same fmap can be written recursively or using a loop, but at the top level we only have function declarations. Well, here it is - declarative programming!
There is a significant difference between a loop and a function, like for_each: for_each takes the entire list as an argument, while the loop can generate the necessary values (in our case, integers) on the fly. This is not a problem in a functional language with support for lazy computing, like Haskell - the list will be calculated as needed. Similar behavior can be implemented in C ++ using streams or lazy iterators. I will not do this here because the lists we deal with in this task are relatively short, but you can read more about this approach in this article .
We are not yet ready to write a complete solution to our puzzle, but I will show you a sketch of how it will look. Imagine StateL- this is just a list. Look at the meaning of the big picture:
StateL> solve()
{
StateL sel = &select;
return for_each(sel, [=](int s) {
return for_each(sel, [=](int e) {
return for_each(sel, [=](int n) {
return for_each(sel, [=](int d) {
return for_each(sel, [=](int m) {
return for_each(sel, [=](int o) {
return for_each(sel, [=](int r) {
return for_each(sel, [=](int y) {
return yield_if(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 yield_if(send + more == money, [=]() {
return yield(make_tuple(send, more, money));
});
});
});});});});});});});});
}
The first call to for_each takes a sample of integers, sel (until we think about their uniqueness), and "continue" is a lambda function that takes one integer, s and generates a list of solutions - tuples of three integers. This "continuation", in turn, calls for_each with a selection for the next letter, e, etc.
The innermost “continuation" is a conditional version of the yield function called yield_if . It checks the condition and generates either an empty list or a list consisting of one element - a decision. Inside, it calls yield_if again , which calls the final yield. In this final yield , when it is called (or if it does not work if all the above conditions have not worked), a solution will be generated - a triple of numbers satisfying the condition of the original puzzle. If there are more than one solutions, they will all be added to the resulting list created inside for_each .
In the second part of this series of articles, I will return to the problem of choosing unique numbers and consider the state monad. You can also take a look at the final code on the github .
Task for independent work
- Implement for_each and yield for a vector instead of a list. Use std :: transform instead of fmap
- Using the list monad (or the “vector” modification implemented in the previous step), write a function that will generate the names of all the cells of the chessboard (sets of pairs of characters from 'a' to 'h' - a number from 1 to 8)
- Implement a version of the for_each function (let's call it repeat ), which takes a “continuation” k of type function