dropFirst v dropLast

Using Swift
1

In the following fragment "foo" compiles and "bar" doesn't.

// @inlinable public func dropLast(_ k: Int) -> ArraySlice<Element>
// @inlinable public func dropFirst(_ k: Int = 1) -> ArraySlice<Element>

func foo() {
    var array = [1, 2, 3, 4, 5]
    array = v.dropLast(1)
}

func bar() {
    var array = [1, 2, 3, 4, 5]
    array = array.dropFirst(1)
// ❌Error No 'dropFirst' candidates produce the expected contextual result type '[Int]'
}

I know that "array subscript" is not array itself and I can do:

array = Array(array.dropFirst(1))

to fix "bar". That's not the question.

I included "dropLast" / "dropLast" prototypes above and they return the same type. Perhaps I am looking at the wrong prototypes and there is some overload for "dropLast" that returns array and no such overload for "dropFirst"? This is further supported by the fact that if I use a separate temporary variable I can break "foo" as well:

let x = array.dropLast(1)
array = x // ❌ Cannot assign value of type 'Array<Int>.SubSequence' (aka 'ArraySlice<Int>') to type '[Int]'

The question is:

  1. why do we have this overload for "dropLast" to begin with?
  2. complexity of "let x = array.dropLast(1)" is known to be O(1). Is complexity of "array = array.dropLast(1)" also O(1)? I presume there's an invisible "array = Array(...)" conversion in there.
  3. if (1) is a good reason, should we have this overload for "dropFirst" as well?
1 Like
2

I think the dropLast you're using is the one from Sequence

why do we have this overload for "dropLast" to begin with?

because sequence doesn't have a subsequence type, so it returns Array instead of a subsequence. Array then inherits that overload because of the Collection conformance

complexity of "let x = array.dropLast(1)" is known to be O(1). Is complexity of "array = array.dropLast(1)" also O(1)? I presume there's an invisible "array = Array(...)" conversion in there.

from the docs " Complexity: O( n ), where n is the length of the sequence."

if (1) is a good reason, should we have this overload for "dropFirst" as well?

"dropFirst" for Sequence already exists, and it returns a lazy wrapper which works even for infinite sequences. Returning Array would be worse

2 Likes
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