Exercising Ranges (part 8)

(Start at the beginning of the series if you want more context.)

Extras from the Haskell Prelude

Having implemented iterate, there were a couple of other useful things from the Haskell Prelude that I wanted to have available with ranges. First, there’s cycle. It simply takes a finite range and repeats it ad infinitum. The functionality of the cursor is fairly simple, and uses patterns we’ve already seen, so here it is in its entirety:

template 
struct cursor
{
private:
  template 
  using constify_if = meta::apply, T>;
  using cycle_view_t = constify_if;
  cycle_view_t *rng_;
  range_iterator_t> it_;

public:
  using single_pass = std::false_type;
  cursor() = default;
  cursor(cycle_view_t &rng)
    : rng_{&rng}
    , it_{begin(rng.r_)}
  {}
  constexpr bool done() const
  {
    return false;
  }
  auto current() const
  RANGES_DECLTYPE_AUTO_RETURN_NOEXCEPT
  (
    *it_
  )
  void next()
  {
    if (++it_ == end(rng_->r_))
      it_ = begin(rng_->r_);
  }
  CONCEPT_REQUIRES((bool) BidirectionalRange())
  void prev()
  {
    if (it_ == begin(rng_->r_))
      it_ = end(rng_->r_);
    --it_;
  }
  bool equal(cursor const &that) const
  {
    return it_ == that.it_;
  }
};

Like all cursors, it implements current(), next() and equal(). Additionally, if the range passed in is bidirectional, so is the cursor, using the CONCEPT_REQUIRES macro to conditionally enable prev(). There is no sentinel type needed, and the cursor implements done() in a way that makes the range infinite.

In Haskell, cycle is occasionally useful, although it is often used with zip and filter to achieve the same effect that stride – a function already provided by the range library – offers. (I think this combo use of cycle, zip and filter was hinted at briefly in Eric’s ranges keynote when discussing the motivation that lead to stride.) But it’s sufficiently easy to implement and makes a nice example.

One more from the Prelude

A slightly more useful function from the Prelude is scan (in Haskell, scanl and scanr). Despite its somewhat obscure name, it’s easy to understand: it’s a fold that returns all the partial results in a sequence. For example:

Prelude> scanl (+) 0 [1,2,3,4]
[0,1,3,6,10]

In C++, I’m not sure what to call this… perhaps accumulate_partials? I left it as scan, for want of a better name. (Edit: It’s partial_sum and it exists in the STL and the ranges library. So I’ll let this section just stand as a further example.)

One immediate thing to notice about scan is that the range it produces is one element longer than the input range. That’s easily done:

namespace detail
{
  template
  using scan_cardinality =
    std::integral_constant= 0 ?
            static_cast(C::value + 1) :
            finite>;
} // namespace detail

In general, the action of the cursor is going to be the same as we saw with iterate: keep a cached value that is updated with a call to next(), and return it with a call to current().

A nice addition to accumulate

Eric made a nice addition to the range version of accumulate which I also used for scan: in addition to the binary operation and the initial value, there is the option of a projection function which will transform the input values before passing them to the binary operation. So when next() updates the cached value, that code looks like this:

void update_value()
{
  val_ = rng_->op_(val_, rng_->proj_(*it_));
}

It’s like having transform built in instead of having to do it in a separate step: a nice convenience. And that’s all there is to scan.

Conclusions

This has been a fun series of experiments with ranges, and I’ve learned a lot. I’ve made mistakes along the way, and I’m sure there are still parts of my code that reflect extant misunderstandings and general lack of polish. But as an experiment, this has been a success. The code works. As a user of the ranges library with some functional programming experience, it wasn’t too hard to put together solutions. And the Concept messages really helped, along with a knowledge transfer of iterator categories from the STL.

As an extender of the library adding my own views, it took a little effort to establish correct assumptions and understandings, but Eric’s code is clear and offers good patterns to build from. I’m sure a little documentation would have steered me more quickly out of problem areas that I encountered. There are some things that are still problematic and I’m not yet sure how to tackle: chiefly involving recursion. And at the moment, Concept messages don’t always help – I think digging into compiler diagnostics is going to be a fact of life as a range implementer.

C++ will never be as syntactically nice as Haskell is, but ranges offer our best chance yet at high-performance, composable, declarative, correct-by-construction code.