[swift-evolution] [Draft]: Introducing a striding(by:) method on 3.0 ranges

[Xiaodi Wu]

I realize what follows is actually an argument for restricting stride to
collections with randomly accessible elements, and maybe we should:

We've touched a little bit on performance, and I think my feeling with
stride is that just the name itself suggests a certain logic--namely, that
we actually skip over, rather than visit and discard, the elements that
aren't in the sequence.

I form this intuition from the ordinary sense of the word "stride"--if my
walking gait has a stride size of two feet and there's a puddle less than
one foot wide right in front of me, striding by two feet means that my feet
stay dry. It doesn't mean I drag one shoe through the puddle and ignore it.
Likewise, when I stride from 2 to 10 by 2, I'm adding two at every step,
not adding one twice.

Since an ordinary user of stride doesn't and shouldn't have to inspect the
code in the stride iterator, I think it would violate some users'
expectations if sequences that are not collections have each element
visited regardless of stride size. A user can trivially write a for loop
iterating over the sequence itself and discard every not-nth element. We
shouldn't offer a stride function that looks more performant but actually
isn't.

On Mon, Apr 11, 2016 at 7:38 PM Dave Abrahams <dabrahams at apple.com> wrote:

>
> on Sun Apr 10 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
>
> > On Sun, Apr 10, 2016 at 3:58 PM, Haravikk <swift-evolution at haravikk.me>
> wrote:
> >>
> >> On 10 Apr 2016, at 14:25, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
> >>
> >> What types do you have in mind that would only support positive
> distances?
> >> All numeric types (yes, even UInt, etc.) have signed distances, which
> >
> >> reflects the basic mathematical abstraction of a number line.
> >>
> >>
> >> Say you wanted to stride through a singly-linked list, it would
> actually be
> >> beneficial to support only forward strides, the same is true of
> sequences,
> >> as you either may not know what the endpoint is, or would have to step
> >> through the whole sequence to find it (plus buffer every value in order
> to
> >> do-so safely).
> >>
> >> A consistent behavior with signed distances is so important that we are
> >> currently struggling with an interesting issue with floating point
> types,
> >> which is that due to rounding error 10.0 + a - a != 10.0 for some
> values of
> >> a.
> >>
> >>
> >> While that’s interesting I’m not sure why the sign is important; to me a
> >> stride is a width so it being negative makes no sense. For example, say
> I
> >> laid an array of Ints, organised into groups of five (and also that I’m
> >> lunatic who won’t use a tuple for this), the stride of this array is 5
> >> whether I’m stepping through it forwards or backwards. Imagine I defined
> >> this like so (more realistically it’d be a struct or a class):
> >>
> >> typealias StridedIntegerArray:(stride:Int, array:[Int])
> >>
> >> If the stride is set to 5, it’s always 5, the only thing that changes is
> >> whether I want to stride from the start or end of the array, plus I
> could
> >> things like:
> >>
> >> myStridedIntegerArray.prefix(from: 2).striding(forwardBy:
> >> myStridedIntegerArray.stride) // Returns element at index 2, 7, 12, etc.
> >
> > When you have a sequence returning elements at index 12, 7, 2, etc.,
> > wouldn't you call the stride size -5? I would, because 12 + (-5) = 7.
> >
> >>
> >>
> >> It just occurred to me that perhaps you intended this method only for
> ranges
> >> specifically and that perhaps I’m confusing things, but it seems to me
> like
> >> it should be a method for all sequences (with reverse stride available
> on
> >> collections with a reverse index type) returning a generator that only
> >> returns (or computes) every Nth element, for generic
> sequences/collections
> >> this would take the start or end index and use advanced(by:), though
> again,
> >> I kind of feel like that should be two separate methods as well, but
> that’s
> >> for another issue I think.
> >
> > I don't think it should be for ranges only, but ranges are the extent
> > of this proposal.
> >
> > That said, my own opinion is that striding should not be available on
> > sequences but on collections only. In their most commonly used form,
> > integer strides take a start and end, and there is a finite number of
> > things to stride over; thus, in my reasoning, strides can be extended
> > to cover anything else that has a known start and end and has a finite
> > number of things, which is guaranteed by conformance to Collection but
> > not to Sequence.
>
> I dunno; it seems to me that if someone gives me a Sequence I should be
> able to traverse it, skipping every other element.  I don't see why
> “stride” should be inapplicable here.
>
> > (At the moment, StrideTo/Through conforms to Sequence and not to
> > Collection, but that is considered something to be fixed and we will
> > see if we can address that as part of this set of stride overhauls.)
> >
> > As I see it, we agree on the problem: the current algorithm cannot
> > accommodate singly linked lists and sequences because those things do
> > not have a known endpoint if you begin an attempt to stride. However,
> > my conclusion is the opposite of yours: namely, that they should not
> > have stride. Maybe they should have something similar, but it
> > shouldn't be stride.
> >
> >>
> >> On Sun, Apr 10, 2016 at 12:53 PM Haravikk via swift-evolution
> >> <swift-evolution at swift.org> wrote:
> >>>
> >>>
> >>> On 10 Apr 2016, at 11:17, Brent Royal-Gordon <brent at architechies.com>
> >>> wrote:
> >>>
> >>> Why not just assign it the correct sign during the init function?
> >>> (0 ... 6).striding(by: 2) // [0, 2, 4, 6], end > start, so stride = by
> >>> (6 ... 0).striding(by: 2) // [6, 4, 2, 0], start > end, so stride = -by
> >>>
> >>>
> >>> One reason not to do it this way is that, if we extend `striding(by:)`
> to
> >>> other collections, they will not be as easy to walk backwards through
> as
> >>> this. You will have to do something like
> >>> `collection.reversed().striding(by:)` which will be a hassle.
> >>>
> >>>
> >>> Any thoughts on the alternative I mentioned a little earlier to define
> >>> overloads instead of positive/negative? i.e- you would have two
> methods,
> >>> .striding(forwardBy:) and .striding(backwardBy:). In addition to
> eliminating
> >>> the use of a negative stride to indicate direction, this has the
> advantage
> >>> that .striding(backwardBy:) can be defined only for types with a
> >>> ReverseIndex or only for collections (as you can stride through a
> sequence,
> >>> but only by going forward).
> >>>
> >>> This should also make documentation a bit clearer, otherwise you’ve got
> >>> the caveat that to go backwards requires a negative value, but only if
> the
> >>> type supports that, which a developer would then need to check.
> Instead it
> >>> either has the backwardBy variant or not.
> >>>
> >>> I know that advance(by:) supports negative values, but this is actually
> >>> something I wouldn’t mind seeing changed as well, as it has the same
> issues
> >>> (passing a negative value in looks fine until you realise the type is a
> >>> ForwardIndex only). It would also allow us to define Distance types
> that
> >>> don’t support a direction, since this would be given by the choice of
> method
> >>> called instead.
> >>>
> >>>
> >>> Of course I’d still like to be able to define 6 … 0 or whatever, but
> this
> >>> would at least eliminate what I dislike about using negatives for
> direction.
> >>> _______________________________________________
> >>> swift-evolution mailing list
> >>> swift-evolution at swift.org
> >>> https://lists.swift.org/mailman/listinfo/swift-evolution
> >>
> >>
>
> --
> Dave
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160411/412f7a63/attachment.html>