Fair enough. If we go this direction, there&#39;s little sense in conforming StrideTo and friends to Collection at the moment, I suppose?<br><div class="gmail_quote"><div dir="ltr">On Mon, Apr 11, 2016 at 9:56 PM Dave Abrahams via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>&gt; wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
on Mon Apr 11 2016, Xiaodi Wu &lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:<br>
<br>
&gt; I realize what follows is actually an argument for restricting stride to<br>
&gt; collections with randomly accessible elements, and maybe we should:<br>
&gt;<br>
&gt; We&#39;ve touched a little bit on performance, and I think my feeling with stride is<br>
&gt; that just the name itself suggests a certain logic--namely, that we actually<br>
&gt; skip over, rather than visit and discard, the elements that aren&#39;t in the<br>
&gt; sequence.<br>
&gt;<br>
&gt; I form this intuition from the ordinary sense of the word &quot;stride&quot;--if my<br>
&gt; walking gait has a stride size of two feet and there&#39;s a puddle less than one<br>
&gt; foot wide right in front of me, striding by two feet means that my feet stay<br>
&gt; dry. It doesn&#39;t mean I drag one shoe through the puddle and ignore it. Likewise,<br>
&gt; when I stride from 2 to 10 by 2, I&#39;m adding two at every step, not adding one<br>
&gt; twice.<br>
&gt;<br>
&gt; Since an ordinary user of stride doesn&#39;t and shouldn&#39;t have to inspect the code<br>
&gt; in the stride iterator, I think it would violate some users&#39; expectations if<br>
&gt; sequences that are not collections have each element visited regardless of<br>
&gt; stride size. A user can trivially write a for loop iterating over the sequence<br>
&gt; itself and discard every not-nth element. We shouldn&#39;t offer a stride function<br>
&gt; that looks more performant but actually isn&#39;t.<br>
<br>
I don&#39;t see how stride neessarily has performance implications any more<br>
than other algorithms we also provide for Sequences, and in this case<br>
there&#39;s even less argument for restricting it.  Advancing is still a<br>
constant factor of the cost of advancing through the underlying<br>
Sequence.  We wouldn&#39;t even be able to offer a better big-O performance<br>
bound for restricting it to RandomAccessCollections.<br>
<br>
&gt;<br>
&gt; On Mon, Apr 11, 2016 at 7:38 PM Dave Abrahams<br>
&gt; &lt;<a href="mailto:dabrahams@apple.com" target="_blank">dabrahams@apple.com</a>&gt; wrote:<br>
&gt;<br>
&gt;     on Sun Apr 10 2016, Xiaodi Wu &lt;<a href="http://xiaodi.wu-AT-gmail.com" rel="noreferrer" target="_blank">xiaodi.wu-AT-gmail.com</a>&gt; wrote:<br>
&gt;<br>
&gt;     &gt; On Sun, Apr 10, 2016 at 3:58 PM, Haravikk<br>
&gt;     &lt;<a href="mailto:swift-evolution@haravikk.me" target="_blank">swift-evolution@haravikk.me</a>&gt; wrote:<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; On 10 Apr 2016, at 14:25, Xiaodi Wu<br>
&gt;     &lt;<a href="mailto:xiaodi.wu@gmail.com" target="_blank">xiaodi.wu@gmail.com</a>&gt; wrote:<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; What types do you have in mind that would only support positive<br>
&gt;     distances?<br>
&gt;     &gt;&gt; All numeric types (yes, even UInt, etc.) have signed distances, which<br>
&gt;     &gt;<br>
&gt;     &gt;&gt; reflects the basic mathematical abstraction of a number line.<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; Say you wanted to stride through a singly-linked list, it would actually<br>
&gt;     be<br>
&gt;     &gt;&gt; beneficial to support only forward strides, the same is true of<br>
&gt;     sequences,<br>
&gt;     &gt;&gt; as you either may not know what the endpoint is, or would have to step<br>
&gt;     &gt;&gt; through the whole sequence to find it (plus buffer every value in order<br>
&gt;     to<br>
&gt;     &gt;&gt; do-so safely).<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; A consistent behavior with signed distances is so important that we are<br>
&gt;     &gt;&gt; currently struggling with an interesting issue with floating point types,<br>
&gt;     &gt;&gt; which is that due to rounding error 10.0 + a - a != 10.0 for some values<br>
&gt;     of<br>
&gt;     &gt;&gt; a.<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; While that’s interesting I’m not sure why the sign is important; to me a<br>
&gt;     &gt;&gt; stride is a width so it being negative makes no sense. For example, say I<br>
&gt;     &gt;&gt; laid an array of Ints, organised into groups of five (and also that I’m<br>
&gt;     &gt;&gt; lunatic who won’t use a tuple for this), the stride of this array is 5<br>
&gt;     &gt;&gt; whether I’m stepping through it forwards or backwards. Imagine I defined<br>
&gt;     &gt;&gt; this like so (more realistically it’d be a struct or a class):<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; typealias StridedIntegerArray:(stride:Int, array:[Int])<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; If the stride is set to 5, it’s always 5, the only thing that changes is<br>
&gt;     &gt;&gt; whether I want to stride from the start or end of the array, plus I could<br>
&gt;     &gt;&gt; things like:<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; myStridedIntegerArray.prefix(from: 2).striding(forwardBy:<br>
&gt;     &gt;&gt; myStridedIntegerArray.stride) // Returns element at index 2, 7, 12, etc.<br>
&gt;     &gt;<br>
&gt;     &gt; When you have a sequence returning elements at index 12, 7, 2, etc.,<br>
&gt;     &gt; wouldn&#39;t you call the stride size -5? I would, because 12 + (-5) = 7.<br>
&gt;     &gt;<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; It just occurred to me that perhaps you intended this method only for<br>
&gt;     ranges<br>
&gt;     &gt;&gt; specifically and that perhaps I’m confusing things, but it seems to me<br>
&gt;     like<br>
&gt;     &gt;&gt; it should be a method for all sequences (with reverse stride available on<br>
&gt;     &gt;&gt; collections with a reverse index type) returning a generator that only<br>
&gt;     &gt;&gt; returns (or computes) every Nth element, for generic<br>
&gt;     sequences/collections<br>
&gt;     &gt;&gt; this would take the start or end index and use advanced(by:), though<br>
&gt;     again,<br>
&gt;     &gt;&gt; I kind of feel like that should be two separate methods as well, but<br>
&gt;     that’s<br>
&gt;     &gt;&gt; for another issue I think.<br>
&gt;     &gt;<br>
&gt;     &gt; I don&#39;t think it should be for ranges only, but ranges are the extent<br>
&gt;     &gt; of this proposal.<br>
&gt;     &gt;<br>
&gt;     &gt; That said, my own opinion is that striding should not be available on<br>
&gt;     &gt; sequences but on collections only. In their most commonly used form,<br>
&gt;     &gt; integer strides take a start and end, and there is a finite number of<br>
&gt;     &gt; things to stride over; thus, in my reasoning, strides can be extended<br>
&gt;     &gt; to cover anything else that has a known start and end and has a finite<br>
&gt;     &gt; number of things, which is guaranteed by conformance to Collection but<br>
&gt;     &gt; not to Sequence.<br>
&gt;<br>
&gt;     I dunno; it seems to me that if someone gives me a Sequence I should be<br>
&gt;     able to traverse it, skipping every other element. I don&#39;t see why<br>
&gt;     “stride” should be inapplicable here.<br>
&gt;<br>
&gt;     &gt; (At the moment, StrideTo/Through conforms to Sequence and not to<br>
&gt;     &gt; Collection, but that is considered something to be fixed and we will<br>
&gt;     &gt; see if we can address that as part of this set of stride overhauls.)<br>
&gt;     &gt;<br>
&gt;     &gt; As I see it, we agree on the problem: the current algorithm cannot<br>
&gt;     &gt; accommodate singly linked lists and sequences because those things do<br>
&gt;     &gt; not have a known endpoint if you begin an attempt to stride. However,<br>
&gt;     &gt; my conclusion is the opposite of yours: namely, that they should not<br>
&gt;     &gt; have stride. Maybe they should have something similar, but it<br>
&gt;     &gt; shouldn&#39;t be stride.<br>
&gt;     &gt;<br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt; On Sun, Apr 10, 2016 at 12:53 PM Haravikk via swift-evolution<br>
&gt;     &gt;&gt; &lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt; On 10 Apr 2016, at 11:17, Brent Royal-Gordon<br>
&gt;     &lt;<a href="mailto:brent@architechies.com" target="_blank">brent@architechies.com</a>&gt;<br>
&gt;     &gt;&gt;&gt; wrote:<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt; Why not just assign it the correct sign during the init function?<br>
&gt;     &gt;&gt;&gt; (0 ... 6).striding(by: 2) // [0, 2, 4, 6], end &gt; start, so stride = by<br>
&gt;     &gt;&gt;&gt; (6 ... 0).striding(by: 2) // [6, 4, 2, 0], start &gt; end, so stride = -by<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt; One reason not to do it this way is that, if we extend `striding(by:)`<br>
&gt;     to<br>
&gt;     &gt;&gt;&gt; other collections, they will not be as easy to walk backwards through as<br>
&gt;     &gt;&gt;&gt; this. You will have to do something like<br>
&gt;     &gt;&gt;&gt; `collection.reversed().striding(by:)` which will be a hassle.<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt; Any thoughts on the alternative I mentioned a little earlier to define<br>
&gt;     &gt;&gt;&gt; overloads instead of positive/negative? i.e- you would have two methods,<br>
&gt;     &gt;&gt;&gt; .striding(forwardBy:) and .striding(backwardBy:). In addition to<br>
&gt;     eliminating<br>
&gt;     &gt;&gt;&gt; the use of a negative stride to indicate direction, this has the<br>
&gt;     advantage<br>
&gt;     &gt;&gt;&gt; that .striding(backwardBy:) can be defined only for types with a<br>
&gt;     &gt;&gt;&gt; ReverseIndex or only for collections (as you can stride through a<br>
&gt;     sequence,<br>
&gt;     &gt;&gt;&gt; but only by going forward).<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt; This should also make documentation a bit clearer, otherwise you’ve got<br>
&gt;     &gt;&gt;&gt; the caveat that to go backwards requires a negative value, but only if<br>
&gt;     the<br>
&gt;     &gt;&gt;&gt; type supports that, which a developer would then need to check. Instead<br>
&gt;     it<br>
&gt;     &gt;&gt;&gt; either has the backwardBy variant or not.<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt; I know that advance(by:) supports negative values, but this is actually<br>
&gt;     &gt;&gt;&gt; something I wouldn’t mind seeing changed as well, as it has the same<br>
&gt;     issues<br>
&gt;     &gt;&gt;&gt; (passing a negative value in looks fine until you realise the type is a<br>
&gt;     &gt;&gt;&gt; ForwardIndex only). It would also allow us to define Distance types that<br>
&gt;     &gt;&gt;&gt; don’t support a direction, since this would be given by the choice of<br>
&gt;     method<br>
&gt;     &gt;&gt;&gt; called instead.<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt;<br>
&gt;     &gt;&gt;&gt; Of course I’d still like to be able to define 6 … 0 or whatever, but<br>
&gt;     this<br>
&gt;     &gt;&gt;&gt; would at least eliminate what I dislike about using negatives for<br>
&gt;     direction.<br>
&gt;     &gt;&gt;&gt; _______________________________________________<br>
&gt;     &gt;&gt;&gt; swift-evolution mailing list<br>
&gt;     &gt;&gt;&gt; <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
&gt;     &gt;&gt;&gt; <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
&gt;     &gt;&gt;<br>
&gt;     &gt;&gt;<br>
&gt;<br>
&gt;     --<br>
&gt;     Dave<br>
&gt;<br>
&gt; _______________________________________________<br>
&gt; swift-evolution mailing list<br>
&gt; <a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
&gt; <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
<br>
--<br>
Dave<br>
<br>
_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
</blockquote></div>