Naming of `rotate(at:)`

The index parameter of rotate(at:) is confusing to me.

var numbers = [10, 20, 30, 40, 50, 60]
let p = numbers.rotate(at: 2)
// numbers == [30, 40, 50, 60, 10, 20]

"Rotate at" sounds like it's the center point of a pivot; it sounds similar to "rotate around". The operation here is not rotating around that point at all, so that's a confusing metaphor. Perhaps a better metaphor is to imagine it like a Rolodex, and we're rotating to a particular index?

mutating func rotate(to index: Index) -> Index

Also, the readme gives very little discussion of the return value. I believe it's the new index where the item at the start index now lives? Is that correct?

4 Likes

I had thought that previous iterations of the discussion here had settled on something like: rotate(shiftingToStart:)?

That name was addressed in the readme as well:

Naming

The index parameter has been proposed as shiftingToStart in the past; this proposal uses the simpler at label. shiftingToStart introduces the idea of a "shift", which can sound like shifting just that single element to the beginning of the collection.

shiftingToStartAt seems to fix that problem.

That problem is solvable; if it is desired to remove the word "shift", we can name it instead: rotate(toStartAt:)--or even, perhaps, just rotate(to:).

7 Likes

This one is on me! As hinted at in the README, this was intended to be rotate(toStartAt:). The shorter at label was an earlier version that apparently snuck through the gates.

10 Likes

I know that the following is not the goal of this algorithm, but I would personally prefer a rotate(by:) method to rotate clockwise and counterclockwise more easily knowing by how many places to rotate:

var numbers = [10, 20, 30, 40, 50, 60]

numbers.rotate(by: 2)  // rotates left by 2 places
// numbers == [30, 40, 50, 60, 10, 20]
numbers.rotate(by: -1) // rotates right by 1 place
// numbers == [20, 30, 40, 50, 60, 10]

Is there a particular reason it's more useful to rotate giving an element index and returning the index that the element that previously was first now has?

Thinking of simple algorithms in which you need to rotate matrix rows, such as in the AES cryptosystem, I find more useful to think in terms of shifted amount.

Edit: MATLAB does the same.

2 Likes

Wait, which way is clockwise vs. counterclockwise? Or left vs. right? Don't answer; my point is those directions are based on how we describe rotation with diagrams in our computer science textbooks. They're all meaningless when looking from a (for example) memory chip perspective. But rotating-towards-start or -end is pretty clear since we already use terms like startIndex or endIndex.

These methods would be the same as using the index-offset functions to get the new baseline then calling the towards-start/end rotation methods. They could still be useful extension methods, but the labels need to clarify which way a positive amount will move values.

1 Like

I agree with the arbitrariness of the rotation direction, but there are contexts in which you have such arbitrariness and you need to check the documentation first to know how offsetting works (like in any coordinate system, in iOS the y-axis is pointing downwards instead of upwards).

The pros of an offset based rotation are:

  • you don't need to know the Index type of the specific collection, you can pass an offset which is an Int and easier to use (if the Index type wasn't trivial, to get the 3rd element you would have to use the offset to get the index, why not using the offset directly at that point?);
  • you can trivially get the inverse function by using the opposite offset.

The pros of an "index of the element you want to scroll left to become to first element of the circularly shifted collection" are:

  • rotate(toStartAt:) is self-explanatory. Is it? Does rotate(toStartAt:) mean "rotate to let the element at the given index become the first element" or "rotate to let the collection start at the given index, i.e. placing the first element at the given index and the last elements on its left"?

Based on the MATLAB's approach and @LucianoPAlmeida's RotatedCollection I would like to rewrite my suggestion with:

var numbers = [10, 20, 30, 40, 50, 60]
numbers.rotate(by: 2)  // numbers == [50, 60, 10, 20, 30, 40]

var numbers = [10, 20, 30, 40, 50, 60]
numbers.rotate(by: -1) // numbers == [20, 30, 40, 50, 60, 10]

extension MutableCollection {
    func rotate(by offset: Int) { ... }
    func rotate(subrange: Range<Index>, by offset: Int) { ... }
}

with offset having the same meaning of the Collection.formIndex(_:offsetBy:) method.

Once people get a taste of this, there will be clamoring for both directions on more general-purpose overloads. Is a negative position a better choice than a negative translation vector? I don't think so, but I'm pretty sure they amount to the same thing.

My mental model/approach is translation vector-based:

public extension Sequence {
  func shifted(by shift: Int) -> AnySequence<Element> {
    shift >= 0
      ? dropFirst(shift) + prefix(shift)
      : suffix(-shift) + dropLast(-shift)
  }

  /// Combines two `Sequence`s.
  static func + <Sequence1: Swift.Sequence>(sequence0: Self, sequence1: Sequence1) -> AnySequence<Element>
  where Sequence1.Element == Element {
    .init { () -> AnyIterator<Element> in
      var iterators = ( sequence0.makeIterator(), sequence1.makeIterator() )
      return .init { iterators.0.next() ?? iterators.1.next() }
    }
  }
}

I always confused about its name. For me rotation is moving around center.
So [1, 2, 3, 4, 5, 6].rotate(by: 2) will return something like [6, 5][4, 3, 2, 1]

Rotation doesn't change ordering (other than wrapping). Think of a clock face; if I turn it so that 12 isn't at the top, the numbers still appear in the same order--only the start point changes. So the two most plausible interpretations of rotate(by: 2) are:

[3,4,5,6,1,2] // offset 2 rotated to start.
[5,6,1,2,3,4] // start rotated to offset 2.

the challenge is to pick naming that disambiguates these two alternatives (n.b.: personally, in practice I don't think this is a big deal. It's a convention, people who use the operation will get used to it even if the name is slightly ambiguous).

In a perfect world, I would probably call this operation a "block swap" or something like that, but "rotate" is the term of art that computer science has settled on for this operation.

4 Likes

How about rotate(left:2) and rotate(right:2)?

3 Likes

Collections don't have a notion of "left" or "right".

Even if they did, and even if we ignore languages that write them right-to-left, there's a very reasonable argument that it should be the reverse of what a non-technical English speaker might expect ("on a little-endian system--including both x86 and arm64--right shifting an big integer moves bytes from higher indexed to lower, so a 'right' rotation by 2 should produce [3,4,5,6,1,2]").

3 Likes

I sometimes use these terms by accident as well, but I think the better terms are “head” and “tail” or to speak of the collection’s “leading” and “trailing” ends.

Of course, Swift’s Collection protocol also defines “startIndex” and “endIndex” properties, so implicitly there must be some position called the “start” and “end”.

This may sound kind of obscure, but it’s good to be consistent with your terminology.

5 Likes

Could you elaborate on this some more?

An array literal has a notion of left-to-right. And when you print an array, its elements are printed left-to-right.

While it may be understandable to talk about "left" and "right" when it comes to Arrays for the reasons you note, neither of those apply to collections in general (arbitrary collection types may not conform to ExpressibleByArrayLiteral and may print their contents in some format other than just left-to-right). There's no general requirements that Collection-conforming types model something which it makes sense to talk about in terms of "left" and "right".

I think an example would help me understand your concerns.

Suppose we had a Grid type which was modeled as a collection of Rows. A rotation operation on this collection would correspond directionally to "up" and "down", not "left" and "right". An operation called as, say, grid.rotate(leftBy: 3) would be downright misleading.

1 Like

An array literal has a "start" and "end". They happen to be "left" and "right" in source code because Swift reads left-to-right. But if I were printing the contents of an array into a string in a language that reads right to left, the start would appear on the right and the end on the left. You can see a version of this here: Compiler Explorer (The location of the trailing [ looks like a bug on Linux). You can clearly see in the output that 1 ends up on the right and 3 on the left. Start/end is the salient distinction, not right/left.

2 Likes