[swift-evolution] (Draft) Add last(where:) and lastIndex(where:) methods

[Hooman Mehr]

Thank you for your comments. 

I think additional index manipulation and collection scanning API is needed, and your proposal cover an important part of it.

I also have some clarifications and comments inline:

> On May 10, 2016, at 4:52 PM, Nate Cook <natecook at gmail.com> wrote:
> Thanks Hooman! Those do look like useful extensions. I think the proposal should stay focused on the APIs it includes already.
>> On May 10, 2016, at 4:18 PM, Hooman Mehr <hooman at mac.com <mailto:hooman at mac.com>> wrote:
>> public func offset(of index: Index) -> IndexDistance
>> public func index(atOffset offset: IndexDistance) -> Index
> 
> I like these, but I doubt they would get much traction, since they're essentially substituting startIndex into existing methods. I have thought it would be nice to have startIndex as the default parameter to those methods, though, so you could write either of these:
> 
> 	let i = c.index(c.startIndex, offsetBy: 5)		// current
> 	let i = c.index(offsetBy: 5)				// nice addition

That is right. The main function is `offset` that I use a lot and for the reverse, your suggestion seems better. I am using `offset` quite a bit but I don’t know if it is generally as useful for other people as it is for me.

> 
>> public func index(of element: Iterator.Element, from firstIndex: Index) -> Index?
>> public func index(from firstIndex: Index, where predicate: @noescape (Iterator.Element) throws -> Bool) rethrows -> Index?
> 
> I have the same reaction to these. Because indices are shared between collections and slices, instead of using a starting index, Swift's collection operations can just work on a slice. So instead of calling
> 
> 	let i = c.index(of: "A", from: firstIndex)
> 
> you can call
> 
> 	let i = c.suffix(from: firstIndex).index(of: "A”)

The point is: The `i` above is an index into the (discarded) slice returned by `suffix()`, not the collection `c`. In general, it does not work correctly on the original collection. The behavior of slice indexes have changed a couple of times and is not totally consistent or guaranteed for different concrete collections. That is the reason I am proposing the above function to provide a sure way to have this functionality working properly and I find it extremely useful. Again I don’t know about others.

It seems that the subject of the interaction between slice indexes and the parent collections need further clarifications and specification from the core Swift team.

> 
>> public func index<C: Collection where ...>(of elementSequence: C) -> Index?
>> public func index<C: Collection where ...>(of elementSequence: C, from firstIndex: Index) -> Index?
> 
> These methods we don't have at all currently, and could really use! I would definitely support a proposal for finding a subsequence of a collection. There are several algorithms beyond the naive approach, so it would be interesting to see if / how a proposal could use those in a generic context.
> 

I updated the gist <https://gist.github.com/hooman/e77cc0e955a1db672ae49e45b0038d04>. Besides some corrections and removing a couple of extension constraints, I merged the two functions above into:

public func index<C: Collection where ...>(of elementSequence: C, from firstIndex: Index? = nil) -> Index?

I think the basic implementation in the gist is good enough for many cases and we can specialize for array. As long as the collection and the sub-collection are not huge, performance should be fine.

On the other hand, I am too busy to seriously propose and pursue its addition. If enough people find it worthy of general inclusion into the standard library, somebody will pick it up, but not me.

I didn’t intend to hijack your proposal, but I thought some comments would help clarify things.

Thank you again,
Hooman


> Thanks again!
> Nate
> 
>> Look at the comments for the example usage. For `offset` function, see the source code for usage.
>> 
>> Hooman
>> 
>>> On May 10, 2016, at 11:54 AM, Nate Cook via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>> 
>>> I've needed these in the past and used them in other languages—any feedback on this  idea?
>>> 
>>> Add last(where:) and lastIndex(where:) Methods to Bidirectional Collections
>>> The standard library should include methods for finding the last element of a bidirectional collection that matches a predicate, along with the index of that element.
>>> 
>>> Motivation
>>> The standard library currently has (or will soon have) methods that perform a linear search from the beginning of a collection to find an element that matches a predicate:
>>> 
>>> let a = [20, 30, 10, 40, 20, 30, 10, 40, 20]
>>> a.first(where: { $0 > 25 })         // 30
>>> a.index(of: 10)                     // 2
>>> a.index(where: { $0 > 25 })         // 1
>>> Unfortunately, there is no such method that searches from the end of a bidirectional collection. Finding the last of particular kind of element has multiple applications, particularly with text, such as wrapping a long string into lines of a maximum length or trimming whitespace from the beginning and end of a string.
>>> 
>>> This limitation can be worked around by using the methods above on the reversed collection, but the resulting code is truly dreadful. For example, to find the corresponding last index to a.index(where: { $0 > 25 }), this unholy incantation is required:
>>> 
>>> (a.reversed().index(where: { $0 > 25 })?.base).flatMap({ a.index(before: $0) })
>>> Wat.
>>> 
>>> Proposed solution
>>> Bidirectional collections should include three new methods for symmetry with the existing forward-searching APIs: last(where:), lastIndex(where:), and lastIndex(of:), specifically for collections of Equatable elements.
>>> 
>>> These additions would remove the need for searching in a reversed collection and allow code like the following:
>>> 
>>> a.last(where: { $0 > 25 })          // 40
>>> a.lastIndex(of: 10)                 // 6
>>> a.lastIndex(where: { $0 > 25 })     // 7
>>> Much better!
>>> 
>>> _______________________________________________
>>> swift-evolution mailing list
>>> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
>>> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
>> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160511/3a455270/attachment.html>