[swift-evolution] Sequence/Collection Enhancements

Fri Feb 17 11:50:11 CST 2017

I definitely find the intent here to be an interesting view at performant collection operations; in Foundation we have exposed IndexSet to do this type of thing.  When Foundation migrated to structural types it was really obvious to make IndexSet a structure - it was a logical change because it already was used as that concept in the Objective-C APIs. One of it’s biggest features is that it interoperates with NSArray/NSMutableArray which unfortunately it does not operate upon Array/Collection etc as of current. But there are APIs like UI/NS CollectionView that some of the primitive interoperation is based upon IndexSet which mirror NSArray/NSMutableArray making modeling really nice. As of current Swift is lacking some of those handy parallels. The IndexSet type has been used across many APIs in the SDK (as well as third party code). I wonder if it would be reasonable to sink an encapsulation type of the collection of ranges (as an efficient store) down and make it generic for the Index type. That way we would have a cohesive story when it comes to interoperation with on-going improvements that might happen in UIKit/AppKit/Foundation etc where the changes like this would interoperate well.

There are also a few other methods that I think might be worth investigating; 

non mutation
Fetching elements out of a collection given a sequence of ranges.
Fetching a sequence of ranges where a predicate matches elements (and perhaps even a sequence of ranges as a constraint upon that predicate)

mutation
Inserting a sequence of elements into the collection at indexes defined by a sequence of ranges
Replacing elements at indexes defined by a sequence of ranges with elements from a sequence

If we modified IndexSet to be generic (and perhaps moved it further down to interoperate with collection) I am certain that this would work really well with the already established APIs we have (just making bridged NSIndexSets really a IndexSet<Int> ). However this would mean that we would need some sort of way of indicating types were “Countable” which might be a decent addendum to the collection protocol cluster.

I think that overall these APIs have worked nicely with other counterparts (perhaps with a slight caveat of the matching of replacement counts and index counts). Additionally I am quite certain that having an encapsulating efficient storage for a sequence of ranges can allow for some really nice performance improvements and getting the performance point right is not always easy or obvious; so having the higher level APIs to handle these can not only be easier for the developer but also offer some really great performance optimizations too.

I have already tinkered with the idea of using IndexSet on Data and it is amazing; I can easily write really complex parsers for doing awful things like parsing mach-o headers from executables or other such things. I have also tinkered with the idea of making a slice type that is a sparse slice (it breaks some other assumptions of how collections work) and that works pretty nicely too (I think that should be a further discussion and this is probably not the time to introduce that idea just yet).

Hope that gives somethings to chew on from a frameworks perspective.

Cheers!
Philippe Hausler

> On Feb 16, 2017, at 4:39 PM, Ben Cohen via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 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
> 
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170217/b5094440/attachment-0001.html>