[Challenge] implementing the ambiguous operator in D

[Andrei Alexandrescu]

On 09/06/2010 04:34 PM, Philippe Sigaud wrote:
> Which gives us: (0,0),(0,1),(1,0),(0,2),(1,1),(2,0),(0,3), ..
> See the indices: sum of 0, then sum of 1, then sum of 2, ...
> You never get stuck in an infinite line since these diagonal slices are finite.

I don't think iteration for constant index sums works with forward 
ranges - you need bidirectional ranges to go back in one while going 
forth in another. You need to only move forward in all ranges, or reset 
them to zero.

It helps me a lot to think how I'd lay bricks to fill the first quadrant 
of an n-dimensional infinite space. If you tried the tensorial product, 
you'd lay a nice column of bricks, but you'd be busy at it forever 
because the column would have infinite "height".

If you try your solution that has constant sums, then you are filling 
hypersimplexes of increasing size. That's certainly encouraging because 
it fills the space quite nicely, but again it requires bidirectional ranges.

My solution is to fill hypercubes of increasing size from origin. One 
hypercube of size k is built by adding a layer of bricks on a hypercube 
of size k - 1. That can be done with forward iterators, and in fact is 
not all that difficult.

> Andrei:
>      We've discussed this before. Crosscartesian product of multiple infinite
> ranges can be easily done by applying Cantor's trick for proving that rational
> numbers are just as numerous than natural numbers. Google for "Cantor" with
> "site:digitalmars.com".
>
>
>
> Ok, I think I solved this particular problem, if only for infinite ranges.
> It's in three parts:
>
> 1- A memorize(range) struct that slowly looks ahead in a range, store the result
> in an internal array and so slowly transforms an input range into a random-access
> range. I tried this a few months ago, but got stuck in trying to propagate
> properties (bidirectional, etc). Now it's just an input range. Much easier. It's
> related to Zippers (in functional PL).
> 2- Generate the indices of sum  = 0, then sum = 1, then sum = 2; etc.
> 3- Just take the corresponding indices in the input ranges.

I don't think this is a good solution.


Andrei