Is there a type std :: function or similar for a lambda with an automatic parameter?

Question

When I assign a lambda to an explicitly typed variable (for example, when it is recursive to capture this function itself), I use std::function .

Consider this stupid “bit counting” function as an example:

 std::function<int(int)> f; f = [&f](int x){ return x ? f(x/2)+1 : 0; }; 

How about when we use an automatic parameter to generalize x , as was introduced in C ++ 14 generic lambda?

 std::function<int(???)> f; f = [&f](auto x){ return x ? f(x/2)+1 : 0; }; 

Obviously, I cannot place auto in parameters of type function .

Is it possible to define a functor class common enough to cover the exact case above, but still using lambda to define the function?

(Do not override this, accept only one automatic parameter and adjust the return value.) The use case will be for a scenario similar to the one described above: capturing the function itself by reference for recursive calls.

Answer 1

You can create a lambda that calls itself by passing it to itself as a parameter:

 auto f = [](auto self, auto x) -> int { return x ? self(self, x / 2) + 1 : 0; }; std::cout << f(f, 10); 

You can then capture this lambda into another lambda, so you don't need to worry about passing it to yourself:

 auto f2 = [&f](auto x) { return f(f, x); }; std::cout << f2(10); 

Answer 2

Here is the fast y-combinator recursive engine:

 template<class F> struct recursive_t { F f; // note Self must be an lvalue reference. Things get // strange if it is an rvalue: // invoke makes recursive ADL work a touch better. template<class Self, class...Args> friend auto invoke( Self& self, Args&&...args ) -> decltype( self.f( self, std::declval<Args>()... ) ) { return self.f( self, std::forward<Args>(args)... ); } // calculate return type using `invoke` above: template<class Self, class...Args> using R = decltype( invoke( std::declval<Self>(), std::declval<Args>()... ) ); template<class...Args> R<recursive_t&, Args...> operator()(Args&&...args) { return invoke( *this, std::forward<Args>(args)... ); } template<class...Args> R<recursive_t const&, Args...> operator()(Args&&...args)const { return invoke( *this, std::forward<Args>(args)... ); } }; template<class F> recursive_t< std::decay_t<F> > recurse( F&& f ) { return {std::forward<F>(f)}; } 

now you can do:

 auto f = recurse( [](auto&& f, auto x){ return x ? f(x/2)+1 : 0; } ); 

and you get a recursive lambda that has no capture & (which limits its use to the current area).

Capturing std::function by reference means that your lambda lifetime is the current area, and each recursive call requires iterative overwriting of the type (blocking any possible optimizations, such as tail recursion, from the recursive call). The same applies to other similar solutions.

Using recursive_t is required, not using lambda, because lambda cannot call itself.

Living example .

The lambda-based version is somewhat easier to implement. Note that you will need another type function for mutable and immutable lambdas:

 template<class F> auto recurse( F&& f ) { return [f=std::forward<F>(f)](auto&&...args){ return f(f, decltype(args)(args)...); }; }; 

recursive_t works like:

 auto fib = recurse( [](auto&& fib, int x){ if (x<2) return 1; return fib(x-1)+fib(x-2); } ); 

lambda version works like:

 auto fib = recurse( [](auto&& self, int x){ if (x<2) return 1; return self(self, x-1)+self(self,x-2); } ); 

which I personally find more uncomfortable.

It is also more difficult to describe the recurse type. For the recursive_t version, recurse is of type:

 ((A->B)->A->B)->(A->B) 

which is inconvenient, but the final type.

The lambda version is more complicated. The argument type of the recursive function is of the type:

 F:= F->A->B 

which is annoyingly endless and then recurse is of type

 F->A->(A->B) 

which inherits infinity.

In any case, the return value of recurse can be stored in the ordinary std::function or not stored in the container deleted by the type.