2
\$\begingroup\$

This is a follow-up question for A population_variance Function For Various Type Arbitrary Nested Iterable Implementation in C++. Thanks to G. Sliepen's answer, I am trying to implement the mentioned recursive_transform_reduce function here.

The usage description

Similar to std::transform_reduce, the purpose of recursive_transform_reduce function is to apply a function (unary operation) to each element in the given range then reduce the results with a binary operation. There are four parameters in recursive_transform_reduce function (the version without execution policy). The first one is a input range, the second one is the initial value of reduction result, the third one is a function (unary operation) which is to apply to each element and the final one is a binary operation for reduction operation.

The experimental implementation

The experimental implementation of recursive_transform_reduce template function is as below.

//  recursive_transform_reduce implementation
template<class Container, class ValueType, class UnaryOp, class BinaryOp = std::plus<ValueType>>
requires (std::ranges::range<Container>) && (!is_elements_iterable<Container>)
constexpr auto recursive_transform_reduce(const Container& input, ValueType init, const UnaryOp& unary_op, const BinaryOp& binop = std::plus<ValueType>())
{
    for (const auto& element : input) {
        auto result = unary_op(element);
        init = binop(init, result);
    }
    return init;
}

template<class Container, class ValueType, class UnaryOp, class BinaryOp = std::plus<ValueType>>
requires (std::ranges::range<Container>) && (is_elements_iterable<Container>)
constexpr auto recursive_transform_reduce(const Container& input, ValueType init, const UnaryOp& unary_op, const BinaryOp& binop = std::plus<ValueType>())
{
    return std::transform_reduce(std::begin(input), std::end(input), init, binop, [&](auto& element) {
        return recursive_transform_reduce(element, init, unary_op, binop);
        });
}

//  With execution policy
template<class ExPo, class Container, class ValueType, class UnaryOp, class BinaryOp = std::plus<ValueType>>
requires ((std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (std::ranges::range<Container>) && (!is_elements_iterable<Container>))
constexpr auto recursive_transform_reduce(ExPo execution_policy, const Container& input, ValueType init, const UnaryOp& unary_op, const BinaryOp& binop = std::plus<ValueType>())
{
    for (const auto& element : input) {
        auto result = unary_op(element);
        init = binop(init, result);
    }
    return init;
}

template<class ExPo, class Container, class ValueType, class UnaryOp, class BinaryOp = std::plus<ValueType>>
requires ((std::is_execution_policy_v<std::remove_cvref_t<ExPo>>) && (std::ranges::range<Container>) && (is_elements_iterable<Container>))
constexpr auto recursive_transform_reduce(ExPo execution_policy, const Container& input, ValueType init, const UnaryOp& unary_op, const BinaryOp& binop = std::plus<ValueType>())
{
    return std::transform_reduce(execution_policy, std::begin(input), std::end(input), init, binop, [&](auto& element) {
        return recursive_transform_reduce(execution_policy, element, init, unary_op, binop);
        });
}

Test cases

With recursive_transform_reduce function here, population_variance function in the previous question can be improved as below.

template<typename T>
concept can_calculate_variance_of = requires(const T & value)
{
    (std::pow(value, 2) - value) / std::size_t{ 1 };
};

template<typename T>
struct recursive_iter_value_t_detail
{
    using type = T;
};

template <std::ranges::range T>
struct recursive_iter_value_t_detail<T>
    : recursive_iter_value_t_detail<std::iter_value_t<T>>
{ };

template<typename T>
using recursive_iter_value_t = typename recursive_iter_value_t_detail<T>::type;

//  population_variance function implementation (with recursive_transform_reduce template function)
template<class T = double, class Container>
requires (is_recursive_sizeable<Container>&& can_calculate_variance_of<recursive_iter_value_t<Container>>)
auto population_variance(const Container& input)
{
    auto mean = arithmetic_mean<T>(input);
    return recursive_transform_reduce(std::execution::par,
        input, T{}, [mean](auto& element) {
        return std::pow(element - mean, 2);
        }, std::plus<T>()) / recursive_size(input);
}

Note: recursive_iter_value_t is referred from How to solve requires clause is incompatible.

The improved version of arithmetic_mean function implementation:

template<typename T>
concept is_recursive_reduceable = requires(T x)
{
    recursive_reduce(x, T{});
};

template<typename T>
concept is_recursive_sizeable = requires(T x)
{
    recursive_size(x);
};

template<class T = double, class Container> requires (is_recursive_sizeable<Container>)
auto arithmetic_mean(const Container& input)
{
    return (recursive_reduce(input, T{})) / (recursive_size(input));
}

The implementation of recursive_reduce function:

template<class T, class ValueType, class Function = std::plus<ValueType>>
auto recursive_reduce(const T& input, ValueType init, const Function& f)
{
    return f(init, input);
}

template<class Container, class ValueType, class Function = std::plus<ValueType>>
requires is_iterable<Container>
auto recursive_reduce(const Container& input, ValueType init, const Function& f = std::plus<ValueType>())
{
    for (const auto& element : input) {
        auto result = recursive_reduce(element, ValueType{}, f);
        init = f(init, result);
    }

    return init;
}

The recursive_size function implementation:

//  recursive_size implementation
template<class T> requires (!std::ranges::range<T>)
auto recursive_size(const T& input)
{
    return 1;
}

template<class T> requires (!is_elements_iterable<T> && std::ranges::range<T>)
auto recursive_size(const T& input)
{
    return input.size();
}

template<class T> requires (is_elements_iterable<T>)
auto recursive_size(const T& input)
{
    return std::transform_reduce(std::begin(input), std::end(input), std::size_t{}, std::plus<std::size_t>(), [](auto& element) {
        return recursive_size(element);
        });
}

The test of population_variance function is like:

std::vector<double> test_vector{ 1, 2, 3, 4, 5 };
std::cout << "recursive_size of test_vector: " << recursive_size(test_vector) << std::endl;
std::cout << "population_variance of test_vector: " << population_variance(test_vector) << std::endl;

//  std::vector<std::vector<double>> case
std::vector<decltype(test_vector)> test_vector2;
test_vector2.push_back(test_vector);
test_vector2.push_back(test_vector);
test_vector2.push_back(test_vector);

std::cout << "recursive_size of test_vector2: " << recursive_size(test_vector2) << std::endl;
std::cout << "population_variance of test_vector2: " << population_variance(test_vector2) << std::endl;

auto test_vector3 = n_dim_container_generator<10, std::vector, decltype(test_vector)>(test_vector, 3);
std::cout << "recursive_size of test_vector3: " << recursive_size(test_vector3) << std::endl;
std::cout << "population_variance of test_vector3: " << population_variance(test_vector3) << std::endl;

Then, the execution output:

recursive_size of test_vector: 5
population_variance of test_vector: 2
recursive_size of test_vector2: 15
population_variance of test_vector2: 2
recursive_size of test_vector3: 295245
population_variance of test_vector3: 2

Another test of population_variance function:

std::vector<double> test_vector{ 1, 2, 3 };
std::cout << "recursive_size of test_vector: " << recursive_size(test_vector) << std::endl;
std::cout << "population_variance of test_vector: " << population_variance(test_vector) << std::endl;

//  std::vector<std::vector<double>> case
std::vector<decltype(test_vector)> test_vector2;
test_vector2.push_back(test_vector);
test_vector2.push_back(test_vector);
test_vector2.push_back(test_vector);

std::cout << "recursive_size of test_vector2: " << recursive_size(test_vector2) << std::endl;
std::cout << "population_variance of test_vector2: " << population_variance(test_vector2) << std::endl;

auto test_vector3 = n_dim_container_generator<10, std::vector, decltype(test_vector)>(test_vector, 3);
std::cout << "recursive_size of test_vector3: " << recursive_size(test_vector3) << std::endl;
std::cout << "population_variance of test_vector3: " << population_variance(test_vector3) << std::endl;

The execution output of the above test code:

recursive_size of test_vector: 3
population_variance of test_vector: 0.666667
recursive_size of test_vector2: 9
population_variance of test_vector2: 0.666667
recursive_size of test_vector3: 177147
population_variance of test_vector3: 0.666667

A Godbolt link is here.

All suggestions are welcome.

The summary information:

  • Which question it is a follow-up to?

    A population_variance Function For Various Type Arbitrary Nested Iterable Implementation in C++

  • What changes has been made in the code since last question?

    I am trying to implement a recursive_transform_reduce function here and use it in population_variance function.

  • Why a new review is being asked for?

    Please check the implementation of recursive_transform_reduce function and if there is any possible improvement, please let me know.

\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

Ensure init is only used once

Since you pass the value of init to recursive calls to recursive_transform_reduce(), the value of init ends up being added potentially more than once to the output. For example:

recursive_transform_reduce(std::vector<std::vector<int>>{{},{}}, 1, std::identity())

This will return 3 instead of 1. To fix it, instead of passing init, pass ValueType{} to the recursive call. Although of course that assumes there is a default constructible null element.

Consider using advice given in earlier answers

I think you should follow the advise given to you in this answer to your question you reference about a recursive iter_value_t:

  • Have one unconstrained template
  • Avoid the requires clause if possible by using the concept name instead of class in the template parameter list

Also again, both your templates implement do a std::transform_reduce(), you just wrote out one of them manually. But it should just be one of the variants that has to do the heavy lifting, the other can just deal with a single value. Then it becomes:

template<class Input, class T, class UnaryOp, class BinaryOp = std::plus<T>>
constexpr auto recursive_transform_reduce(const Input& input, T init, const UnaryOp& unary_op, const BinaryOp& binop = std::plus<T>())
{
    return binop(init, unary_op(input));
}

template<std::ranges::range Input, class T, class UnaryOp, class BinaryOp = std::plus<T>>
constexpr auto recursive_transform_reduce(const Input& input, T init, const UnaryOp& unary_op, const BinaryOp& binop = std::plus<T>())
{
    return std::transform_reduce(std::begin(input), std::end(input), init, binop, [&](auto& element) {
        return recursive_transform_reduce(element, T{}, unary_op, binop);
    });
}

I also changed the names of the types to match std::transform_reduce.

\$\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.