Should there be BidirectionalCollection.dropLast(while:)?

Using Swift
1

There is Collection.drop(while:) which drops elemenst from the beginning.

Look like Swift Algorithms added BidirectionalCollection.suffix(while:)

I think for symmetry and completeness, there should be BidirectionalCollection.dropLast(while:)

I needed this so I made one like this:

extension BidirectionalCollection {
    func dropLast(while predicate: (Element) throws -> Bool) rethrows -> Self.SubSequence {
        let suffix = try suffix(while: predicate)
        return dropLast(suffix.count)
    }
}

is there correct? is there better way?

1 Like
2

Avoid calling count on a non-RandomAccess collection, by leveraging the fact that a slice shares indices with its base collection:

return self[..<suffix.startIndex]

Or, using only standard library methods:

let i = try lastIndex{ try !predicate($0) }

guard let j = i else {
  return self[..<startIndex]
}

return self[...j]
3

I don't understand why this works to return the whole thing as Subsequence:

return self[..<startIndex]   // why is the range result in the entire thing as Subsequence?

is it because ..<startIndex is an empty range? Then shouldn't it be an empty Subsequence?

these two I can understand:

return self[..<endIndex]
return self[...]     // I prefer this form

Thanks for the answer, I learned something new about when not to use count

4

It returns an empty subsequence.

1 Like
5

okay, I understand now. The guard ... else { } is executed when every element in the collection match the predicate, so an empty Subsequence is returned.

:pray:

1 Like
6

Agreed!

is there a better way?

Your original is nearly perfect:

extension BidirectionalCollection {
    func dropLast(while predicate: (Element) throws -> Bool) rethrows -> Self.SubSequence {
        let suffix = try suffix(while: predicate)
        return self[..<suffix.startIndex]
    }
}

I might write @Nevin's suggestion this way:

extension BidirectionalCollection {
    func dropLast(while predicate: (Element) throws -> Bool) rethrows -> Self.SubSequence {
        let end = try lastIndex{ try !predicate($0) }.map(index(after:)) ?? startIndex
        return self[..<end]
    }
}
7

should endIndex be startIndex to return an empty collection? I think when lastIndex(where:) is nil, you are returning the whole collection. It should be empty.

1 Like
8

You're quite right, thanks

9

I think there is an off-by-one error: when lastIndex(where:) found an index, that index position need to be included in the SubSequence. This is what I did:

extension BidirectionalCollection {
    func droppedLast(while predicate: (Element) throws -> Bool) rethrows -> SubSequence {
        try lastIndex(where: { try !predicate($0) }).map { self[...$0] } ?? self[..<startIndex]
    }
}
10

The Algorithms package does include this method, with the name trimmingSuffix(while:) (implemented here). The package includes a variety of trimming methods, including trimmingPrefix(while:) — a method that shares the functionality of drop(while:) but is more predictably readable at the call site when written with a trailing closure.

Related to the implementation conversation in this thread, we discovered that there are a couple common operations that are used in implementing this kind of functionality: endOfPrefix(while:) and startOfSuffix(while:) (implemented here). startOfSuffix(while:) handles that off-by-one case without recalculating the trailing index.

2 Likes
11

Why are endOfPrefix(while:) and startOfSuffix(while:) internal? They seem to be generally useful.

12

Honestly, we just weren't sure if we had the names right or not. They should probably be public!

13

Should @young file an issue to request they be made public?

14

That would be great! @young, feel free to start a thread in the Swift Algorithms discussion, file an issue, or open a PR to make the change. Happy to discuss in any of those places.

15

Bah, that's what I get for hastyposting. Thanks for fixing my errors!

16

Here's a more elegant one that additionally shows why it's important to expose the bases of the standard library's adapter types:

extension BidirectionalCollection {
    func dropLast(while predicate: (Element) throws -> Bool) rethrows -> Self.SubSequence {
      let head = try self.reversed().drop(while: predicate)
      return self[head.endIndex.base..<head.startIndex.base]
    }
}
1 Like
17

At the C++Now conference 2 weeks ago, I attended a talk I thought I was going to hate: “Why iterators got it all wrong and what we should use instead” by Arno Schoedl. Turns out it was pretty brilliant in fact, and I think it helps explain how I posted several wrong answers in this thread: a fuzziness in the role of indices makes them error-prone. I don't love some details of the library design he proposes (and I think he's gone on to revise those details out since the conference), but his fundamental insight, that sometimes an index represents the position of an element and other times it represents the boundary between elements, is extremely powerful. If Swift ever gets around to revising its collection model, these insights should be taken into consideration.

/cc @lorentey @scanon

9 Likes
18

The recording of this talk is now available: https://www.youtube.com/watch?v=TZ_m6_IGwX0

(YouTube currently shows it as "unlisted"; I got the link from JetBrains's conference page, where some videos have been pre-published. I believe the YouTube link won't change once it goes fully public.)