# 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.

This site uses Akismet to reduce spam. Learn how your comment data is processed.