Combining infinite ranges

[Andrei Alexandrescu]

On 05/31/2010 10:51 PM, Simen kjaeraas wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
>
>> 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.
>
> All forward ranges should be doable, too.

How would the spanning strategy work for two forward infinite ranges?

Andrei