Combining infinite ranges

[Philippe Sigaud]

On Tue, Jun 1, 2010 at 19:54, Andrei Alexandrescu <
SeeWebsiteForEmail at erdani.org> wrote:

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

Yeah, that's why I proposed it as a challenge.  You guys sure seem to like
this :)
What's interesting, is that it may even be useful :)


It's ok to store positions in ulong objects. Most uses of infinite

> range combinations use only the first few elements; the computation
>>> will anyway take a very, very long time when any of the ranges
>>> overflows a ulong.
>>>
>>
Quite...


>
> I still haven't understood your explanation, but I think I figured a
> different way to reach the same solution. The idea is to crawl the space by
> adding layers on top of a hypercube of increasing side, starting from the
> origin corner.
>

Like this?

01234
11234
22234
33334
44444

where you have layer #0, #1, ...

In fact, any method to iterate on a finite but growing space without going
onto the already produced values is OK. You could iterate on an hypercube,
then duplicate it to make it n times bigger and recurse:

01 22 3333
11 22 3333
22 22 3333
22 22 3333
3333
3333 ...
3333
3333

I think your solution is viable, because you always iterate on 'square'
shapes, that's a good idea. Its only drawback is that the elements are
produced in a less natural order, but really, who cares: you just want to
take a finite part of an infinite range without closing any door while doing
so.
Going full diagonal is more difficult: you must find a way to peel of the
slices.

I encountered this while reading some on Haskell and enumerating infinite
ranges, but the only implentation I know of for diagonals is here:
http://hackage.haskell.org/packages/archive/level-monad/0.3.1/doc/html/Control-Monad-Levels.html

Related to this, I've something that takes 'hyperslices' from ranges of
ranges of ... (of whatever rank), but only
'vertical' or 'horizontal' (perpendicular to the normal basis of ranges of
ranges...)

I also have a n-dim generalization of take: take(rangeOfRanges, 2,3,4, ...)
and for drop and slice.
I think it's doable to preduce something akin to your layers than way, or
maybe my suggestion on blocks. A combination of takes and drops should
produce
finite cubic shapes that can then be iterated.



> This is an absolutely awesome problem.


Man, don't you have some boring stuff to do instead?

I also found the (simple?) problem to enumerate a range of ranges to be more
interesting than I thought.
Given a range of ranges ... of ranges, of whatever rank, recursively
enumerate it:

[[a,b,c],[d,e,f],[g,h,i]]

produce:

(a,0,0),(b,0,1), (c,0,2),(d,1,0), ...

the coordinates of each element, if you will. I have a working version now,
but it sure taught me that my vision of recursion was flawed.



I attach an implementation for two ranges. It's quite a bit more messy than
> I'd hope, so generalization to n ranges should be preceded by cleaning up
> the abstractions used. I think your solution already has said cleanups!
>

It's good if you can make it to more than two ranges, but I think 2 is
already quite useful.


> The output of the program is:
>
> 0       Tuple!(uint,uint)(0, 0)
> 1       Tuple!(uint,uint)(0, 1)
> 2       Tuple!(uint,uint)(1, 1)
> 3       Tuple!(uint,uint)(1, 0)
> 4       Tuple!(uint,uint)(0, 2)
> 5       Tuple!(uint,uint)(1, 2)
> 6       Tuple!(uint,uint)(2, 2)
> 7       Tuple!(uint,uint)(2, 0)
> 8       Tuple!(uint,uint)(2, 1)
> 9       Tuple!(uint,uint)(0, 3)
> 10      Tuple!(uint,uint)(1, 3)
> 11      Tuple!(uint,uint)(2, 3)
> 12      Tuple!(uint,uint)(0, 4)
> 13      Tuple!(uint,uint)(1, 4)
> 14      Tuple!(uint,uint)(2, 4)
>
>
> Seems good to me. I see the layers, like in the Matrix.
If you ever put that in Phobos, make it a secondary function compared to a
standard combination, or use a policy to let the user dicide to iterate
along layers. Most of the time, you just want the standard 'digit-like' way
to iterate on n ranges.

I'll have a look at your code.

Philippe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20100601/1fcbb093/attachment-0001.html>