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

[Dave Abrahams]

on Mon Apr 11 2016, Xiaodi Wu <swift-evolution at swift.org> wrote:

> 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.

I don't see how stride neessarily has performance implications any more
than other algorithms we also provide for Sequences, and in this case
there's even less argument for restricting it.  Advancing is still a
constant factor of the cost of advancing through the underlying
Sequence.  We wouldn't even be able to offer a better big-O performance
bound for restricting it to RandomAccessCollections.

>
> 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
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-- 
Dave