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

[Xiaodi Wu]

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.
2. No attempt at the suggested stride(from:to:steps:) quite yet.
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.
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
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: FloatingPointStrideable.swift
Type: application/octet-stream
Size: 6384 bytes
Desc: not available
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160402/a3565eaa/attachment.obj>