[swift-evolution] Sequence/Collection Enhancements

[plx]

Some belated feedback.

> On Feb 16, 2017, at 6:39 PM, Ben Cohen via swift-evolution <swift-evolution at swift.org> wrote:
> 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
+0.5 in the stdlib if only to side-step numerous re-implementations and perhaps also for minor performance gains.

+0.5 if it’s paired with an in-place variant (`mutating func mapInPlace(_ transform: (inout Element) -> Void) -> Void`); could perhaps be better-named `updateEach`.

Both are minor but would be nice-to-have as built-ins.

> remove(where:) that takes a predicate i.e. in-place filter
+2 as long as this is an overridable method. It’s a common need and difficult for users to write an efficient implementation.

One quibble: would this be on  `Collection`, `MutableCollection`, or some new `ShrinkableCollection`? This issue I’d have with putting this onto `Collection` itself is that that would seemingly shut the door on `Collection` being adoptable by any type that implements a “collection” with some fixed, intrinsic size.

Thus either adding it to `MutableCollection` (at cost of being overly narrow) or adding it to some new refinement like `ShrinkableCollection` (thus allowing e.g. `Set` and `Dictionary` to conform w/out eliminating fixed-size “collections” from adopting `Collection`).


> remove(indices:) that takes a Sequence of Index
+0 if *exactly* as stated; the point of a method like this would presumably be efficient bulk-removal, and a mere “a `Sequence` of `Index`” doesn’t provide much useful information: no count, no guarantee each index is included at-most once, no guarantee of ordering, and so on.

I think the “right” eventual solution is an equivalent to `(NS)IndexSet`—loosely speaking, a “collection” of non-empty, non-overlapping, ordered-ascending ranges of indices—but unfortunately it seems both difficult and premature to contemplate such a thing at this time.

> bulk operations (replace, remove, insert) on RangeReplaceableCollection for a Sequence of subranges
See above: a `Sequence` of subranges is a bit better than a `Sequence` of `Index`, but doesn’t provide much information (# of ranges? # of indices? ranges ordered somehow? ranges non-overlapping? ranges non-empty?).

Thus for both of the previous two I strongly think building them around an `(NS)IndexSet`-like component is the way to do them but to do that `(NS)IndexSet`-alike type properly would IMHO be a bigger project than the current scope; in the absence of such an index-set type I’m not sure there’s enough benefit to these bulk operations to justify their inclusion.

> Select a random element of a RandomAccessCollection (note this could include a random element of 0..<n)
+1 to add to the stdlib some reasonable way to draw a value at random from `0..<n` along with the obvious convenience method on `RandomAccessCollection`. Especially with cross-platform ambitions having the stdlib provide a non-terrible way to do this seems prudent.

That said, I’d be wary of doing anything more than that basic pair—random value from `0..<n` + convenience on `RandomAccessCollection`—at least at this point in time…I say this because I’d like to believe the stdlib will eventually gain a more-structured approach to randomness (perhaps something analogous to what C++11 picked up), and thus this feature should be kept very minimal.

> Check if all elements in a Sequence match a predicate (i.e. !contains(!predicate))
+1, this in the stdlib is better than a million independent re-implementations.

As a philosophical point, I’d actually prefer if `all`, `any`, `notAll`, and `notAny` (change names to suit) were all in the stdlib even if just as convenience methods defined in an extension: no point having everyone roll their own and there’s likely a minor performance advantage if such code goes in the stdlib.

When only one “polarity” of a logical operation is available (`all` but not `none`, or `remove(where:)` but not `keep(where:)`, etc.) it seems inevitable to have occasional mismatches, and wrapping a closure in another closure just to apply `!` to it always at least “feels” wasteful. 

> 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>)
+0.5? The performance consideration is real, but I’d hope the eventual ownership system would be able to mitigate the performance issues.

> 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>)
+0.5, it’s another nice thing to have in the standard library but not especially urgent. 

> 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. 
> 
One last question: what’s the right cost model for adding an associated type to a standard library protocol?

EG: for the collection-rotation above, the `RotatedCollection` type as presently proposed would result in `RotatedCollection<Base>` returning `RotatedCollection<RotatedCollection<Base>>` from `func rotated(shiftingToStart:)`; this *could* be avoided by having `Collection`:

- gain `associatedtype Rotation: Collection where…`
- make `func rotated(shiftingToStart index: Index) -> Rotation`
- default `Rotation = RotatedCollection<Self>`

…and then having `RotatedCollection<Base>` make use `Rotation = RotatedCollection<Base>`.

There’s a benefit but also a cost, and it’s never been clear *how costly* one should consider a new associated type on a stdlib protocol.

> 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/20170225/a07a60e0/attachment.html>