A Summation Function For Boost.MultiArray in C++

Question

This is a follow-up question for A Summation Function For Arbitrary Nested Vector Implementation In C++ and A Summation Function For Various Type Arbitrary Nested Iterable Implementation in C++. I am trying to implement a recursive_sum function for the Boost Multidimensional Array Library. The purpose of this recursive_sum function is to sum up each element in a input boost::multi_array data. The recursive structure here is similar to the previous implementation for std::vector and the other type nested iterable. Furthermore, I found that there are several types including boost::multi_array, boost::detail::multi_array::sub_array and boost::detail::multi_array::const_sub_array in Boost.MultiArray library. I am trying to handle these types with multiple overload function as below.

template<class T> requires is_summable<T>
auto recursive_sum(const T& input)
{
    return input;
}

//  Deal with the boost::multi_array case
template<class T, std::size_t Dims> requires is_summable<T>
auto recursive_sum(const boost::detail::multi_array::const_sub_array<T, Dims>& input)
{
    T sum_output{};
    for (typename boost::multi_array<T, Dims>::index i = 0; i < input.shape()[0]; i++)
    {
        sum_output += recursive_sum(input[i]);
    }
    return sum_output;
}

//  Deal with the boost::multi_array case
template<class T, std::size_t Dims> requires is_summable<T>
auto recursive_sum(const boost::detail::multi_array::sub_array<T, Dims>& input)
{
    T sum_output{};
    for (typename boost::multi_array<T, Dims>::index i = 0; i < input.shape()[0]; i++)
    {
        sum_output += recursive_sum(input[i]);
    }
    return sum_output;
}

//  Deal with the boost::multi_array case
template<class T, std::size_t Dims> requires is_summable<T>
auto recursive_sum(boost::multi_array<T, Dims>& input)
{
    T sum_output{};
    for (typename boost::multi_array<T, Dims>::index i = 0; i < input.shape()[0]; i++)
    {
        sum_output += recursive_sum(input[i]);
    }
    return sum_output;
}

The used is_summable concept:

template<typename T>
concept is_summable = requires(T x) { x + x; };

The test for this recursive_sum function:

int main()
{
    // Create a 3D array that is 3 x 4 x 2
    typedef boost::multi_array<double, 3> array_type;
    typedef array_type::index index;
    array_type A(boost::extents[3][4][2]);

    // Assign values to the elements
    int values = 0;
    for (index i = 0; i != 3; ++i)
        for (index j = 0; j != 4; ++j)
            for (index k = 0; k != 2; ++k)
                A[i][j][k] = values++;
    
    auto recursive_sum_output = recursive_sum(A);
    std::cout << "recursive_sum_output: " << recursive_sum_output;
    
    return 0;
}

All suggestions are welcome.

• Which question it is a follow-up to?

  A Summation Function For Arbitrary Nested Vector Implementation In C++ and

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

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

  The previous question is focused on the common containers in C++ STL, such as std::vector. The main idea in this question is trying to implement another type summation function which can deal with boost::multi_array.

• Why a new review is being asked for?

  I found that there are three types of array structure in Boost.MultiArray library which are boost::multi_array, boost::detail::multi_array::sub_array and boost::detail::multi_array::const_sub_array. In order to handle these different type classes, there are three overload functions recursive_sum for dealing with each type separately. I am not sure is there any better way to simplify these overload functions. Moreover, if there is any possible improvement for this code, please let me know.

Answer 1

Implement a recursive std::reduce()

You shouldn't need to special-case boost::multi_array and related types, as those types already act like STL containers (they provide begin() and end() for example). The main problem however is how to deduce the return type of recursive_sum(). Your functions seem to work because they deduce T from a boost::multi_array<T, Dims>, but do they really? Your recursive_sum() recurses over the dimensions of a multi_array, but it doesn't actually handle nested multi_arrays, like for example:

boost::multi_array<boost::multi_array<double, 2>, 3> array;

The reason is that in the above case, calling recursive_sum(array) will deduce T to be a boost::multi_array<double, 2> instead of a double.

To solve this issue, I would do what std::reduce() does, and sidestep the issue by requiring an initial value for the sum. The type of this initial value will also be the return type. For example:

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;
}

Then you can call it like so:

boost::multi_array<...> array(...);
std::cout << recursive_reduce(array, 0.0) << "\n";

You could perhaps write some template to find the inner-most value type, so that you can use that as a default for the template parameter ValueType in recursive_reduce(), and then you can use {} as the default value for init, and be able to write:

std::cout << recursive_reduce(array) << "\n";