[swift-evolution] Feature proposal: Range operator with step

[Dave Abrahams]

on Sat Apr 02 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

> All righty, here's a proof-of-concept for non-error-accumulating
> stride based on the swift-3-indexing-model branch. I tried to
> incorporate the feedback received in the interim. Namely:
>
> 1. Only floating point types get this slightly more computationally
> intensive "new" stride; all other types get the "classic" stride. If
> accepted, this new code could be appended to Stride.swift and exist
> alongside current code, which doesn't need to be modified.
>
> 2. Based on discussions about UnsafePointer, etc., it dawned on me
> that what really determines whether a StrideTo<T> accumulates error
> isn't T but rather T.Stride, so based on Dave's insights above we get
> "new stride" if T.Stride == FloatingPoint.
>
> 3. I need to multiply floating point values, and if I understand
> correctly multiplication will be guaranteed by a revised SignedNumber
> protocol; for now, I've used a _FloatingPointStrideable protocol as a
> workaround. Note that Float80 doesn't conform to FloatingPoint, so it
> isn't retroactively modeled to conform to _FloatingPointStrideable.
> Nothing's lost for the moment because we can't use Float80 values for
> "new stride" anyway, since it doesn't currently implement the isNormal
> property (see below for why I use that property).
>
> 4. I considered Dave's suggestion whether we could avoid introducing
> new types, instead modifying the existing StrideToIterator and
> StrideThroughIterator and relying on compiler optimization to turn
> "new" stride into "classic" stride for StrideTo<Int>, etc.; however,
> because the differences between "classic" stride and "new" stride
> extend beyond the iterator's next() method (see below), I thought it
> best to keep the floating point logic in distinct types.
>
> 5. One difference discussed was how to handle edge cases involving
> lots of iterations; I incorporated Howard's suggestions here, so
> whether a stride requires more than Int.max steps is tested
> upfront--as a consequence, infinite loops are impossible. I would love
> it if, as Thorsten suggests, we could use BigInts, but of course
> there's no such type in the stdlib and adding one would have to be
> another discussion altogether.
>
> 6. The stride increment can't be zero; for a floating point type, it
> also obviously can't be infinity or NaN. I'm inclined to think that
> subnormal increments should be out of the question as well, so my
> proposed streamlined criterion is simply `stride.isNormal`. Comments
> on this are welcome...
>
> Not included:
> 1. I know Ranges are in flux, so I've held off on extending Range with
> a striding(by:) method in this proof-of-concept.

They're not in flux, except for not having been reviewed yet; they are
settled in the swift-3-indexing-model branch.

> 2. No attempt at the suggested stride(from:to:steps:) quite yet.

#1 and #2 are mutually exclusive; we prefer #1 as it removes questions
about the meaning of "to" or "through."

> 2. No tests written yet for this proof-of-concept; I noticed that
> there's a stub for testing strides with bounds of type Double, but
> there's a comment about things not being ready because Double conforms
> to RandomIndexType--not sure what to make of that.  

Comments in that branch are badly out-of-date.  It's worth trying that,
especially since there is no RandomAccessIndexType in that branch any
longer.

> 3. Haven't gotten around to testing performance.
>
> On Wed, Mar 30, 2016 at 12:03 PM, Erica Sadun <erica at ericasadun.com> wrote:
>>
>> On Mar 29, 2016, at 11:26 PM, Xiaodi Wu via swift-evolution
>> <swift-evolution at swift.org> wrote:
>>
>> On Tue, Mar 29, 2016 at 7:48 PM, Dave Abrahams <dabrahams at apple.com> wrote:
>>
>>
>> on Tue Mar 29 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>>
>> Relatedly, while you're tackling this big revision:
>>
>> I've tried to play around with what it would take to write a generic
>> non-error-accumulating striding method, and afaict, it would be
>> enormously cleaner if Strideable types are guaranteed to have + and *
>> (well, Strideable.Stride needs *, to be more accurate),
>>
>>
>> That should happen automatically, since it conforms to SignedNumber,
>> when we get the Integer protocols updated (project currently on hold while
>> we land this other revision).
>>
>> since the iterator needs to be able to compute end = start + iteration
>> * stride.
>>
>>
>> Don't you need division too if you're going to do this?
>>
>>
>> I didn't seem to ever need division. See attached playground (which
>> borrows shamelessly from existing code and Erica's proposal, and which
>> is written in Swift 2.2 because that's what I had handy).
>>
>>
>> Have you considered trying to extend the `swift-3-indexing-model` branch
>> at the Swift repo to take the floating point approach into account? Dave A
>> is working on a massive overhaul of ranges (including `Countable` items
>> and one would presume floating point closed and open intervals as well),
>> and I'd love to see better implementations of, for example,
>> `(x..<y).striding(by:z)`
>> happen for Double types.
>>
>> I'd be happy to throw a proposal together based on a proof of concept,
>> if you had the flexibility to work on the coding.
>>
>> -- Erica
>>
>

-- 
Dave