Combining infinite ranges

[Andrei Alexandrescu]

On 05/30/2010 04:43 PM, Philippe Sigaud wrote:
> On Sun, May 30, 2010 at 19:01, Simen kjaeraas <simen.kjaras at gmail.com
> <mailto:simen.kjaras at gmail.com>> wrote:
>
>     Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org
>     <mailto:SeeWebsiteForEmail at erdani.org>> wrote:
>
>             This reminded me that Phobos lacks a combinatorial range,
>             taking two or
>             more (forward) ranges and giving all combinations thereof:
>
>             combine([0,1],[2,3])
>             =>
>             (0,2), (0,3), (1,2), (1,3)
>
>             Work has commenced on implementing just that.
>
>
>         Yah, that would be useful. If Philippe agrees to adapt his work,
>         maybe that would be the fastest route. And don't forget - the
>         gates of Phobos are open.
>
>
>     Too late for that, as I've already written this. :p
>
>
> Hey, cool, lots of static foreach. Man, it's like I'm reading my own
> code. I'm happy to see convergent evolution: this must be the D way to
> do this.
>
>     Current problems: back and popBack not implemented. I'm not sure they
>     even should be. Doing so would be a tremendous pain the region below the
>     spine.
>
>
> Ow.
> I *guess* it's doable, but I for sure don't want to do it.
>
>     May very well be there are other problems, I don't know. If anyone finds
>     any, please let me know.
>
>
> Well, I like the way you dealt with popFront.  You length is more costly
> than mine, but I cheated: I count the numbers of popFronts and substract
> them from the original length.
>
> Your empty use .length in the foreach loop. You should use .empty
> instead, I think. And with an infinite range in the mix, the resulting
> product is infinte also, so you can define your combine to be infinite.
>
> Then I can give you something to munch over :-)
>
> When one range is infinite, the resulting combination is infinite.
> What's sad is that you'll never 'traverse' the infinite range:
> auto c = combine([0,1,2], cycle([2,3,4]));
> ->
> (0,2),(0,3),(0,4),(0,2),(0,3), ...
>
> You never reach the (1,x) (2,x) parts, as it should be seeing how we
> both defined combinations: iterating on the ranges as if they were
> digits in a number.
>
> But there is another way to iterate: diagonally, by cutting successive
> diagonal slices:
>
> c is:
> (0,2),(0,3),(0,4),(0,2),...
> (1,2),(1,3),(1,4),(1,2),...
> (2,2),(2,3),(2,4),(2,2),...
> ->
>
> (0,2),(0,3)(1,2),(0,4),(1,3),(2,2) ...
>
> It's even better if all ranges are infinite.
> I never coded this, but it seems doable for two ranges. Lot thougher for
> any number of ranges... Pretty obscure, maybe?
>
> btw, I think we should divert this discussion in another thread if you
> wish to continue: this is bearophile's Huffman thread, after all.

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).

Andrei