Add an `adjacentPairs` algorithm to Sequence


(Michael Pangburn) #1

The full WIP proposal can be found here.
Below is a summary.

In line with recent proposals enhancing the Sequence and Collection APIs, the proposed algorithm seeks to simplify a common pattern: accessing adjacent elements in a sequence. Such a pattern can be seen as a general first step in performing an operation such as producing a sequence of the distances between points in a sequence or verifying that a sequence is sorted based on some predicate.

The algorithm returns a sequence containing two-tuples of adjacent elements in a sequence.

let pairs = (1...5).adjacentPairs()
// Array(pairs) == [(1, 2), (2, 3), (3, 4), (4, 5)]

The proposed algorithm deserves Standard Library support on the following grounds:

  • Commonality: Supports a common algorithm pattern: accumulating adjacent pairs of elements in a sequence, which can then be processed.
  • Readability: Improves call-site clarity; the concision of seq.adjacentPairs() reduces cognitive load when used in place of a for-loop.
  • Generality: Supports all Sequence conformances, including single-pass sequences.
  • Performance: Utilizes a specialized lazy sequence to avoid unnecessarily creating an intermediate array.
  • Correctness: Avoids a tempting one-line implementation that results in undefined behavior for single-pass sequences.

Additional examples, details, and an implementation are provided in the proposal sketch linked above.

Looking forward to feedback in developing in the proposal; if positive, I'm more than happy to open a PR with the implementation and tests.


Supporting collection slice by slices of a given size parameter
#2

I'm happy that this pitch is so well written. I appreciate that single-pass sequences are supported. I appreciate that it gives a name to this operation, so that other libraires that provide similar features don't have to look for proper vocabulary (reactive programming...). I hope this pitch turns into a full-fledged proposal soon.


#3

Yet I wonder why the resulting sequence is an Array, and is not lazy. For exemple, when one checks if a sequence is sorted, one wants to break the loop on the first badly ordered pair.


(Lance Parker) #4

A lazy variant would be great but you'd probably want to leave the Array providing version on Sequence and provide the lazy overload on LazySequence


#5

That sounds very sensible. I still lack reflexes regarding lazy sequences.


(TJ Usiyan) #6

+1 from me. I currently drop first and zip with self for this.


(Nate Cook) #7

I think using a wrapper type even for the non-lazy version is the way to go. Just like zip, this is often a transitory step toward computing some other value. A wrapper would also let us use adjacentPairs with infinite sequences like 1....


(Lance Parker) #8

Right you are! No real reason to have the Array version at all


(Michael Pangburn) #9

Thanks all for the feedback. Per @nnnnnnnn's suggestion, I've updated the proposal to return a specialized wrapper type for the single implementation on Sequence, with justification in Alternatives Considered.

Happy to hear any additional thoughts before I begin designing tests and moving forward in the PR-opening process.


(Antonino) #10

I suggest:

extension Sequence {
func adjacentPairs( circular:Bool = false ) -> Zip2Sequence<Self, Self.SubSequence> {
// ....
}
}

let pairs = (1...5).adjacentPairs()
// 'pairs' == [(1, 2), (2, 3), (3, 4), (4, 5)]

let pairs = (1...5).adjacentPairs( circular:true )
// 'pairs' == [(1, 2), (2, 3), (3, 4), (4, 5), (5,1)]

I have a similar function in my code and is usefull for producing an array of segments of a closed polygon, for example.


#11

@Loooop, your user name matches your pitch perfectly :-)

That's a really nice feature idea. I also sometimes have to deal with closed polygons whose representation does not end with the starting point, and I quite clearly see the use cases (computing path length, computing all normals to all segments, etc, etc, etc).


#12

@Loooop: Now I don't think adjacentPairs(circular: true) will pass the review: in the mind of many members of the forum, ad-hoc boolean arguments are not "swifty". While I wholeheartedly support the idea, it needs polish before we can convince the community.

First, what if that feature would not exist, and one wants to create his own circular collection of adjacent pairs?

Well, in the naive and straightforward way, it's painful. One can't conveniently add an element to a sequence unless that sequence is something like an array:

let values = [1, 2, 3]

var pairs = Array(values.adjacentPairs())
if let first = values.first {
    pairs.append((values.last!, first))
}
print(pairs) // [(1,2), (2,3), (3,1)]

This code is uneasy to read, and loses track of the goal. On top of that:

  • we lose the lazy nature of the resulting sequence.
  • we lose support for single-pass sequences
  • we have to check for emptiness
  • there is a force unwrap in sight and some will turn pale.

This explains which it is useful for the standard library to provide the feature, and free the developers from thinking too much about it.

Now, how should it look, since a boolean parameter is not the way to go?

Well, what about another method?

var pairs = values.circularAdjacentPairs()
var pairs = values.loopingAdjacentPairs()
var pairs = values.cyclingAdjacentPairs()

#13

Oh, and we also have to check if @mpangburn thinks that the looping version is a useful addition to his pitch :-)


(Michael Pangburn) #14

@Loooop @gwendal.roue I can see the utility of a version containing a pair of the last and first elements for working with polygons; do you have any other use cases in mind?
Without too much thought, the number of occasions on which there exists a meaningful relationship between the last and first elements of a sequence seems much fewer to me.


#15

That's a very natural question. I personally only see graphical uses. Cycling data structures are not so common, are they? I'm not familiar enough with rings et al. May I summon the mathematical culture of @Fryie for more ideas?


(Pierpaolo Frasa) #16

Rings don't really have anything to do with cyclical structure, the name is an oddity as are most in mathematics.

Some ideas where "cycles" appear in mathematics, though:

  • modular arithmetic: this includes clock time and weekdays—24 hours from now the clock will show the same number
  • rotations and reflections: if you rotate something 360 degrees, you're back where you started; if you take the reflection of the reflection, you get the original, etc. All this is closely related to symmetries of objects.
  • permutation groups: Let's say you have three cards. If you move the first card to the second position, the second to the third and the third to the first, then repeat that same exchange twice, you're back where you started.
  • complex roots of unity: best shown by this image
  • graph theory: Cycles are pretty important here for a number of reasons (e.g. trees are connected acyclic graphs, which means, if you find a cycle, it's not a tree)

Of course there's also periodic functions like sine, cosine, but those are probably less relevant since they are not discrete .

I'm not sure if that helps though. :)

edit: Maybe someone more versed in computer science should chime in, though. There are certainly cyclic data structures, but I couldn't say too much about how often and where they are commonly used. Off the top of my head, maybe in relation to process scheduling or something?


(Michael Pangburn) #17

I've opened a PR on apple/swift-evolution with the proposal along with a link to the corresponding implementation PR on apple/swift.

Thanks to all for your feedback during the pitch!


#18

Thanks for writing it up. You probably don't need to address this in the proposal, but just a heads up that the discussion around opaque result types is probably relevant here, since AdjacentPairsSequence seems like a good candidate for hiding in this way.