[swift-evolution] Sequence/Collection Enhancements

[Ben Cohen]

Hi swift-evolution,

Following up on Ted’s post regarding the opening up of stage 2, I’m starting a thread to discuss additive algorithms for Sequence and Collection.

Here is a list of commonly requested algorithms to operate on Sequence or Collection:

In-place transformations:
transform elements in a MutableCollection using a closure i.e. in-place map
remove(where:) that takes a predicate i.e. in-place filter
remove(indices:) that takes a Sequence of Index
bulk operations (replace, remove, insert) on RangeReplaceableCollection for a Sequence of subranges
Sorting:
change sort/sorted/partition to be stable
possibly add an explicitly unstable sort
provide partial sorting i.e. the _n_th lowest element of a sequence
Select a random element of a RandomAccessCollection (note this could include a random element of 0..<n)
Check if all elements in a Sequence match a predicate (i.e. !contains(!predicate))
reduce with an inout argument for the running value (PR for proposal here: https://github.com/apple/swift-evolution/pull/587 <https://github.com/apple/swift-evolution/pull/587>)
cycle – repeat a collection over and over.
scan/accumulate/reductions/some other spelling of a reduce that returns the running values (previously proposed: https://github.com/apple/swift-evolution/blob/master/proposals/0045-scan-takewhile-dropwhile.md <https://github.com/apple/swift-evolution/blob/master/proposals/0045-scan-takewhile-dropwhile.md>)
rotation of elements in a collection (deferred proposal: https://github.com/apple/swift-evolution/blob/master/proposals/0078-rotate-algorithm.md <https://github.com/apple/swift-evolution/blob/master/proposals/0078-rotate-algorithm.md>)
Please reply here with any comments or questions on the above list, or any additions you believe are important that are missing from it.
As this focus area is larger in scope than Dictionary, it is likely that it will need to be broken up into multiple separate proposals. The plan is to get an initial high-level signal from this thread on which areas to put focus on. We are also looking for volunteers to put together proposals and implementations – if you're interested in helping with that, please email me off-list. High quality community implementations will significantly improve the chances of a feature making it into Swift 4. Smaller, more focussed proposals are also more likely to make it than larger ones.

All methods added to the standard library increase complexity, so need a strong justification to reduce the risk of API sprawl. When requesting additions/modifications, please keep the following questions in mind:

Is the suggested addition a common operation that many would find useful? Can it be flexible enough to cover different needs?
Will it encourage good practice? Might it be misused or encourage anti-patterns?
Can the operation be composed simply from existing std lib features? Is that composition intuitive/readable? 
Is writing the equivalent by hand hard to get right? Are there common correctness traps that this addition would help avoid?
Is writing the equivalent by hand hard to make efficient? Are there common performance traps that this addition would help avoid?
Might a native implementation be able to execute more efficiently, by accessing internals, than the equivalent implementation using public APIs?
Thanks!

Ben


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170216/595b1cfc/attachment.html>