Sequence.removeFirst(Int) inconsistency

Using Swift
1

Sequence has two overloads of removeFirst():

  • Sequence.removeFirst() -> Element, which removes the first elements,
  • Sequence.removeFirst(_ n: Int), which removes the first n elements, but doesn't return them as a SubSequence. I think part of the issue here is the SubSequence got moved down to Collection, but I'm not sure.

I'm trying to fix this by implementing my own extension:

extension Collection {
	mutating func removeAndReturnFirst(_ n: Int) -> SubSequence {
		defer { self.removeFirst(n) }
		return self.prefix(n)
	}
}

... but I get a funky error I can't figure out:

Untitled 5.swift:3:16: error: referencing instance method 'removeFirst' on 'Collection' requires the types 'Self' and 'Self.SubSequence' be equivalent
                defer { self.removeFirst(n) }
                             ^
Swift.Collection:1:11: note: where 'Self' = 'Self', 'Self.SubSequence' = 'Self.SubSequence'
extension Collection where Self == Self.SubSequence {
          ^

I don't see why this requirement exists. What stops me from doing this?

var s: String = "ABCDEF"
let firstThree: Substring = s.removeAndReturnFirst(3)
assert(firstThree == "ABC")
assert(s == "DEF")

If I add the constraint it's bugging me about, then I can only operate on collections where Self == Self.SubSequence, such as Substring, and ArraySlice, but not String or Array.

extension Collection where Self == Self.SubSequence {
    mutating func removeAndReturnFirst(_ n: Int) -> SubSequence {
        defer { self.removeFirst(n) }
        return self.prefix(n)
    }
}

var s: Substring = "ABCDEF" // I'm forced to use Substring here
let firstThree: Substring = s.removeAndReturnFirst(3)
assert(firstThree == "ABC")
assert(s == "DEF")

Can somebody please explain:

  1. Why I'm forced to add this constraint?
  2. Why Sequence.removeFirst(_ n: Int) wasn't design to return a subsequence?
2
  1. Because the implementation takes an appropriate SubSequence and assign it to self.
  2. As you said, SubSequence belongs to Collection, not Sequence as per SE-0234. Also, I couldn't find removeFirst, only dropFirst.

Edit:

Re-reading the post, it seems you're thinking about Collection, not Sequence. If so, the new-answer would be:

  1. Again, because the implementation requires that you can assign a SubSequence to self.
  2. Returning the removed element would require another construction of SubSequence, which you can already get using Collection.prefix(_:), and it doesn't seem to save you anything to do it within removeFirst function.
4

Also, you probably want to use RangeReplaceableCollection.removeFirst(_:), not Collection.removeFirst(_:).

5

From the documentation of Collection (not Sequence, a sequence can just give you the next element if any, unlike a collection):

Available when Self is SubSequence.

1 Like
6

Interesting. You have me the idea to specialize this for String, and it works:

extension String {
    mutating func removeAndReturnFirst(_ n: Int) -> SubSequence {
        defer { self.removeFirst(n) }
        return self.prefix(n)
    }
}

var s = "ABCDEF" // I'm forced to use Substring here
let firstThree: Substring = s.removeAndReturnFirst(3)
assert(firstThree == "ABC")
assert(s == "DEF")

I guess String's removeFirst(_ n:) is unconditional .. digging into it, RangeReplaceableCollection was the ticket!

extension RangeReplaceableCollection {
    mutating func removeAndReturnFirst(_ n: Int) -> SubSequence {
        defer { self.removeFirst(n) }
        return self.prefix(n)
    }
}

var s = "ABCDEF" // I'm forced to use Substring here
let firstThree: Substring = s.removeAndReturnFirst(3)
assert(firstThree == "ABC")
assert(s == "DEF")
7

Yea, looking at your post, it seems you're indeed looking for RangeReplaceableCollection. Swift does have a lot of protocols in Sequence/Collection hierarchy, it does help to familiarize those.

8

Beware this is a very inefficient extension (on any COW Collection type, not just String) and I wouldn't recommend it.

What is going to happen here is self.prefix is going to create a Substring which holds a deferred copy of the outer string. So on return the string buffer will be multiply referenced. Then the deferred removeFirst mutates this multiply-referenced string buffer, triggering the actual copy. This means mutating the string will be not just O(n) but also allocating.

But outside of this, I think you should reexamine your approach to use subsequences in general. It is probably worth considering a redesign where you instead start with a Substring (created with mystr[...]) and then eat from the front of that substring. This is better not just because it avoids the O(n) nature of removeFirst (because removing the front of a substring is just a question of moving the index of the starting bound). I think the objc.io folks have some material on this approach with strings that's worth taking a look at.

2 Likes
9

…which is the reason the API wasn't designed this way to begin with.

10

Thanks for the explanation! I'll switch to using Substrings :slight_smile: