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 < [email protected]> wrote:
> > on Mon Apr 11 2016, Xiaodi Wu <[email protected]> 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 > > <[email protected]> wrote: > > > > on Sun Apr 10 2016, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote: > > > > > On Sun, Apr 10, 2016 at 3:58 PM, Haravikk > > <[email protected]> wrote: > > >> > > >> On 10 Apr 2016, at 14:25, Xiaodi Wu > > <[email protected]> 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 > > >> <[email protected]> wrote: > > >>> > > >>> > > >>> On 10 Apr 2016, at 11:17, Brent Royal-Gordon > > <[email protected]> > > >>> 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 > > >>> [email protected] > > >>> https://lists.swift.org/mailman/listinfo/swift-evolution > > >> > > >> > > > > -- > > Dave > > > > _______________________________________________ > > swift-evolution mailing list > > [email protected] > > https://lists.swift.org/mailman/listinfo/swift-evolution > > -- > Dave > > _______________________________________________ > swift-evolution mailing list > [email protected] > https://lists.swift.org/mailman/listinfo/swift-evolution >
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
