On 12/23/13 7:00 AM, Francesco Cattoglio wrote:
A few preliminary considerations:
- iota() currently returns a Random Access range, and I'm sure nobody
would agree to downgrade the result to a ForwardRange or an InputRange,
because that would break an unknown amount of code.
Agreed.
- I think everyone agrees that even after enhancements, iota() should
always return a RA range, even if we use types that are currently not
supported. It would make little sense returning different kind of ranges
for different input types.
I think it makes a lot of sense to relax that. Different types have
different properties leading to different iota capabilities.
Let's define the types: When calling iota(start,end,inc)
S=typeof(start),
E=typeof(end),
I=typeof(inc),
C=CommonType!(S,E).
My proposal:
iota(start, end, inc) accepts any type, as long as
{C c; c += inc; c < end;} or {C c; c = c + inc; c < end;} is valid
code;
Sounds good. That's not sufficient to make it random access though.
Since inc type might not be directly comparable to 0, we also check if
(start + inc < start). If this returns true, this means that "inc is
negative" in a more general sense. We can use this information to return
an empty range when needed, respecting the behaviour defined by the
library reference. eg: (start < end && inc < 0) => return empty range.
end is not required to be equal to (start + n*inc) for any given n; eg:
iota(4, 9, 2) should be valid and return [4, 6, 8]. We can discuss if
this makes sense or should be changed, but I think it would be better
this way.
Anything sensible is fine so long as we don't pay every iteration.
If the code {int n; I n_inc = n * inc;} is valid, this instruction is
used for providing O(1) access for opIndex and opSlice methods.
Ah, nice. There's an unstated assumption here - adding inc n times is
the same as adding n * inc.
If the code {C c; c -= inc;} or {C c; c = c - inc} is valid, this
instruction is used for providing O(1) access for popBack() method.
Noice.
If no optimization is available, the code will provide O(n) performance
for those methods.
I don't think any primitive should be O(n).
The real issue however is that construction of the range might end up
taking O(n) time, because we have to provide the length and the back
property. One work around is computing those lazily only if the user
requests them.
By doing this, anyone only using iota() for forward iteration will still
obtain O(1) performance.
All primitives must be O(1).
iota(start, end) accepts any type, as long as
{C c; ++c; c < end;} or {iota(start, end, 1);} is valid code. If
both forms are valid, the iota(start, end, 1) version is preferred
(allowing possible optimizations as discussed before).
No, there are types for which increment is sensible but not adding an
arbitrary number. (Impractical example: Peano arithmetic. Practical
examples anyone?) So iota(start, end) should be a special range, not
derived from the general one. Also x++ is faster than x += a where a is
a variable.
Everything else ends up being the same as before: popBack() can be
optimized if {--c;} is valid code, the opIndex, opSlice, back and length
methods will take O(n) time, no way around this sadly.
Must be O(1) or don't implement. This is the D way.
hsteoh suggested:
If start+inc is *not* supported but start-- is, and end < start,
should we support iota(start,end)?
Absolutely.
I think this idea should be discarded since some code could quickly
become a minefield:
type T implements ++t and --t;
type P only implements ++p;
t1 < t2 => iota(t2, t1) has a way to compute a non-empty range;
p1 < p2 => iota(p2, p1) can do nothing but return an empty range;
And this behaviour really smells bad, IMHO. The only way to solve this
is requiring opUnary!"--" being implemented for the type to be used, and
I am not sure about this (most iota uses only really need ++).
Not sure I understand this, but any reasoning that leads to the
conclusion that simple ++ ranges should be discarded must be carefully
revised.
Andrei
