So, std.range.isInfinite checks if r.empty is a compile time boolean equal to false. This works most of the time, but not always. Some ranges are infinite, but cannot be determined to be so at compile time (or even run time!)

cycle([1, 2, 3]).until(4);    // infinite, but not isInfinite
cycle(new int[0]);            // not infinite, but isInfinite
collatzSequence(n).until(1);  // infiniteness an open problem!

In short, isInfinite does not -- and cannot -- work as a way of telling if a range is finite or infinite in general.

On resolution is to take isInfinite at face value: it only tells you if a range is statically determined to be infinite. If isInfinite is false, it could still be infinite.

This leaves us with the tricky cases like cycle(new int[0]). There's three resolutions to this (as far as I can tell):

1. Change cycle to not be an infinite range.
2. Make cycle assert when the source range is empty.
3. Ignore this issue.

Option 1 is sound, but kind of sucks, because generally cycle is infinite.

Option 2 is sound, but I don't like the idea of asserting on logically valid input just because the problem is too hard.

Option 3 is not sound, but may be practical. Perhaps these edge-case, fake, infinite sequences are not worth worrying about -- just let it slide and make other people worry about the consequences.

This Phobos pull request is relevant: https://github.com/D-Programming-Language/phobos/pull/871

Thoughts?

On Wednesday, 17 October 2012 at 12:18:32 UTC, Peter Alexander wrote:
> So, std.range.isInfinite checks if r.empty is a compile time boolean equal to false. This works most of the time, but not always. Some ranges are infinite, but cannot be determined to be so at compile time (or even run time!)
>
> cycle([1, 2, 3]).until(4);    // infinite, but not isInfinite
> cycle(new int[0]);            // not infinite, but isInfinite
> collatzSequence(n).until(1);  // infiniteness an open problem!
>
> In short, isInfinite does not -- and cannot -- work as a way of telling if a range is finite or infinite in general.
>
> On resolution is to take isInfinite at face value: it only tells you if a range is statically determined to be infinite. If isInfinite is false, it could still be infinite.
>
> This leaves us with the tricky cases like cycle(new int[0]). There's three resolutions to this (as far as I can tell):
>
> 1. Change cycle to not be an infinite range.
> 2. Make cycle assert when the source range is empty.
> 3. Ignore this issue.
>
> Option 1 is sound, but kind of sucks, because generally cycle is infinite.
>
> Option 2 is sound, but I don't like the idea of asserting on logically valid input just because the problem is too hard.
>
> Option 3 is not sound, but may be practical. Perhaps these edge-case, fake, infinite sequences are not worth worrying about -- just let it slide and make other people worry about the consequences.
>
> This Phobos pull request is relevant: https://github.com/D-Programming-Language/phobos/pull/871
>
> Thoughts?

> cycle(new int[0]);            // not infinite, but isInfinite
> 2. Make cycle assert when the source range is empty.

Technically, while cycle does not assert, it will fail on the first call to front, either because of a divide by 0 (RA: index%length), or because of a call to an empty front.

We should add an assert. IMO.

--------
TBH, I do not see either as being a problem:

Technically, cycle([]) *is* isInfinite, but the program will assert because of a run-time error due to the user's logic. Nobody said that just because a range is infinite, that it can't ever fail...

Ranges that go on forever, but are not *isInfinite*. My stance on this point is that it is not a *big* problem either. I see it more as a runtime "infinite loop", rather than an compile time "infinite range". It's like a for loop where the run-time end condition will always be true.

That said, if the user *does* know the range will be infinite, I wouldn't be against having an "assumeInfinite" template function, that can take any range, and transform into an (assumed) compile time infinite range.

On Wednesday, 17 October 2012 at 12:33:54 UTC, monarch_dodra wrote:
> Technically, cycle([]) *is* isInfinite, but the program will assert because of a run-time error due to the user's logic. Nobody said that just because a range is infinite, that it can't ever fail...

cycle([]) is not infinite. A infinitely repeated empty range is the empty range.

On Wednesday, 17 October 2012 at 12:45:07 UTC, Peter Alexander wrote:
> On Wednesday, 17 October 2012 at 12:33:54 UTC, monarch_dodra wrote:
>> Technically, cycle([]) *is* isInfinite, but the program will assert because of a run-time error due to the user's logic. Nobody said that just because a range is infinite, that it can't ever fail...
>
> cycle([]) is not infinite. A infinitely repeated empty range is the empty range.

I'd argue that cycle should be redefined as "Repeats the *content* of the given forward range ad infinitum." From there, passing it an empty range would be a logic error, since said range didn't have any content.

On 10/17/12 8:18 AM, Peter Alexander wrote:
> 2. Make cycle assert when the source range is empty.

I think this is sensible.

Andrei

I want to resurrect that thread. Can someone explains the benefices of isInfinite ? I fail to see how it really benefit the code.

On Tuesday, 12 March 2013 at 10:01:38 UTC, deadalnix wrote:
> I want to resurrect that thread. Can someone explains the benefices of isInfinite ? I fail to see how it really benefit the code.

The advantage of "enum empty = false" is that algorithms gain a great performance boost by optimizing out any "if (r.empty)". This can be exploited for things like take, or anything that iterates as a matter of fact. I don't think anybody will argue that this is a bad approach.

The trait itself checks if empty can be evaluated at compile time (to false). The advantage for the *coder* to know if the range is infinite is less obvious.

One of the advantages is that an infinite range can have random access (meets RA requirements), even though it has no length member (normally, any RA range must have length).

Having "isInfinite" can also have the advantage of protecting users from stupid calls. For example, calling "count" on an infinite range is forbidden => shifting problems from runtime to compile time is a HUGE gain.

One of downsides to having infinite ranges is that their existence tends to make dealing with generic RA ranges a bit more difficult. A lot of our algorithms have changed requirements conditions from:
"if (isRandomAccessRange!R)"
to
"if (isRandomAccessRange!R && hasLength!R)"
or
"if (isRandomAccessRange!R && !isInfinite!R)"
//NOTE: Both are strictly equivalent: An RA range is either infinite, or has length, but not neither nor both.

Up until not so long ago, it was not possible to slice infinite ranges. It is now possible. Unfortunatly, because RA ranges with slicing don't guarantee that r[0 .. $] is legal, things are still complicated in template code.

The last point (IMO minor) that is raised in the thread is "runtime" infiniteness. EG: a range that may or may not be infinite at compile time, but which will be known at runtime. IMO, these a rare enough (arguably, inexistent) to not really matter. The workarounds are easy:
1) Make the range always infinite, but with a requirement that user must intialize it or whatnot.
2) Make a runtime fork that will call code that operates on a compile-time known infinite adaptor/subtype.

12-Mar-2013 14:49, monarch_dodra пишет:

> Up until not so long ago, it was not possible to slice infinite ranges.
> It is now possible. Unfortunatly, because RA ranges with slicing don't
> guarantee that r[0 .. $] is legal, things are still complicated in
> template code.

I thought it goes in opposite direction - slicing of Infinite range works only for ..$ slice. The chief new requirement of slicing is self-assign ability.
>
> The last point (IMO minor) that is raised in the thread is "runtime"
> infiniteness. EG: a range that may or may not be infinite at compile
> time, but which will be known at runtime. IMO, these a rare enough
> (arguably, inexistent) to not really matter. The workarounds are easy:
> 1) Make the range always infinite, but with a requirement that user must
> intialize it or whatnot.
> 2) Make a runtime fork that will call code that operates on a
> compile-time known infinite adaptor/subtype.


-- 
Dmitry Olshansky

On Tuesday, 12 March 2013 at 11:24:00 UTC, Dmitry Olshansky wrote:
> 12-Mar-2013 14:49, monarch_dodra пишет:
>
>> Up until not so long ago, it was not possible to slice infinite ranges.
>> It is now possible. Unfortunatly, because RA ranges with slicing don't
>> guarantee that r[0 .. $] is legal, things are still complicated in
>> template code.
>
> I thought it goes in opposite direction - slicing of Infinite range works only for ..$ slice. The chief new requirement of slicing is self-assign ability.

I believe the official stance on this is that self-assign is only required for non-infinite ranges.

On Tuesday, 12 March 2013 at 11:24:00 UTC, Dmitry Olshansky wrote:
> 12-Mar-2013 14:49, monarch_dodra пишет:
>
>> Up until not so long ago, it was not possible to slice infinite ranges.
>> It is now possible. Unfortunatly, because RA ranges with slicing don't
>> guarantee that r[0 .. $] is legal, things are still complicated in
>> template code.
>
> I thought it goes in opposite direction - slicing of Infinite range works only for ..$ slice. The chief new requirement of slicing is self-assign ability.

Its... complicated.

To be exact: hasSlicing only requires that:
//--------
        static if(isInfinite!R)
            typeof(take(r, 1)) s = r[1 .. 2];
        else
        {
            static assert(is(typeof(r[1 .. 2]) == R));
            R s = r[1 .. 2];
        }
        //minor tests here
//--------

Which means that if you are going to slice an RA, make sure it is finite before back-assigning.

From there, *if* r[0 .. $] is legal, *then* extra checks are made:
//--------
        static if(is(typeof(r[0 .. $])))
        {
            static assert(is(typeof(r[0 .. $]) == R));
            //minor tests here
        }
//--------

*Ideally*, for finite RA ranges, we would want to enforce that [0 .. $] MUST be legal. This would be breaking change however. We'd want the compiler to auto generate opDollar, which would make things simpler for everyone:
http://d.puremagic.com/issues/show_bug.cgi?id=7177
The only reason this isn't done yet (AFAIK) is because:
* Support for opDollar is still relativelly new.
* exact details are not fully thought out yet.

As for infinite ranges, ditto. Basically, once you've implemented "slice to end", normal slicing is also trivial.

However, today, this is not the case, since it's breaking change.

If you want to call "r[0 .. $]", you have to jump through hoops to know if it is legal code.

...

Come to think about it, with today's "deprecated features are on by default", I think it would be possible to activate this new requirement without breaking any code. Those that activate -w would then notice their range needs change to meet the new hasSlicing requirements. traits + deprecation is funny business.

@jmdavis: What do you think?