Polymorphic function mapping in C++

In 2016, Jonathan Blow published a video demo for his upcoming (but still unreleased) programming language Jai. In it, he does a demo about how the polymorphic solver in the Jai compiler is much better than the C++ version, using a demo of trying to pass a polymorphic function to another polymorphic function without explicitly stating the type as his proof, stating that it might be possible in C++17.

While he is certainly correct that the Jai polymorphic solver is (from the video at least) a lot more powerful than C++'s, as well as significantly better looking (no one likes looking at templates, lets be honest), he's incorrect about not being able to implicitly pass a polymorphic function to another polymorphic function, so long as you use a C++11 compatible compiler.

The secret lies with the decltype specifier introduced in C++11. decltype (and auto, also introduced in C++11) allows us to get the type of an object at compile type without having to specify what the type actually is. This is great for polymorphic functions as we suddenly no longer have to specify any types at all, save that which we pass in.

So using the same example as Jonathan used, a transformative map, we can actually avoid using any specific type specifiers in our program. I'm going to use std::vector<> instead of an array, but the principle is the same.

Let's start by having a polymorphic function to print out our arrays, and our polymorphic incrementer. These will form the backbone which we use to solve our types.

template <typename T>
void print_array(std::vector<T> arr) {
    std::cout << "{ ";
    for (auto t : arr)
        std::cout << t << " ";
    std::cout << "}" << std::endl;
}

template <typename T>
auto incr(T x) -> decltype(x+1) {
    return x + 1;
}

You will notice that while we declare the return type of our incrementer to be auto, we also declare a trailing return type with decltype. This is very similar to what Jonathan attempted, but he tried replacing the auto with just a decltype. In C++11, if you want a type deduced return value, you must state the type of the function to be auto and have a trailing decltype statement (This was relaxed in C++14 to no longer require the trailing decltype, though having the decltype still helps with template deduction on occasion).

template <typename T, typename F, typename R = typename std::result_of<F&&(T&&)>::type>
auto map(std::vector<T> arr, F&& f) -> decltype(std::vector<R>()) {
    std::vector<R> out(arr.size());
    for (long i = 0; i < arr.size(); ++i) {
            out[i] = f(arr[i]);
    }
    return out;
}

Now we can see our map function. Most likely the first thing that you'd notice is the std::result_of<> in the middle of our template declaration. std::result_of<> is another compile time type declaration resolver. It takes a function and its arguments and evaluates what its return type is. We use F&&(T&&) inside std::result_of<> because there are a few quirks with it that we would hit into using F(T), such as discarding cv-qualifiers and automatically adjusting arrays and function types to pointers. If you're using C++17 and above, std::result_of<> no longer exists due to those quirks, and so instead you can use std::invoke_result<F, T>::type, which looks one hell of a lot better.

Finally we come to our test function.

int main() {
    std::vector<long> array = {1, 2, 3, 4, 5};
    print_array(array);
    print_array(map(array, incr));
}

And... it fails to compile. The reason why is that the compiler doesn't know the way in which incr will be used inside of the map function, so it can't infer the function type that we are actually passing. Once again, we can solve this by using a decltype to avoid having to use any nasty types:

int main() {
    std::vector<long> array = {1, 2, 3, 4, 5};
    print_array(array);
    print_array(map(array, incr<decltype(array)::value_type>));
}

If that's too ugly for you, you could declare a macro that does it instead:

#define poly_map(v, f) map(v, f<decltype(v)::value_type>)
int main() {
    std::vector<long> array = {1, 2, 3, 4, 5};
    print_array(array);
    print_array(poly_map(array, incr));
}

But this compiles and works!

> clang++ -std=c++11 template_poly.cpp
> ./a.out
{ 1 2 3 4 5 }
{ 2 3 4 5 6 }

What's more, this actually works with anything that could be considered a function.

It works with normal functions:

long long_incr(long x) { return x+1; }
int main() {
    std::vector<long> array = {1, 2, 3, 4, 5};
    print_array(array);
    print_array(map(array, long_incr));
}

> clang++ -std=c++11 template_poly.cpp
> ./a.out
{ 1 2 3 4 5 }
{ 2 3 4 5 6 }

It works with lambdas:

int main() {
    std::vector<long> array = {1, 2, 3, 4, 5};
    print_array(array);
    print_array(map(array, [](long x) { return x+1; }));
}

> clang++ -std=c++11 template_poly.cpp
> ./a.out
{ 1 2 3 4 5 }
{ 2 3 4 5 6 }

In C++14 you can even replace the long in the lambda declaration with auto, or wrap the polymorphic function so you don't need the poly_map wrap!

int main() {
    std::vector<long> array = {1, 2, 3, 4, 5};
    print_array(array);
    print_array(map(array, [](auto x) { return x+1; }));
}

> clang++ -std=c++14 template_poly.cpp
> ./a.out
{ 1 2 3 4 5 }
{ 2 3 4 5 6 }

It even works with std::binded member functions!

struct Incr {
    long incr(long x) { return x+1; }
};
int main() {
    std::vector<long> array = {1, 2, 3, 4, 5};
    Incr i;
    print_array(array);
    print_array(map(array, std::bind(&Incr::incr, &i, std::placeholders::_1)));
}

> clang++ -std=c++11 template_poly.cpp
> ./a.out
{ 1 2 3 4 5 }
{ 2 3 4 5 6 }

So that's C++11. What does the C++14 or C++17 code look like?

// C++14
template <typename T, typename F, typename R = typename std::result_of<F&&(T&&)>::type>
auto map(std::vector<T> arr, F&& f) {
    std::vector<R> out(arr.size());
    for (long i = 0; i < arr.size(); ++i) {
            out[i] = f(arr[i]);
    }
    return out;
}
// C++17
template <typename T, typename F, typename R = typename std::invoke_result<F, T>::type>
auto map(std::vector<T> arr, F&& f) {
    std::vector<R> out(arr.size());
    for (long i = 0; i < arr.size(); ++i) {
            out[i] = f(arr[i]);
    }
    return out;
}

template <typename T>
auto incr(T x) { return x + 1; }

// and also
auto incr = [](auto x) { return x + 1; }

We've lost our trailing return types and we can now use auto for lambda parameters!

There's also a fun quirk on g++ that allows for auto to be used as a function parameter, even though you're not supposed to until C++20.

auto incr(auto x) { return x + 1; }

You can find the full code of everything used here on my github.

Never underestimate the power of a good template!