Issues applying std::bind recursively on a std::function

Question

Given a function f(x, y, z) we can bind x to 0, getting a function g(y, z) == f(0, y, z). We can continue doing this and get h() = f(0, 1, 2).

In C++ syntax that would be

#include <functional>
#include <iostream>

void foo(int a, long b, short c)
{
    std::cout << a << b << c << std::endl;
}

int main()
{
    std::function<void(int, long, short)> bar1 = foo;
    std::function<void(long, short)> bar2 = std::bind(bar1, 0, std::placeholders::_1, std::placeholders::_2);
    std::function<void(short)> bar3 = std::bind(bar2, 1, std::placeholders::_1);
    std::function<void()> bar4 = std::bind(bar3, 2);

    bar4(); // prints "012"

    return 0;
}

So far so good.

Now say that I want to do the same -- bind the first argument of a function, get the new function back and repeat this process until all arguments are binded -- but generalize it to work not only with a function of 3 arguments as in the C++ example above, but with a function with unknown* number of arguments.

* In C++ there is such thing as variadic arguments and in C++11 there are variadic templates. I'm referring to variadic templates here.

Basically, what I want to be able to do, is to write a function that accepts any std::function and recursively binds the first argument to some value until all arguments are binded and the function can be called.

For the simplicity, let's assume that std::function represents a function taking any integral arguments and returning void.

This code can be considerate to be a generalization of the previous code

#include <functional>
#include <iostream>

// terminating case of recursion
void apply(std::function<void()> fun, int i)
{
    fun();
}

template<class Head, class... Tail>
void apply(std::function<void(Head, Tail...)> f, int i)
{
    std::function<void(Tail...)> g = std::bind(f, i);
    apply<Tail...>(g, ++i);
}

void foo(int a, long b, short c)
{
    std::cout << a << b << c << std::endl;
}

int main()
{
    std::function<void(int, long, short)> bar1 = foo;
    apply<int, long, short>(bar1, 0);

    return 0;
}

This code is great. It is exactly what I want. It doesn't compile.

main.cpp: In instantiation of 'void apply(std::function<void(Head, Tail ...)>, int) [with Head = int; Tail = {long int, short int}]':
main.cpp:24:40:   required from here
main.cpp:12:56: error: conversion from 'std::_Bind_helper<false, std::function<void(int, long int, short int)>&, int&>::type {aka std::_Bind<std::function<void(int, long int, short int)>(int)>}' to non-scalar type 'std::function<void(long int, short int)>' requested                        
      std::function<void(Tail...)> g = std::bind(f, i);
                                                     ^  

The issue is that you can't just leave out std::placeholders in std::bind call like that. They are required, and number of placeholders in std::bind should match the number of non-binded arguments in the function.

If we change line

std::function<void(Tail...)> g = std::bind(f, i);

to

std::function<void(Tail...)> g = std::bind(f, i, std::placeholders::_1, std::placeholders::_2);

we see that it successfully passes through the first apply() call, but gets stuck on the second pass, because during the second pass g needs only one placeholder, while we still have two of them in the std::bind.

main.cpp: In instantiation of 'void apply(std::function<void(Head, Tail ...)>, int) [with Head = long int; Tail = {short int}]':
main.cpp:13:30:   required from 'void apply(std::function<void(Head, Tail ...)>, int) [with Head = int; Tail = {long int, short int}]'
main.cpp:24:40:   required from here
main.cpp:12:102: error: conversion from 'std::_Bind_helper<false, std::function<void(long int, short int)>&, int&, const std::_Placeholder<1>&, const std::_Placeholder<2>&>::type {aka std::_Bind<std::function<void(long int, short int)>(int, std::_Placeholder<1>, std::_Placeholder<2>)>}' to non-scalar type 'std::function<void(short int)>' requested
         std::function<void(Tail...)> g = std::bind(f, i, std::placeholders::_1, std::placeholders::_2);
                                                                                                      ^

There is a way to solve that using regular non-variadic templates, but it introduces a limit on how many arguments std::function can have. For example, this code works only if std::function has 3 or less arguments

(replace apply functions in the previous code on these)

// terminating case
void apply(std::function<void()> fun, int i)
{
    fun();
}

template<class T0>
void apply(std::function<void(T0)> f, int i)
{
    std::function<void()> g = std::bind(f, i);
    apply(g, ++i);
}

template<class T0, class T1>
void apply(std::function<void(T0, T1)> f, int i)
{
    std::function<void(T1)> g = std::bind(f, i, std::placeholders::_1);
    apply<T1>(g, ++i);
}

template<class T0, class T1, class T2>
void apply(std::function<void(T0, T1, T2)> f, int i)
{
    std::function<void(T1, T2)> g = std::bind(f, i, std::placeholders::_1, std::placeholders::_2);
    apply<T1, T2>(g, ++i);
}

But the issue with that code is that I would have to define a new apply function to support std::function with 4 arguments, then the same with 5 arguments, 6 and so on. Not to mention that my goal was to not have any hard-coded limit on the number of arguments. So this is not acceptable. I don't want it to have a limit.

I need to find a way to make the variadic template code (the second code snippet) to work.

If only std::bind didn't require to specify placeholders -- everything would work, but as std::bind currently works, we need to find some way to specify the right number of placeholders.

It might be useful to know that we can find the right number of placeholders to specify with C++11's sizeof...

sizeof...(Tail)

but I couldn't get anything worthwhile out of this fact.

Answer 1

First, stop using bind unless you absolutely need to.

// terminating case of recursion
void apply(std::function<void()> fun, int i) {
  fun();
}
// recursive case:
template<class Head, class... Tail>
void apply(std::function<void(Head, Tail...)> f, int i) {
  // create a one-shot lambda that binds the first argument to `i`:
  auto g = [&](Tail&&...tail) // by universal ref trick, bit fancy
  { return std::move(f)(std::move(i), std::forward<Tail>(tail)...);};
  // recurse:
  apply<Tail...>(g, ++i);
}

next, only type erase if you have to:

// `std::resukt_of` has a design flaw.  `invoke` fixes it:
template<class Sig,class=void>struct invoke{};
template<class Sig>using invoke_t=typename invoke<Sig>::type;

// converts any type to void.  Useful for sfinae, and may be in C++17:
template<class>struct voider{using type=void;};
template<class T>using void_t=typename voider<T>::type;

// implementation of invoke, returns type of calling instance of F
// with Args...
template<class F,class...Args>
struct invoke<F(Args...),
  void_t<decltype(std::declval<F>()(std::declval<Args>()...))>
>{
  using type=decltype(std::declval<F>()(std::declval<Args>()...));
};

// tells you if F(Args...) is a valid expression:
template<class Sig,class=void>struct can_invoke:std::false_type{};
template<class Sig>
struct can_invoke<Sig,void_t<invoke_t<Sig>>>
:std::true_type{};

now we have some machinery, a base case:

// if f() is a valid expression, terminate:
template<class F, class T, class I,
  class=std::enable_if_t<can_invoke<F()>{}>
>
auto apply(F&& f, T&& t, I&&i)->invoke_t<F()>
{
  return std::forward<F>(f)();
}

which says "if we can be invoked, just invoke f.

Next, the recursive case. It relies on C++14 return type deduction:

// if not, build lambda that binds first arg to t, then recurses
// with i(t):
template<class F, class T, class I,
  class=std::enable_if_t<!can_invoke<F()>{}, int>>
>
auto apply(F&& f, T&& t, I&&i)
{
  // variardic auto lambda, C++14 feature, with sfinae support
  // only valid to call once, which is fine, and cannot leave local
  // scope:
  auto g=[&](auto&&...ts) // takes any number of params
  -> invoke_t< F( T, decltype(ts)... ) > // sfinae
  {
    return std::forward<F>(f)(std::forward<T>(t), decltype(ts)(ts)...);
  };
  // recurse:
  return apply(std::move(g), i(t), std::forward<I>(i));
}

If you want increment, pass [](auto&&x){return x+1;} as 3rd arg.

If you want no change, pass [](auto&&x){return x;} as 3rd arg.

None of this code has been compiled, so there may be typos. I am also worried about the recursion of apply with C++14 return type deduction, that gets tricky sometimes.