(Start at the beginning of the series if you want more context.)
On reversibility
It occurs to me that I’ve been touting reversibility as a good thing, both implicitly and explicitly (for polynomials), and the reason for that is not just that I might want to print polynomials in natural decreasing-power-of-x order.
The first reason reversibility is important to me: coming from the STL, we are used to containers being iterable. If a container supports bidirectional iterators, it’s necessarily reversible, since all containers are finite and one can obtain the end iterator. The same is not true of ranges – because of the generalization of end as a sentinel condition, ranges can be infinitely long. An infinitely long range has no end, so there’s no way to reverse it, because there’s nowhere to start. It can still support bidirectional iteration, but without reversibility that’s of limited use in most cases. So in my mind, reversibility is a better concept for ranges than simply the availability of bidirectional iteration. (There may be occasional uses for bidirectional iteration without the existence of end – Turing machine simulation springs to mind – but I think reversibility is the more common desire.)
The second reason might be called Postel’s Law of iterator categories: if you’re writing an algorithm (or range view), accept as weak an iterator category as you can, but provide as strong an iterator category as you can. Many views can work with input iterators. Some require forward iterators. Few require stronger guarantees. (They might work more efficiently if random access iteration is available, but this isn’t the same as saying they require that.) And on the flip side, a view should almost never degrade the iterator category that is passed in to it. Polynomials should be reversible, so views on them should be reversible.
In this vein, I tried to make monoidal_zip require only InputRange, but support reversing if the underlying ranges support it.
Pretty-printing polynomials
With that in mind, I embarked on pretty-printing polynomials and infinite series, wanting to print them both in infinite series form (increasing powers-of-x) and “more natural” polynomial form (decreasing powers-of-x).
We have a sequence of coefficients, and each corresponds to a power of x, so I start out by zipping the polynomial with an increasing sequence of integers representing the powers.
I first thought of view::transform and view::intersperse. I coded up a solution using view::transform (view::intersperse turned out to be problematic because the thing being interspersed – the plus or minus sign – depends on the sign of the coefficient).
Here’s a helper function for printing the power of x:
std::string x_to_power(int n)
{
if (n == 0) return {};
if (n == 1) return {"x"};
return {"x^" + std::to_string(n)};
}
And here’s the prettyprint function (that’s what I originally called it) using view::transform:
template
void prettyprint(Rng&& r)
{
bool start = true;
auto m = view::zip(std::forward(r),
view::iota(0))
| view::transform(
[&start] (const std::pair& p) -> std::string {
std::string s;
if (p.first != 0) {
if (!start)
s = p.first > 0 ? " + " : " - ";
s += std::to_string(p.first) + x_to_power(p.second);
start = false;
}
return s;
});
ranges::for_each(m, [](const string& s){ cout << s; });
cout << endl;
}
It has several bugs as-is, and I wasn't happy with that start boolean hanging out there. And moreover, this seemed like a very procedural way to work and was annoying the functional programming part of my brain. What I actually wanted was not a function to output a sequence, but a fold to convert a sequence into a string, or to put it in C++ language, accumulate. The fold is independent of whether or not the sequence is reversed, so I factored out the "driver function" in anticipation of creating a reversing version of it.
template
std::string to_string(Rng&& r)
{
return detail::to_string(
ranges::view::zip(std::forward(r),
ranges::view::iota(0)));
}
And the fold looks like this:
template
std::string to_string(Rng&& r)
{
return ranges::accumulate(
std::forward(r),
std::string(),
[] (std::string s, const auto& p) {
// if the coefficient is non-zero
if (p.first != 0)
{
// treat the first one printed specially
if (s.empty())
s += p.first > 0 ? "" : "-";
else
s += p.first > 0 ? " + " : " - ";
auto coeff = p.first > 0 ? p.first : -p.first;
// don't print coefficient of 1 (unless it's the constant)
if (coeff != 1 || p.second == 0)
{
s += std::to_string(coeff);
}
s += detail::x_to_power(p.second);
}
return s;
});
}
The complexity that creeps in here is, I think, the intrinsic complexity of printing a polynomial rather than complexity introduced by the wrong solution (start has disappeared, replaced with logic that deals with the first printed term). So this accumulate-based approach works with the power series approach of printing in increasing powers of x; but how do we reverse that zip? How can we reverse iota?
To answer that, I needed to go back to the Haskell Prelude, in the next part.