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.