Elements of functional programming in C ++: mapping compositions

The standard C ++ library is quite good. For many years, the standard algorithms faithfully serve the simple plus sign!

But the whole industry is booming, and the C ++ language with it. For a long time, people began to realize that no matter how good the standard algorithms are, they have a big drawback: zero composability. In other words, it is impossible to combine several transformation, filtering, convolution, etc. algorithms without additional difficulties. etc.

There are several solutions to this problem. One of them - lazy calculations and ranges - is already on the way to the standard library.

However, the good old algorithms are still too early to write off.

In this article I want to consider one of the techniques, which, although not a complete solution to the composability of algorithms, is quite capable of simplifying work with the old standard algorithms, and will definitely come in handy for working with upcoming versions of the C ++ standard.

Content

1. Technique of functional objects
2. Simple composition
3. Multiposition composition
4. Addition
5. Conclusion

Technique of functional objects

Before proceeding directly to the point, I want to touch on the technique that is not yet very widely represented in the current standard library, but it seems to be quite common in STL2, at least in the part that lazy calculations will command and ranges.

If you are an experienced positive, you can safely skip this part.

Are you still here? Then imagine that we have a set of containers, and we face a difficult task: to write the dimensions of all these containers into another container.

We write a function that returns the size of the container:

template <typename Container> constexpr decltype(auto) size (Container & container) { return container.size(); } 

Now, it would seem, nothing prevents to call the standard std::transform algorithm.

 std::vector<std::vector<int>> containers{...}; std::vector<std::size_t> sizes; std::transform(containers.begin(), containers.end(), std::back_inserter(sizes), size); 

But it was not there:

 //  : // // couldn't deduce template parameter '_UnaryOperation' // std::transform(containers.begin(), containers.end(), std::back_inserter(sizes), size); // ^~~~ 

size is a template function. The template function is specified either explicitly (in our case it will be size<std::vector<int>> ), or at the time of the call. And just the size entry does not allow the compiler to understand with which arguments this function will be called.

This problem can be circumvented by declaring size not as a function, but as a functional object :

 struct size_fn { template <typename Container> constexpr decltype(auto) operator () (Container & container) { return container.size(); } }; constexpr auto size = size_fn{}; 

Now there are no more compilation errors:

 std::transform(containers.begin(), containers.end(), std::back_inserter(sizes), size); 

Of course, the experienced positive positive will say that functional objects also have certain disadvantages in comparison with functions. But we will not focus on this now.

Simple composition

So, the technique is mastered, we consider a more complex life example.

Imagine that we need to get all associated values ​​from an associative array. To do this, you can use the algorithm already familiar to us std::transform :

 std::map<std::string, double> m{...}; std::vector<double> r; std::transform(m.begin(), m.end(), std::back_inserter(r), [] (const auto & p) {return p.second;}); 

So far, everything is quite simple. Short and clear lambda function, all is well. But if the mapping logic becomes complicated, the situation will deteriorate dramatically.

For example, you need to take not just the second element of the pair, but calculate the square root of it, and round the result to the nearest integer. Lambda becomes too long, will have to format:

 std::transform(m.begin(), m.end(), std::back_inserter(r), [] (const auto & p) { return std::lround(std::sqrt(p.second)); }); 

On the other hand, our intention could be expressed in a shorter and clearer way:

 std::transform(m.begin(), m.end(), std::back_inserter(r), get<1> | sqrt | lround); 

Attention draws record get<1> | sqrt | lround get<1> | sqrt | lround get<1> | sqrt | lround . This syntax should be understood as follows: take the element of a tuple with index 1, take the square root of it and round it to the nearest integer. Exactly what was required.

Schematically, this can be represented as:

You can implement the get functional object as follows:

 template <std::size_t Index> struct get_fn { template <typename Tuple> constexpr decltype(auto) operator () (Tuple && t) const { using std::get; return get<Index>(std::forward<Tuple>(t)); } }; template <std::size_t Index> constexpr auto get = get_fn<Index>{}; 

lround propose to implement the functional objects sqrt and lround as an exercise for all who are interested.

The very mechanism of the composition is implemented through an appropriate functional object:

 template <typename L, typename R> struct compose_fn { template <typename ... Ts> constexpr decltype(auto) operator () (Ts && ... ts) const & { return l(r(std::forward<Ts>(ts)...)); } template <typename ... Ts> constexpr decltype(auto) operator () (Ts && ... ts) & { return l(r(std::forward<Ts>(ts)...)); } template <typename ... Ts> constexpr decltype(auto) operator () (Ts && ... ts) && { return std::move(l)(std::move(r)(std::forward<Ts>(ts)...)); } L l; R r; }; template <typename L, typename R> constexpr auto compose (L && l, R && r) -> compose_fn<std::decay_t<L>, std::decay_t<R>> { return {std::forward<L>(l), std::forward<R>(r)}; } template <typename ... Ts, typename R> constexpr auto operator | (compose_fn<Ts...> l, R && r) { return compose(std::forward<R>(r), std::move(l)); } 

It is important to note that in this implementation, the compose function applies the composition from right to left, as is customary in mathematics. In other words, compose(f, g)(x) equivalent to f(g(x)) .

The operator changes the order of the composition. That is, (f | g)(x) equivalent to g(f(x)) .

This is done in order not to mislead a programmer who is familiar with solutions such as Boost Range Adapters , range-v3 , and console console.

Multiposition composition

So far everything was easy and understandable. But we will not stop at this.

Suppose we want to sort an array of pairs:

 std::vector<std::pair<int, type_with_no_ordering>> v{...}; 

For the second element of the pair, the order relation is not set (which is clear from its name), so it makes no sense to compare it, moreover, such a comparison simply does not compile. Therefore, the sorting is written as:

 std::sort(v.begin(), v.end(), [] (const auto & l, const auto & r) {return l.first < r.first;}); 

Looks a bit long. You can format for beauty.

 std::sort(v.begin(), v.end(), [] (const auto & l, const auto & r) { return l.first < r.first; }); 

In my opinion, it is more convenient to read, but still quite verbose.

Is it possible to simplify this expression? Let's try to write pseudocode, in which we will express with words what we want to do:

 std::sort(v.begin(), v.end(), ___); 

The action we need — a comparison by the first element — can be divided into two logical steps: taking the first element from each pair and the comparison itself.

To take the first element, create a functional object based on the existing get :

 constexpr auto first = get<0>; 

For the actual comparison, SBSH already has a suitable tool: std::less .

But how to put these functions together? I will try to illustrate the problem.

The std::sort algorithm std::sort expects two objects to be input.

And by itself, std::less satisfies this condition.

At the same time, first is a single function. It takes only one argument. Does not fit:

So we can't just write first | std::less{} first | std::less{} .

At the same time, the result we want to get should look something like this:

That is, we must link this whole block with the std::less function:

If we translate thoughts into code, we want to get the following entry:

 std::sort(v.begin(), v.end(), each(first) | std::less<>{}); 

But it turns out that the function generated by writing each(first) must not only accept, but also return two values ​​at once, in order to submit them to the input std::less . And in C ++, a function cannot return more than one value!

However, there is a solution. It is necessary to implement a special composition scheme for the functional object each .

The functional object itself each is trivial:

 template <typename UnaryFunction> struct each_fn { UnaryFunction f; }; template <typename UnaryFunction> constexpr auto each (UnaryFunction && f) -> each_fn<std::decay_t<UnaryFunction>> { return {std::forward<UnaryFunction>(f)}; } 

It is not even a fully functional object. Rather, it is a special container tag, which, when compositing, will inform the composition engine that the composition of the function stored inside the container should not be performed as usual.

And here are the composition mechanisms themselves:

 template <typename L, typename R> struct each_compose_fn { template <typename ... Ts> constexpr decltype(auto) operator () (Ts && ... ts) const & { return l(r(std::forward<Ts>(ts))...); } template <typename ... Ts> constexpr decltype(auto) operator () (Ts && ... ts) & { return l(r(std::forward<Ts>(ts))...); } template <typename ... Ts> constexpr decltype(auto) operator () (Ts && ... ts) && { return std::move(l)(r(std::forward<Ts>(ts))...); } L l; R r; }; template <typename UnaryFunction1, typename UnaryFunction2> constexpr auto compose (each_fn<UnaryFunction1> l, each_fn<UnaryFunction2> r) -> each_fn<decltype(compose(lf, rf))> { return {compose(std::move(lf), std::move(rf))}; } template <typename L, typename UnaryFunction> constexpr auto compose (L && l, each_fn<UnaryFunction> r) -> each_compose_fn<std::decay_t<L>, UnaryFunction> { return {std::forward<L>(l), std::move(rf)}; } template <typename UnaryFunction, typename R> constexpr auto operator | (each_fn<UnaryFunction> l, R && r) { return compose(std::forward<R>(r), std::move(l)); } 

The main difference from the usual composition - in the disclosure of the list of arguments.
In the compose function, the expansion is as follows: l(r(args...)) , and in each_compose , otherwise: l(r(args)...) .

In other words, in the first case, a single place function is applied to the result of a multi-place function, and in the second case, a multi-place function is applied to the results of applying a single place function to each of the input parameters.

Now we can compose multi-seat functions with single:

 std::sort(v.begin(), v.end(), each(first) | std::less<>{}); std::lower_bound(v.begin(), v.end(), x, each(second) | std::greater<>{}); //  .. 

This is victory.

Addition

Many will note that it is too expensive to implement for each function, each property of an object, etc. separate functional object. And this is impossible to disagree. For example, in one of the examples above, it would be more convenient not to implement new functional objects for the lround and sqrt functions, but to use the existing library ones.

There is even if imperfect, but the working solution to this problem - drumming - macros.

For example, to call a member function of a class, a macro can be implemented like this:

 #define MEM_FN(f)\ [] (auto && x, auto && ... args)\ -> decltype(auto)\ {\ return std::forward<decltype(x)>(x).f(std::forward<decltype(args)>(args)...);\ } 

It will be used as follows:

 std::vector<std::vector<int>> containers{...}; std::none_of(containers.begin(), containers.end(), MEM_FN(empty)); 

Similar macros can be implemented to call free functions:

 #define FN(f)\ [] (auto && ... args)\ -> decltype(auto)\ {\ return f(std::forward<decltype(args)>(args)...);\ } 

And even for access to class members:

 #define MEMBER(m)\ [] (auto && x)\ -> decltype(auto)\ {\ /*   ,      */\ /*   */\ return (std::forward<decltype(x)>(x).m);\ } struct Class { int x; }; std::vector<Class> v{...}; std::remove_if(v.begin(), v.end(), MEMBER(x) | equal_to(5)); 

The code is prompted in places so as not to introduce too many new entities.

Conclusion

What is all this for? Why not just use lambdas?

Ljubda can use and need. But, unfortunately, lambdas often generate a lot of duplicate code. It happens that the lambda completely repeat each other. It happens that a few lambdas differ quite a bit, but they are not amenable to decomposition.

The approach described in this article allows you to assemble simple lambda from the "cubes", reducing the amount of hand-written code and, consequently, reducing the chance of making a mistake when writing the next lambda.

Although this approach can work independently, it is intended primarily to simplify work with algorithms and ranges.

Full code with all the details .

Links

1. Boost Range Adapters
2. Ranges for the Standard Library
3. atria :: xform

To top