[swift-evolution] [Draft]: Introducing a striding(by:) method on 3.0 ranges
Xiaodi Wu
xiaodi.wu at gmail.com
Mon Apr 11 16:07:19 CDT 2016
Fair enough. If we go this direction, there's little sense in conforming
StrideTo and friends to Collection at the moment, I suppose?
On Mon, Apr 11, 2016 at 9:56 PM Dave Abrahams via swift-evolution <
swift-evolution at swift.org> wrote:
>
> 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
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160411/ed55fbf9/attachment.html>
More information about the swift-evolution
mailing list