std.range.iota enhancement: supporting more types (AKA issue 10762)

[Andrei Alexandrescu]

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