[stdlib] Collection mutators availability inconsistent

Evolution Discussion
1

Collections have mutating functions for removing the first and last element.
One of these is popLast(), which will safely check if the collection is empty before popping the last element.

So calling popLast() is like doing:
if !collection.isEmpty {
  collection.removeLast()
}

There also exists a popFirst() function, but what I find inconsistent is that popFirst() is only available on ArraySlice.

Example:
var collection = [1, 2, 3, 4]
collection.removeFirst() // works fine
collection.removeLast() // works fine
let last = collection.popLast() // works fine
let first = collection.popFirst() // Compile error: [Int] is not convertible to 'ArraySlice<Int>'

Is it intended that popLast() is available on collections, but popFirst() is not?

– Louis D'hauwe

2

Hi Louis,

I believe the difference is due to the performance guarantees. One can only efficiently implement `popFirst` and `removeFirst` on slices, where it’s just a matter of index manipulation. Removing the first element of a Collection is potentially an O(n) operation. Using `popFirst` in a loop in some algorithm would result in a quadratic complexity.

So the reason is: we only provide `popFirst` in a context where it is guaranteed to be O(1). Same applies to `popLast`, actually.. I think.

To reiterate what I mentioned in your pull request <Sign in to GitHub · GitHub

This case clearly identifies the flaw in the design of these methods, solving which might become a part of a follow-up to this proposal <https://github.com/apple/swift-evolution/blob/master/proposals/0132-sequence-end-ops.md&gt;one day.

Max

···

On Oct 18, 2016, at 11:16 AM, Louis D'hauwe via swift-evolution <swift-evolution@swift.org> wrote:

Collections have mutating functions for removing the first and last element.
One of these is popLast(), which will safely check if the collection is empty before popping the last element.

So calling popLast() is like doing:
if !collection.isEmpty {
  collection.removeLast()
}

There also exists a popFirst() function, but what I find inconsistent is that popFirst() is only available on ArraySlice.

Example:
var collection = [1, 2, 3, 4]
collection.removeFirst() // works fine
collection.removeLast() // works fine
let last = collection.popLast() // works fine
let first = collection.popFirst() // Compile error: [Int] is not convertible to 'ArraySlice<Int>'

Is it intended that popLast() is available on collections, but popFirst() is not?

– Louis D'hauwe
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

3

Hi Louis,

I believe the difference is due to the performance guarantees. One can
only efficiently implement `popFirst` and `removeFirst` on slices,
where it’s just a matter of index manipulation.

Well, and on deques, doubly-linked lists, and circular buffers.

Removing the first element of a Collection is potentially an O(n)
operation. Using `popFirst` in a loop in some algorithm would result
in a quadratic complexity.

So the reason is: we only provide `popFirst` in a context where it is
guaranteed to be O(1). Same applies to `popLast`, actually.. I think.

Right.

···

on Tue Oct 18 2016, Max Moiseev <swift-evolution@swift.org> wrote:

--
Dave