dropFirst v dropLast

Using Swift
3

dropLast is indeed overloaded here; specifically, you're seeing the difference between

  1. Sequence.dropLast(_:), which returns an explicitly-typed [Self.Element], and
  2. BidirectionalCollection.dropLast(_:), which returns Self.SubSequence

Array conforms to both protocols, so without explicit typing, either one can get called, which may be unfortunate. To answer your questions:

  1. The overload exists because this is a useful operation, but Sequences can't be sliced. The only way for the operation to exist is for something to collect the results of iterating the Sequence and drop the last N elements on the floor
  2. No, the Sequence version of the method is O(n), which means that reassigning array = array.dropLast(1) goes through an O(n) copy, which you'll want to avoid. Yes, this is subtle!
    • It may be possible for the Sequence implementation to optimize this by checking if Self == Array and using some Array internals to avoid a copy via CoW, but I don't know the specifics off the top of my head, and it simply doesn't do this at the moment
  3. We don't need an overload for dropFirst, since Sequence.dropFirst(_:) can already drop the first N element in the sequence (by iterating forward and ignoring the results) in "O(1)" time

This situation is very similar to Is Swift array reversed()[n] efficient or not? - Stack Overflow and Missed optimization in ReversedCollection?

3 Likes