Exercising Ranges (part 5)

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

Generalising iota

To pretty-print a reversible polynomial, we need to provide for reversibility of iota. So what is iota? It makes a range by repeatedly incrementing a value. What if instead of increment, we use an arbitrary function? We could do this with generate_n:

template 
std::string to_string_reverse(Rng&& r)
{
  auto s = ranges::size(r);
  auto powers = ranges::view::generate_n(
      [s] () mutable { return --s; }, s);
  return detail::to_string(
      ranges::view::zip(ranges::view::reverse(std::forward(r)), 
                        powers));
}

But this isn’t quite as clean as it could be: the lambda mutates state. An alternative is found in the Haskell Prelude:

iterate :: (a -> a) -> a -> [a] 

iterate applies a function repeatedly to an argument, feeding the result of the last iteration to the input of the next one. It’s very similar to generate, and we can write both iterate and iterate_n. The view takes a function and an initial value, and produces the sequence:

[latex] x, f(x), f(f(x)), f(f(f(x))), … [/latex]

Here’s the C++ for the skeleton of iterate_view:

template
struct iterate_view
  : view_facade, infinite>
{
private:
  friend struct range_access;
  using result_t = concepts::Function::result_t;
  semiregular_t gen_;
  semiregular_t val_;
  ...
  explicit iterate_view(G g, T&& t)
    : gen_(std::move(g)), val_(std::move(t))
  {}
  ...
};

The cursor is easily written just like generate‘s cursor: next() caches a new value, and current() returns it. Like generate, the view can only be traversed once, so the cached value is kept in the view itself rather than the iterator. And there is no end cursor.

struct cursor
{
  iterate_view *view_;
  ...
  result_t current() const
  {
    return view_->val_;
  }
  void next()
  {
    view_->next();
  }
};
void next()
{
  val_ = gen_(val_);
}

For iterate_n, the approach is almost identical, except that next() decrements a count, and size() is also provided. Using iterate_n, we can generate a decreasing sequence and use it in the reverse print function for a polynomial, which we know is a SizedRange.

template 
std::string to_string_reverse(Rng&& r)
{
  auto s = ranges::size(r);
  auto powers = ranges::view::iterate_n(
      [] (auto i) { return i - 1; }, s-1, s);
  return detail::to_string(
      ranges::view::zip(ranges::view::reverse(std::forward(r)), 
                        powers));
}

As for iterate itself, it’s potentially useful in lots more places. The obvious use cases (and test cases) are mathematical in nature, for instance my test case using the Collatz conjecture (aka Ulam conjecture, 3n+1 conjecture) sequence starting with 27:

int collatz(int n)
{
  if (n & 1) return 3*n+1;
  return n>>1;
}

DEF_TEST(Collatz27, Iterate)
{
  auto m = view::iterate(collatz, 27)
    | view::take_while([] (int n) { return n != 1; });
  EXPECT(ranges::find(m, 9232) != ranges::end(m));
  return true;
}

But there are also plenty of applications in other code, where we are updating the state of something based on its previous state: iterate separates the loop code and allows us to write a clean function that simply produces a new state from an old state. This is useful for games and simulations of all kinds. So iterate is a useful addition to the range views.

Now we can pretty-print polynomials properly, in the next part I’m going to take on the trickier subject of how to multiply them.