(Start at the beginning of the series if you want more context.)
First steps with power series
A power series (or polynomial, to give it a more familiar term in the case where it’s finite) is represented simply as a sequence of coefficients of increasing powers of x. This is simple – to represent:
[latex]1 + 2x + 3x^2[/latex]
the code is:
std::vector v = {1, 2, 3};
The simplest thing we can do to this is to negate it, which in range terms is a transform:
template
auto negate(Rng&& r)
{
return ranges::view::transform(std::forward(r),
[] (auto i) { return -i; });
}
Adding polynomials
Things get more interesting when we want to add two polynomials, because they might be of differing degree. If we try to use zip_with, things don’t work out as we want:
template
auto add(R1&& r1, R2&& r2)
{
return ranges::view::zip_with(std::plus<>(),
std::forward(r1),
std::forward(r2));
}
...
std::vector v1 = {1, 2, 3};
std::vector v2 = {1, 2, 3, 4, 5};
auto sum = add(v1, v2);
// we want sum to be {2, 4, 6, 4, 5}
// it's actually {2, 4, 6}
The problem is that zip_with (and by extension zip) only zips as far as both ranges go, and discards the “tail” of the longer range, if any. This is mostly What You Want™, but not here. What we want is for the tail to be included.
So I thought about this for a while. The first thing I thought of was appending an infinite sequence of zeroes to the shorter range:
auto summable_range = view::concat(shorter_range, view::repeat(0));
I coded this up to try it out, and in doing so learned some things about range cardinality (more on that to come), but there is a serious limitation here – at least one that was hard for me to immediately circumvent – which is that the view we return isn’t reversible. It really seems like, given two polynomials I can reverse, I ought to be able to reverse their sum. For one thing, if we’re dealing with a polynomial, it’s more naturally written as decreasing powers of x rather than increasing:
[latex]3x^2 + 2x + 1[/latex] is more natural than [latex]1 + 2x + 3x^2[/latex]
Functional spider senses
So, I thought some more – what I needed was a variety of zip that, when one range ran out, started just returning elements from the longer range. At this point, the functional programmer part of my brain woke up. It saw addition. It saw zeroes. And it whispered to me, “think monoids”. What I wanted was a generalization of polynomial addition, a “monoidal zip” that would take a binary operation and extend to the end of both ranges, using the identity element when the shorter range ran out.
In fact, since using the identity is, by definition, unchanging to the other argument, there is no need to supply the identity to this function – a realization that I didn’t come to until later after I’d had time to step back. For now, C++ brain took over again.
template
auto add(R1&& r1, R2&& r2)
{
return ranges::view::monoidal_zip(std::plus<>(),
std::forward(r1),
std::forward(r2));
}
I delved into zip_with.hpp and this is where my real learnings began, in the next part.