Combining infinite ranges

[Andrei Alexandrescu]

On 05/31/2010 08:07 PM, Simen kjaeraas wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
>
>> Yah, there's no argument that infinite ranges must be allowed by a
>> n-way cross-product. It reminds one of Cantor's diagonalization, just
>> in several dimensions. Shouldn't be very difficult, but it only works
>> if all ranges except one are forward ranges (one can be an input range).
>
> Might I coerce you into indulging some more detail on this idea? I'm
> afraid my knowledge of the diagonal method is sadly lacking, and some
> reading on the subject did not give me satisfactory understanding of
> its application in the discussed problem.
>
> Way I thought of doing it is save the highest position this far of each
> range, then in popFront see if we're past it. If we are, reset this
> range, and pop from the next range up, recursively.

I thought about this some more, and it's more difficult and more 
interesting than I thought.

Cantor enumerated rational numbers the following way: first come all 
fractions that have numerator + denominator = 1. That's only one 
rational number, 1/1. Then come all fractions that have num + denom = 2. 
That gives 1/2 and 2/1. Then come all fractions that have num + denom = 
3, and so on.

Using this enumeration method he proved that rational numbers are 
countable so in some way they are not more "numerous" than natural 
numbers, which was an important result.

With ranges, the trick should be similar: although individual ranges may 
be infinite, they are composed in a simple, countable manner.

Generalizing Cantor's enumeration technique to n ranges, note that the 
enumeration goes through elements such that the sum of their offsets 
from the beginning of the ranges is constant.

So for two ranges, we first select pairs that have their offsets sum to 
0. That is (0, 0). Then we select pairs of offsets summing to 1: (0, 1) 
and (1, 0). Then same for 2: (0, 2), (1, 1), (2, 0). And so on.

The problem is that in order to make sure offsets are constant, forward 
ranges are not enough. If all ranges involved had random access, the 
problem would be trivially solvable. The trick is pushing that envelope; 
for example, it's possible to make things work with one forward range 
and one random-access range, and so on.

This is bound to be an interesting problem. Please discuss any potential 
solutions here.


Andrei