Combining infinite ranges

Simen kjaeraas simen.kjaras at gmail.com
Mon May 31 20:51:21 PDT 2010


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. One input range also, as long
as no other range is infinite. In the case of all forward ranges, elements
of each should be visited in order, though. I believe this to be possible,
but not at all easy.

I had to abandon my original idea, as it proved fundamentally flawed.

I believe that for the case of 0 or 1 infinite ranges, the approach used
in the already supplied version is good enough. It also works if one range
is an (optionally infinite) input range. Well, except that it does not
without some rewrites...

For more than one infinite range, Cantor's diagonalization approach
should work, but only if all ranges or all except one are random-access.

-- 
Simen


More information about the Digitalmars-d mailing list