C++11 equivalent of Haskell's "inits"

Question

Just a short question:

Is there any C++11 equivalent of Haskell's inits?

The inits function returns all initial segments of the argument, shortest first.

I'd like to do sth. like

reverse $ inits [1..10]

C++11 supports std::reverse, but i could not find sth. like std::inits.

The List will be represented in C++ as a std::vector.

Answer 1

I think I got it working purely functional:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void) {
  vector<int> nums = { 1,5,5,9,8,7,6 };

  auto inits = accumulate(nums.begin()+1, nums.end(), // Iterate between second and last element
                  vector< vector<int> >{ vector<int>{nums.front()}}, // Initialize accumulator
                  [] (vector< vector<int> > &acc, int j) { // Lambda constructing further elements
                        auto tmp = acc.back();
                        tmp.push_back(j);
                        acc.push_back( tmp );
                  });
  return 0;
}

Inits will be a vector of vectors of int's.

Everything without (visible) loops :-)

Answer 2

For a random-access range (since you mention std::vector), a range of successive slices is manageable. This will also work with forward and bidirectional ranges, although that will incur an additional linear cost when computing the distance. With Boost.Range:

#include <boost/range/irange.hpp>
#include <boost/range/adaptor/sliced.hpp>
#include <boost/range/adaptor/transformed.hpp>

namespace R = boost::adaptors;

template<typename Range>
using range_difference_t = typename boost::range_difference<Range>::type;

namespace functors {

template<typename Range>
struct slice {
    using difference_type = range_difference_t<Range>;
    Range* range;

    explicit slice(Range& range)
        : range(&range)
    {}

    boost::sliced_range<Range> operator()(difference_type index) const
    {
        return R::slice(*range, static_cast<difference_type>(0), index);
    }
};

} // functors

template<typename Range>
using inits_type =
    boost::transformed_range<
        functors::slice<Range>,
        const boost::integer_range<range_difference_t<Range>>
    >;

// calling inits with rvalues is not supported on purpose
template<typename Range>
inits_type<Range> inits(Range& range)
{
    using diff_t = range_difference_t<Range>;
    return R::transform(
        // use boost::size instead of distance to restrict
        // inits to working efficiently on random-access ranges only
        boost::irange(static_cast<diff_t>(0), boost::distance(range) + static_cast<diff_t>(1)),
        functors::slice<Range> { range }
        );
}

Demo here.

This solution benefits greatly from C++14, leaving us with just:

// same includes

template<typename Range>
auto inits(Range& range)
{
    namespace R = boost::adaptors;
    using diff_t = typename boost::range_difference<Range>::type;
    return R::transform(
        boost::irange(static_cast<diff_t>(0), boost::distance(range) + static_cast<diff_t>(1)),
        [range = &range](diff_t i) { return R::slice(*range, static_cast<diff_t>(0), i); }
        );
}

C++14 demo here.

As for a non-slicing solution (i.e. closer in spirit to the Haskell version), this would require writing iterators by hand, with ‘interesting’ lifetime considerations. I would not recommend it.