Stride Operators, (a..<b)/step and (a...b)/step


(Tony Y) #18

Maybe, we need a new generic structure like an ArraySlice with a stride for
subscript (stride:) -> ArrayStrideSlice { get }.


(Tony Y) #19

Maybe, we need a Slice structure with a stride, which might be named as StrideSlice.

Here is the definition of the Slice structure from swift/stdlib/public/core/Slice.swift.

public struct Slice<Base: Collection> {
  public var _startIndex: Base.Index
  public var _endIndex: Base.Index
  internal var _base: Base
  public init(base: Base, bounds: Range<Base.Index>) {
    self._base = base
    self._startIndex = bounds.lowerBound
    self._endIndex = bounds.upperBound
  }
  public var base: Base {
    return _base
  }
}

The Index of Collection is Comparable.

public protocol Collection: Sequence where SubSequence: Collection {
  associatedtype Index : Comparable
}

So, StrideSlice might be defined as:

public struct StrideSlice <Base: Collection> {
  public var _startIndex: Base.Index
  public var _endIndex: Base.Index
  public var _stride: Base.Index.Stride
  internal var _base: Base
  public init(base: Base, strideTo: StrideTo<Base.Index>) {
    self._base = base
    self._startIndex = strideTo.start
    self._endIndex = strideTo.end
    self._stride = strideTo.stride
  }
  public var base: Base {
    return _base
  }
}

The Index of Collection should be Strideable.

public protocol Collection: Sequence where SubSequence: Collection {
    associatedtype Index : Strideable
}

(Letanyan Arumugam) #20

FWIW StrideTo and StrideThrough are both Sequence's, so the subscript functionality could be done by generalising this functionality onto a Collection taking a Sequence.

extension Collection {
  // should have some specialised return type instead of Array<Element>
  subscript<S: Sequence>(seq: S) -> [Element]
  where S.Element == Index {
    var result = [Element]()
    for i in seq {
      result.append(self[i])
    }
    return Array(result)
  }
}

let x = Array(1...10)

print(x[stride(from: 0, to: 10, by: 2)])
print(x[sequence(first: 0) { $0 + 2 >= 10 ? nil : $0 + 2 } ])

This has the obvious added benefit of working with any sequence as a subscript, though I’m not sure why Swift doesn’t have this already though. I can’t see many downsides to having this, but I’m sure someone will point them out :slight_smile:


(Tony Y) #21

If a Slice instance with stride is used, we can save memory when performing forEach, map, or etc.

x[stride(from: 0, to: 100000, by: 2)].forEach {...}
let y = x[stride(from: 0, to: 100000, by: 2)].map {...}

(Tony Y) #22

.+= or ..+= might be better than ..+ and .++.

for x in -10 ..+= 4 {
    print(x)
    break
}
Array(10 ..+= -4 ... -10)
Array(-10 ..+= 4 ..! 10)

(Jens Persson) #23

I wonder how many readers reacted on the fact that your statement is making the invalid assumption that “any sequence” is multi-pass, breaking the (current) semantic requirements of Sequence.

This is a very common mistake (that I myself use(d) to make). After I realized this, I started this thread which might be an Interesting read.

EDIT: No, I was wrong, your subscript will work as expected even with a single-pass sequence.


(Maik) #24

Isn’t % the operator that feels intuitive?

Array(-10 ..< 10) // [-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array((-10 ..< 10) % 4) // [-10, -6, -2, 2, 6]
Array(-10 ... 10) // [-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array((-10 ... 10) % 4) // [-10, -6, -2, 2, 6, 10]

You normally expect the remainder to be returned, so probably it’s not that good. What do you think?


#25

Is it? It appears to only be doing a single pass over seq to me (the for-in loop). What am I missing?


(Jens Persson) #26

You are right, I misread the code (It’s almost as if I want to see everyone making these mistakes! :blush: ). Edited my post.


(Tony Y) #27

As @Chris_Lattner3 said for the / operator, the % operator would also be not preferable.


(Jon Hull) #28

Would it be possible to just use a contextual keyword “by” for this?

let x = 0...100 by 5

It feels very natural to me.


(Tony Y) #29

I think the keyword by should be the last option.


(Tony Y) #30

%% might be an option for the stride operator.

for i in -10 %% 4 {...}
for i in -10 %% 4 ..! 10 {...}

(Tony Y) #31

If you try the %% operator, replace the corresponding part of the previous implementation with the following code:

precedencegroup StrideFormationPrecedence {
    higherThan: RangeFormationPrecedence
    lowerThan: AdditionPrecedence
}

infix operator %% : StrideFormationPrecedence
infix operator ..! : RangeFormationPrecedence

func %% <T: Strideable>(start: T, step: T.Stride) -> Stride<T> {
    return stride(from: start, by: step)
}

(Tony Y) #32
for i in -10 %% 4 ... {...}

is beter than it, because the range expression ... is included. But, I cloud not implement this postfix operator .... Please help me!


(Tony Y) #33

I implemented the stride operator %% to create StrideTo from Range, StrideThrough from ClosedRange, and StrideFrom from CountablePartialRangeFrom, PartialRangeUpTo, and PartialRangeThrough. The StrideFrom structure is almost the same as the Stride structure introduced by @Alexandre_Lopoukhine.

For example,

Array(-10..<10%%4) // [-10, -6, -2, 2, 6]
Array(-10...10%%4) // [-10, -6, -2, 2, 6, 10]
for i in (-10)... %% 4 {
  print(i) // -10 -6 -2 2 6 10
  if i >= 10 { break }
}
for i in ..<10 %% -4 {
  print(i) // 6 2 -2 -6 -10
  if i <= -10 { break }
}
for i in ...10 %% -4 {
  print(i) // 10 6 2 -2 -6 -10
  if i <= -10 { break }
}

(Erica Sadun) #34

I spent some time playing around with this. I found that it feels less readable than using stride directly, for example:

// Clear, understandable, built using recognition
stride(from: 1, through: 10, by: 3)

// Depends more on interpreting intent
(1 ... 10) / 3
// Does this return (1/3, 2/3, 3/3, ...)?
// Does this return 1, 4, 7?
// Does this return 1..<4, 4..<7, 7..<10? or 1..<4, 4..<7, 7..<10, 10...10?

The answer is the first (because you state it wraps stride) but in doing so, it removes clarity to achieve concision and forces the use of parentheses.

Thank you for bringing up this topic. It gave me a lot to think about.


(Tony Y) #35

I fixed the %% operator for the half-open range stride with a negative stride.

-        return stride(from: left.upperBound, to: left.lowerBound, by: right)
+        return stride(from: left.upperBound.advanced(by: right), to: left.lowerBound.advanced(by: right), by: right)

Upon this fix, the reverse stride of the half-open range behaves as you expect:

Array(-10..<10 %% -4) // [6, 2, -2, -6, -10]

(Tony Y) #36

The generic structure Array has the instance property:

  var indices: CountableRange<Int> { get }

To create the stride range from this indices, I added the stride operators %% for CountableRange as well as CountableClosedRange.

Github link

For example:

let a = (0..<100).map { Double($0) }
for i in a.indices %% 20 { print(a[i]) } // 0.0 20.0 40.0 60.0 80.0
for i in a.indices %% -20 { print(a[i]) } // 80.0 60.0 40.0 20.0 0.0
let a = (0...100).map { Double($0) }
let range = CountableClosedRange(a.indices)
for i in range %% 20 { print(a[i]) } // 0.0 20.0 40.0 60.0 80.0 100.0
for i in range %% -20 { print(a[i]) } // 100.0 80.0 60.0 40.0 20.0 0.0

(Tony Y) #37

I am sorry. This fix is wrong. I fixed as the stride starts from the last element of the half-open range:

-        return stride(from: left.upperBound.advanced(by: right), to: left.lowerBound.advanced(by: right), by: right)
+        return stride(from: left.upperBound.advanced(by: -1), to: left.lowerBound.advanced(by: -1), by: right)

Github link

For example:

Array(-10..<10 %% -4) // [9, 5, 1, -3, -7]
let a = (0..<100).map { Double($0) }
for i in a.indices %% -20 {
  print(a[i]) // 99.0 79.0 59.0 39.0 19.0
}