March 12, 2013
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
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
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
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
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
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.

1 2 3
Next ›   Last »