March 12, 2013 Re: isInfinite isInadequate | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | On Tuesday, 12 March 2013 at 16:41:32 UTC, Steven Schveighoffer wrote: > On Tue, 12 Mar 2013 12:32:22 -0400, monarch_dodra <monarchdodra@gmail.com> wrote: >> On Tuesday, 12 March 2013 at 16:16:07 UTC, Andrei Alexandrescu >>> >>> Crossed my mind a few times that fresh non-infinite ranges should be empty. >> >> s/should/could/ >> >> In any case, that's a very dangerous logic to follow. Not-initialized means not initialized. At that point, the concept of empty or not empty is irrelevant, it's a wrong call. > > No, ranges can be initialized without a constructor. Structs are. Classes aren't. But a class with empty as an enum would work. Depends on your definition of "initialized" I guess. Sure, you can create a struct instance without a constructor. Try using a RefCounted!(AutoInit.No) and see what happens. > The idea is that the ultimate underlying source of empty is an enum. Since it's an enum, it should be calculable at compile-time, and it should always be false, regardless of the state of the range (invalid or valid). Yes. *empty* will always answer false. My point though is that it's not just because range.empty says false that the range is ready for use. > The problem is whether NON-infinite ranges are empty or not. Looks like there are cases where they could be non-empty. > > -Steve I think that each range should be responsible for its own initialization semantics. |
March 12, 2013 Re: isInfinite isInadequate | ||||
---|---|---|---|---|
| ||||
Posted in reply to monarch_dodra | On Tue, 12 Mar 2013, monarch_dodra wrote:
> 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).
Where did this assertion come from? There's nothing about infinite that implies random access in the general case. Consider a circular linked list. It's infinite but not random access.
There's a class of infinite functions which are random access, but definitely not all.
|
March 12, 2013 Re: isInfinite isInadequate | ||||
---|---|---|---|---|
| ||||
Posted in reply to Brad Roberts | On Tuesday, 12 March 2013 at 18:08:25 UTC, Brad Roberts wrote:
> On Tue, 12 Mar 2013, monarch_dodra wrote:
>
>> 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).
>
> Where did this assertion come from? There's nothing about infinite that
> implies random access in the general case. Consider a circular linked
> list. It's infinite but not random access.
>
> There's a class of infinite functions which are random access, but
> definitely not all.
Yeah... ergo "can".
|
March 12, 2013 Re: isInfinite isInadequate | ||||
---|---|---|---|---|
| ||||
Posted in reply to monarch_dodra | On Tue, 12 Mar 2013, monarch_dodra wrote:
> On Tuesday, 12 March 2013 at 18:08:25 UTC, Brad Roberts wrote:
> > On Tue, 12 Mar 2013, monarch_dodra wrote:
> >
> > > 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).
> >
> > Where did this assertion come from? There's nothing about infinite that implies random access in the general case. Consider a circular linked list. It's infinite but not random access.
> >
> > There's a class of infinite functions which are random access, but definitely not all.
>
> Yeah... ergo "can".
Ok. The use of 'can' there is generally a much stronger implication than that read of it. I read it as an implies rather than allows for the possibility, and I'll bet I'm not alone.
|
March 12, 2013 Re: isInfinite isInadequate | ||||
---|---|---|---|---|
| ||||
Posted in reply to Peter Alexander | On 10/17/2012 5:18 AM, 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. isInfinite tells you if it is statically determinable to be infinite, not if it might be at run time. > 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. Right. isInfinite doesn't pretend to solve the halting problem. > 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. It isn't just hard, it is impossible. Re the halting problem. |
March 13, 2013 Re: isInfinite isInadequate | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 03/12/2013 05:16 PM, Andrei Alexandrescu wrote: > On 3/12/13 11:47 AM, Steven Schveighoffer wrote: >> ... >> Wouldn't this also be valid? >> >> if(!R.init.empty) >> >> Essentially, you can evaluate R.init.empty at compile time AND it's >> false on an uninitialized range. How can a correctly written >> non-infinite range pass that? >> >> That would make forwarding much easier, as the 'dumb' implementation >> still would result in an infinite range. > > Crossed my mind a few times that fresh non-infinite ranges should be > empty. But there's no explicit requirement stating that, and I think > e.g. one may define a k-elements buffer backed by in-situ storage. > > Andrei std.algorithm.joiner assumes that default-initialized separator ranges are empty. import std.algorithm, std.array, std.range; struct NonEmptyRange{ int[] a = [0,8]; @property int front(){ return a.front; } @property bool empty(){ return a.empty; } void popFront(){ a.popFront(); } @property NonEmptyRange save(){ return NonEmptyRange(a.save); } } void main(){ assert(equal([[1,2,3],[1,2,3]].joiner(NonEmptyRange()),[1,2,3,0,8,1,2,3])); // fail } I'd report it, but the bug tracker is down. |
Copyright © 1999-2021 by the D Language Foundation