3
\$\begingroup\$

This is a follow-up question for A recursive_transform for std::vector with various return type, A recursive_transform Template Function with Execution Policy, A recursive_count_if Template Function with Execution Policy in C++, Avoiding requires clause if possible on a series recursive function in C++ and A recursive_count_if Function with Automatic Type Deducing from Lambda for Various Type Arbitrary Nested Iterable Implementation in C++. The standard concept std::invocable is mentioned in the previous G. Sliepen's answer and I am trying to use std::invocable concept in recursive_transform template function. In this way, the termination condition can be determined with the input lambda function. Maybe recursive_transform is more generic here.

The experimental implementation

//  recursive_transform implementation
template<class T, std::invocable<T> F>
constexpr auto recursive_transform(const T& input, const F& f)
{
    return f(input);
}

//  specific case for std::array
template<class T, std::size_t S, class F>
constexpr auto recursive_transform(const std::array<T, S>& input, const F& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));

    std::array<TransformedValueType, S> output;
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [f](auto&& element)
        {
            return recursive_transform(element, f);
        }
    );
    return output;
}

template<template<class...> class Container, class Function, class... Ts>
requires (is_inserterable<Container<Ts...>> && !std::invocable<Function, Container<Ts...>>)
constexpr auto recursive_transform(const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));
    Container<TransformedValueType> output;

    std::transform(input.cbegin(), input.cend(), std::inserter(output, std::ranges::end(output)),
        [&](auto&& element)
        {
            return recursive_transform(element, f);
        }
    );

    return output;
}

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<is_multi_array T, class F>
requires(!std::invocable<F, T>)
constexpr auto recursive_transform(const T& input, const F& f)
{
    boost::multi_array output(input);
    for (decltype(+input.shape()[0]) i = 0; i < input.shape()[0]; i++)
    {
        output[i] = recursive_transform(input[i], f);
    }
    return output;
}
#endif

Test cases

Because of the usage of std::invocable, the termination condition is more flexible instead of simply the base type of nested ranges. In other words, we can play this version of recursive_transform function with recursive_count_if function like this:

//  std::vector<int> -> std::vector<std::string>
std::vector<int> test_vector = {
    1, 2, 3
};
std::cout << "string: " + recursive_transform(test_vector, [](int x)->std::string { return std::to_string(x); }).at(0) << std::endl;


//  std::vector<std::vector<int>> -> std::vector<std::vector<std::string>>
std::vector<decltype(test_vector)> test_vector2 = {
    test_vector, test_vector, test_vector
};
std::cout << "string: " + recursive_transform(test_vector2, [](int x)->std::string { return std::to_string(x); }).at(0).at(0) << std::endl;

//std::vector<std::vector<int>> -> std::vector<std::size_t>
std::cout << "recursive_count_if: " + recursive_transform(test_vector2, [](std::vector<int> x) {
    return std::to_string(recursive_count_if(x, [](int number) { return number == 3; }));
    }).at(0) << std::endl;

The full testing code:

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <complex>
#include <concepts>
#include <deque>
#include <exception>
#include <execution>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <optional>
#include <ranges>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

template<typename T>
concept is_inserterable = requires(T x)
{
    std::inserter(x, std::ranges::end(x));
};

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<typename T>
concept is_multi_array = requires(T x)
{
    x.num_dimensions();
    x.shape();
    boost::multi_array(x);
};
#endif

//  recursive_count implementation
template<std::ranges::input_range Range, typename T>
constexpr auto recursive_count(const Range& input, const T& target)
{
    return std::count(input.cbegin(), input.cend(), target);
}

//  transform_reduce version
template<std::ranges::input_range Range, typename T>
requires std::ranges::input_range<std::ranges::range_value_t<Range>>
constexpr auto recursive_count(const Range& input, const T& target)
{
    return std::transform_reduce(std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [target](auto&& element) {
        return recursive_count(element, target);
        });
}

//  recursive_count implementation (with execution policy)
template<class ExPo, std::ranges::input_range Range, typename T>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr auto recursive_count(ExPo execution_policy, const Range& input, const T& target)
{
    return std::count(execution_policy, input.cbegin(), input.cend(), target);
}

template<class ExPo, std::ranges::input_range Range, typename T>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (std::ranges::input_range<std::ranges::range_value_t<Range>>)
constexpr auto recursive_count(ExPo execution_policy, const Range& input, const T& target)
{
    return std::transform_reduce(execution_policy, std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [execution_policy, target](auto&& element) {
        return recursive_count(execution_policy, element, target);
        });
}

//  recursive_count_if implementation
template<class T, std::invocable<T> Pred>
constexpr std::size_t recursive_count_if(const T& input, const Pred& predicate)
{
    return predicate(input) ? 1 : 0;
}

template<std::ranges::input_range Range, class Pred>
requires (!std::invocable<Pred, Range>)
constexpr auto recursive_count_if(const Range& input, const Pred& predicate)
{
    return std::transform_reduce(std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if(element, predicate);
    });
}

//  recursive_count_if implementation (with execution policy)
template<class ExPo, class T, std::invocable<T> Pred>
requires (std::is_execution_policy_v<std::remove_cvref_t<ExPo>>)
constexpr std::size_t recursive_count_if(ExPo execution_policy, const T& input, const Pred& predicate)
{
    return predicate(input) ? 1 : 0;
}

template<class ExPo, std::ranges::input_range Range, class Pred>
requires ((std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (!std::invocable<Pred, Range>))
constexpr auto recursive_count_if(ExPo execution_policy, const Range& input, const Pred& predicate)
{
    return std::transform_reduce(execution_policy, std::cbegin(input), std::cend(input), std::size_t{}, std::plus<std::size_t>(), [predicate](auto&& element) {
        return recursive_count_if(element, predicate);
    });
}

//  recursive_transform implementation
template<class T, std::invocable<T> F>
constexpr auto recursive_transform(const T& input, const F& f)
{
    return f(input);
}

//  specific case for std::array
template<class T, std::size_t S, class F>
constexpr auto recursive_transform(const std::array<T, S>& input, const F& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));

    std::array<TransformedValueType, S> output;
    std::transform(input.cbegin(), input.cend(), output.begin(), 
        [f](auto&& element)
        {
            return recursive_transform(element, f);
        }
    );
    return output;
}

template<template<class...> class Container, class Function, class... Ts>
requires (is_inserterable<Container<Ts...>> && !std::invocable<Function, Container<Ts...>>)
constexpr auto recursive_transform(const Container<Ts...>& input, const Function& f)
{
    using TransformedValueType = decltype(recursive_transform(*input.cbegin(), f));
    Container<TransformedValueType> output;

    std::transform(input.cbegin(), input.cend(), std::inserter(output, std::ranges::end(output)),
        [&](auto&& element)
        {
            return recursive_transform(element, f);
        }
    );

    return output;
}

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template<is_multi_array T, class F>
requires(!std::invocable<F, T>)
constexpr auto recursive_transform(const T& input, const F& f)
{
    boost::multi_array output(input);
    for (decltype(+input.shape()[0]) i = 0; i < input.shape()[0]; i++)
    {
        output[i] = recursive_transform(input[i], f);
    }
    return output;
}
#endif

template<std::size_t dim, class T>
constexpr auto n_dim_vector_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_vector_generator<dim - 1>(input, times);
        std::vector<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, std::size_t times, class T>
constexpr auto n_dim_array_generator(T input)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_array_generator<dim - 1, times>(input);
        std::array<decltype(element), times> output;
        std::fill(std::begin(output), std::end(output), element);
        return output;
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_deque_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_deque_generator<dim - 1>(input, times);
        std::deque<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, class T>
constexpr auto n_dim_list_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        auto element = n_dim_list_generator<dim - 1>(input, times);
        std::list<decltype(element)> output(times, element);
        return output;
    }
}

template<std::size_t dim, template<class...> class Container = std::vector, class T>
constexpr auto n_dim_container_generator(T input, std::size_t times)
{
    if constexpr (dim == 0)
    {
        return input;
    }
    else
    {
        return Container(times, n_dim_container_generator<dim - 1, Container, T>(input, times));
    }
}

int main()
{
    //  std::vector<int> -> std::vector<std::string>
    std::vector<int> test_vector = {
        1, 2, 3
    };
    std::cout << "string: " + recursive_transform(test_vector, [](int x)->std::string { return std::to_string(x); }).at(0) << std::endl;


    //  std::vector<std::vector<int>> -> std::vector<std::vector<std::string>>
    std::vector<decltype(test_vector)> test_vector2 = {
        test_vector, test_vector, test_vector
    };
    std::cout << "string: " + recursive_transform(test_vector2, [](int x)->std::string { return std::to_string(x); }).at(0).at(0) << std::endl;

    //std::vector<std::vector<int>> -> std::vector<std::size_t>
    std::cout << "recursive_count_if: " + recursive_transform(test_vector2, [](std::vector<int> x) {
        return std::to_string(recursive_count_if(x, [](int number) { return number == 3; }));
        }).at(0) << std::endl;

    //  std::deque<int> -> std::deque<std::string>
    std::deque<int> test_deque;
    test_deque.push_back(1);
    test_deque.push_back(1);
    test_deque.push_back(1);

    auto recursive_transform_result3 = recursive_transform(
        test_deque,
        [](int x)->std::string { return std::to_string(x); });                          //  For testing
    std::cout << "string: " + recursive_transform_result3.at(0) << std::endl;


    //  std::deque<std::deque<int>> -> std::deque<std::deque<std::string>>
    std::deque<decltype(test_deque)> test_deque2;
    test_deque2.push_back(test_deque);
    test_deque2.push_back(test_deque);
    test_deque2.push_back(test_deque);

    auto recursive_transform_result4 = recursive_transform(
        test_deque2,
        [](int x)->std::string { return std::to_string(x); });                          //  For testing
    std::cout << "string: " + recursive_transform_result4.at(0).at(0) << std::endl;


    //  std::array<int, 10> -> std::array<std::string, 10>
    std::array<int, 10> test_array;
    for (int i = 0; i < 10; i++)
    {
        test_array[i] = 1;
    }
    auto recursive_transform_result5 = recursive_transform(
        test_array,
        [](int x)->std::string { return std::to_string(x); });                          //  For testing
    std::cout << "string: " + recursive_transform_result5.at(0) << std::endl;

    //  std::array<std::array<int, 10>, 10> -> std::array<std::array<std::string, 10>, 10>
    std::array<std::array<int, 10>, 10> test_array2;
    for (int i = 0; i < 10; i++)
    {
        test_array2[i] = test_array;
    }
    auto recursive_transform_result6 = recursive_transform(
        test_array2,
        [](int x)->std::string { return std::to_string(x); });                          //  For testing
    std::cout << "string: " + recursive_transform_result6.at(0).at(0) << std::endl;


    //  std::list<int> -> std::list<std::string>
    std::list<int> test_list = { 1, 2, 3, 4 };
    auto recursive_transform_result7 = recursive_transform(
        test_list,
        [](int x)->std::string { return std::to_string(x); });                          //  For testing
    std::cout << "string: " + recursive_transform_result7.front() << std::endl;


    //  std::list<std::list<int>> -> std::list<std::list<std::string>>
    std::list<std::list<int>> test_list2 = { test_list, test_list, test_list, test_list };
    auto recursive_transform_result8 = recursive_transform(
        test_list2,
        [](int x)->std::string { return std::to_string(x); });                          //  For testing
    std::cout << "string: " + recursive_transform_result8.front().front() << std::endl;

    return 0;
}

A Godbolt link is here.

All suggestions are welcome.

The summary information:

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @G.Sliepen Thank you for the comments. Already updated :) \$\endgroup\$
    – JimmyHu
    Commented Dec 17, 2020 at 21:50

1 Answer 1

Reset to default
1
\$\begingroup\$

I’m going to suggest a completely different way of approaching this problem. It will involve a bit more code, and a bit more complexity, but in exchange, it will (I hope) make recursive_transform() much easier to reason about, and test.

The primary reason I think refactoring recursive_transform() is a good idea is because right now you have 4 functions (3 + 1 conditionally defined), all of which are basically identical except for the first one. All of them are essentially this:

template <
    std::ranges::input_range Range,
    something_something_recursively_indirectly_unary_invocable<std::ranges::iterator_t<Range>> F>
constexpr auto recursive_transform(Range&& input, F&& f)
{
    auto output = something_something_result_t<Range, F>{};

    auto out = something_something_get_output_iterator(output);

    std::ranges::transform(
        std::forward<Range>(input),
        out,
        [&f](auto&& element) { return recursive_transform(element, f); }
    );

    return output;
}

And the only “tricky” parts that vary between the functions are:

  1. the something_something_recursively_indirectly_unary_invocable concept
  2. the something_something_result_type type trait; and
  3. the something_something_get_output_iterator function.

The latter two are pretty easy to figure out. The first will take a bit more work—at a single level of recursion it’s just indirectly_unary_invocable<ranges::iterator_t<Range>>, but we need a recursive version. But I think that’s all worth doing, because it means that all you’d need for recursive_transform() is the function above and the non-range one you’ve already written:

template <typename T, std::invocable<T> F>
constexpr auto recursive_transform(const T& input, const F& f)
{
    return f(input);
}

That’s 2 functions instead of 4, and you no longer need the preprocessor.

With F properly constrained in the range version, this should work for all possible arguments:

  1. If input is not an input range, it will always select the non-range overload. In that case, if f is not a function or it can’t handle the type of input, you get a compile error.
  2. If input is an input range, it will check f next:
    1. If f works with the elements of the input range or the elements of the elements of the input range or… and so on, recursively… then it will select the range overload.
    2. Otherwise, if f works with the entire input range (for example if you did something like recursive_transform("123"s, std::stoi), which should return int{123}), then it will select the non-range overload.
    3. Otherwise, you get a compile error, because f won’t work with input or its elements (recursively) at all.

Let’s look at those 3 “tricky”, starting with the easiest.

something_something_result_t<Range, F>

In your existing 3 functions, the result types are as follows:

Template parameters decltype(input) Result
<class T, std::size_t S> array<T, S> array<R, S>
<template<class...> class Container, class... Ts> Container<Ts> Container<R>
<class T> boost::multi_array<T::element, N> boost::multi_array<T::element, N>

And your type trait pretty much writes itself:

template <typename F, typename T>
struct something_something_result;

template <typename F, typename T, std::size_t S>
struct something_something_result<std::array<T, S>, F>
{
    using type = std:::array<
        std::indirect_result_t<F, std::iterator_t<std::array<T, S>>>,
        S
    >;
};

template <typename F, template <typename...> typename Container, typename... Ts>
struct something_something_result<Container<Ts...>, F>
{
    using type = Container<
        something_something_recursively_indirect_result_t<
            F,
            std::iterator_t<Container<Ts...>>
        >
    >;
};

#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
template <typename F, typename U, std::size_t Dims>
struct something_something_result<boost::multi_array<U, Dims>>
{
    using type = boost::multi_array<std::invoke_result_t<F, U>,  Dims>;
};
#endif // USE_BOOST_MULTIDIMENSIONAL_ARRAY

template <typename... Args>
using something_something_result_t =
    typename something_something_result<Args...>::type;

All you need now is that something_something_recursively_indirect_result_t<F, I> type trait, which is just:

  1. indirect_result_t<F, I> if that exists; or
  2. indirect_result_t<F, iterator_t<iter_reference_t<I>> recursively, otherwise.

which is trivial to implement with std::indirectly_unary_invocable.

And once you have that…

something_something_recursively_indirectly_unary_invocable<F, I>

… this concept is just:

template <typename F, typename I>
concept something_something_recursively_indirectly_unary_invocable =
    requires
    {
        typename something_something_recursively_indirect_result<F, I>::type;
    };

And finally…

something_something_get_output_iterator(Range&)

This is just a function template, and you can vary what it does depending on the type of the output range given using a number of different techniques. For example:

template <std::ranges::output_range Range>
constexpr auto something_something_get_output_iterator(Range& output)
{
    // If it's a std::array...
    if constexpr (is_array_v<Range>)
        return output.begin();
#ifdef USE_BOOST_MULTIDIMENSIONAL_ARRAY
    // If it's a boost::multi_array
    else if constexpr (is_boost_multi_array_v<Range>)
        return output.data();
#endif // USE_BOOST_MULTIDIMENSIONAL_ARRAY
    else
        return std::inserter(output, std::ranges::end(output));
}

You could even be clever and do things like also taking the input range as an argument, and then if ranges::size(input) and output.reserve(size) are both valid expressions (such as for std::vector), you can do output.reserve(std::ranges::size()); return output.begin();.

(You might also need to take input as an argument, if you need it to properly set up boost::multi_array with the right dimensions and sizes. I’ve never used it, so I don’t know how it works.)

The bigger picture

Obviously names like something_something_* are silly, but you could replace the something_something_ with a detail namespace.

HOWEVER…

Some of the traits we needed to make all this work are actually useful in their own right. recursively_indirect_result<F, I> seems particularly useful, as does stuff like recursively_indirectly_unary_invocable<F, I>. With those, the entirety of recursive_transform() could be:

template <typename T, std::invocable<T> F>
constexpr auto recursive_transform(T&& input, F&& f)
{
    return f(std::forward<T>(input));
}

template <std::input_range Range, recursively_indirectly_unary_invocable<std::iterator_t<Range>> F>
constexpr auto recursive_transform(Range&& input, F&& f)
{
    auto output = detail_::recursive_transform_result_type_t<Range&&, F&&>{};

    std::ranges::transform(
        std::forward<Range>(input),
        detail_::get_output_iterator(output),
        [&f](auto&& x) { return recursive_transform(x, f); }
    );

    return output;
}

… and all the special-case messiness is hidden in the detail_ namespace.

As a side benefit, if you want to support more special cases (for example, adding that optimization where it’s possible to do output.reserve(ranges.size(input))), those all become implementation details, and don’t require yet-another overload of recursive_transform() that isn’t really necessary because it doesn’t actually change the behaviour of recursive_transform().

Yet another side benefit is that it will make everything much easier to test. You can test the type traits and concepts independently from the actual algorithm… which is a good thing, because they’re not actually part of the algorithm. And, again, as you add more special cases (which, unfortunately, you kinda need since you’re creating the output container internally), you can test those independently of the actual algorithm, and everything will Just Work when you use those special-case container types with the algorithm. (If you don’t test all those special cases separately, then every time you add a new overload, you need a whole new suite of tests for it (such as when it’s empty, when you use a function that moves from the input container, etc., etc.).)

So I’d recommend creating the following:

Type Name Description
Type trait recursively_indirect_result<F, I> Same as std::indirect_result_t<F, I> if that has a type member. Otherwise, std::indirect_result_t<F, std::ranges::iterator_t<std::iter_reference_t<I>>.
Type alias recursively_indirect_result_t<F, I> Just recursively_indirect_result<F, I>::type.
Concept recursively_indirectly_unary_invocable<F, I> You could define this a number of ways, all with pros and cons. The easiest way would probably be to just check for type in recursively_indirect_result<F, I>, but you could also put together a is_recursively_indirectly_invocable<F, I> type trait and use that.

… and adding a detail namespace with a type trait to generate the result type of a recursive transform, and a helper function to get an output iterator to write to that result. Then recursive_transform() simplifies to the two functions above. (You could even further simplify it to one function, using if constexpr, but that seems excessive since the two overloads do conceptually different things.)

Other minor nitpicks

You take the transform function by const&, but you’ll note that I use forwarding references. This isn’t just a matter of taste. If you force the function to be const, then you can’t use anything that doesn’t have a const operator(). Similar logic applies for taking input by const&; that prevents you from doing anything that might mutate the input, including moving the elements out while you’re transforming them.

For example, this won’t work if either input or f has to be const:

struct transform_and_count
{
    auto count = std::size_t{0};

    auto operator()(std::string& d)
    {
        ++count;
        return transform(std::move(d));
    }
};

auto get_input() -> std::forward_list<std::string>;

auto transform_counter = transform_and_count{};
auto result = recursive_transform(get_input(), transform_counter);

// Now all the strings have been transformed and moved into result, with no
// unnecessary copies. And the number of strings is in the counter's count
// member, so we don't need to traverse the forward list a second time to
// find out how many strings we have.

Your test cases don’t catch this issue because they all use lamdas—which have const operator() functions by default (though you can change that by using mutable)—and because none of them do anything that require non-const elements.

This also means you don’t want to be using cbegin() and cend().

Also, it’s probably a typo, but you’re copying f in the std::array overload.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.