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


(Ted van Gaalen) #1

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

What if you are already somewhere in the middle (perhaps landed there by means of some other reference/link) of that linked list and want to stride backward?

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.

Of course !
This is known (in computer domain) since ca. 1938.. (Konrad Zuse, with 22-bit floats)
(btw I am glad that computer development in this critical war times especially in
nazi-Germany was extremely slow, relatively speaking, just imagine...)

So, this should come as no surprise.
Precision loss occurs with all arithmetic operations on floats.
(in the above case probably the intermediate
expression evaluation around the != ,
Compiler optimization may also cause
even further reduction of floating point precision )

Obviously, when working with floating point numbers
one must always be aware of this and design/program
accordingly. This should become second nature.

E.g. it is perfectly acceptable and known (also in classical for-loops)
that
    (0.0…1.0).by(0.1)
is not guaranteed to reach the humanly expected value of 1.0.

Due to the nature of what mostly is done in the floating point numbers domain,
this does not often cause problems (e.g like working with a slide ruler)

if it is important to reach the “expected end” then one could
-add a precision loss compensating value like so
      (v1…v2 + 0.1)
-or generate the desired float sequence within an integer loop **

The whole point with stride() here is perhaps because the attempt
to treat Continuous Data (floats) as Discrete Data (Integers) ?

What about range operator?
   with floats, (a…b) will never work correctly (accept this as normal, inherent with floats)

I’d suggest
    (a<.<b) or (b<..<a) , depending on whether a < b or b < a

In the stride function, swap a and b depending on the sign of the step value
(see a previous email from me for an example, I also had
a bounds tolerance factor implemented in that code
as an attempt to cope with float boundary “problems” )

** The whole problem would disappear if one would generate the desired float collection within an integer iteration
e.g.

   for i in 0..<10
   {
       ar.append(vstart + Double(i) * vstep)
   }

https://en.wikipedia.org/wiki/Floating_point,
especially the topic "Minimizing the effect of accuracy problems” might be interesting here.

n.b. in Pascal, the for loop has also a “downto” keyword.

Kind regards

TedvG


(Haravikk) #2

You can’t; if it’s singly-linked then there’s no way to do that directly with the target of O(1) complexity, i.e- for every step backward you’d have to start again from the beginning of the list and step forward till you reach the correct element, which would make it O(n) performance. For this reason, a singly linked list would want to provide only a ForwardIndex, as it isn’t suited to stepping backwards through its elements (that’s what a doubly-linked list is for, at the cost of even more overhead).

···

On 10 Apr 2016, at 22:44, Ted F.A. van Gaalen via swift-evolution <swift-evolution@swift.org> wrote:

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

What if you are already somewhere in the middle (perhaps landed there by means of some other reference/link) of that linked list and want to stride backward?


(Ted van Gaalen) #3

ah, you're right about that!
somehow there was a doubly linked list in my head, sorry.

TedvG

···

On 11 Apr 2016, at 11:20, Haravikk <swift-evolution@haravikk.me> wrote:

On 10 Apr 2016, at 22:44, Ted F.A. van Gaalen via swift-evolution <swift-evolution@swift.org> wrote:

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

What if you are already somewhere in the middle (perhaps landed there by means of some other reference/link) of that linked list and want to stride backward?

You can’t; if it’s singly-linked then there’s no way to do that directly with the target of O(1) complexity, i.e- for every step backward you’d have to start again from the beginning of the list and step forward till you reach the correct element, which would make it O(n) performance. For this reason, a singly linked list would want to provide only a ForwardIndex, as it isn’t suited to stepping backwards through its elements (that’s what a doubly-linked list is for, at the cost of even more overhead).