One thing I've been thinking about with regards to the existing `reduce` operation is whether it would be better expressed in Swift as taking its closure as (inout State, Element) -> Void rather than (State, Element) -> State. Doing so would avoid many of the accidentally-quadratic issues with the current formulation of reduce:
arrayOfArrays.reduce(, combine: +) // quadratic temporary arrays
arrayOfArrays.inPlaceReduce(, combine: +=) // can be linear by appending arrays in-place
Thanks to the scoped semantics of `inout`, there's no hazard of the mutable state reference being escaped, so the inout form is isomorphic to the traditional pure form of reduce.
Now `scan`-ing to generate an array of intermediate arrays is inherently quadratic, since each intermediate array shows up as a distinct copy in the resulting collection. However, if someone used `scan` to produce a sequence of tree data structures instead of flat arrays, it could still be interesting to share structure among the intermediate states collected by `scan` by performing an in-place operation to generate new values instead of an out-of-place operation. It might be interesting to consider a similar signature change to `scan` for these same reasons.
-Joe
···
On Apr 28, 2016, at 11:11 AM, Chris Lattner <clattner@apple.com> wrote:
Hello Swift community,
The review of "SE-0045: Add scan, prefix(while:), drop(while:), and iterate to the stdlib" begins now and runs through May 3. The proposal is available here:
https://github.com/apple/swift-evolution/blob/master/proposals/0045-scan-takewhile-dropwhile.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at
https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager.
What goes into a review?
The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:
* What is your evaluation of the proposal?
* Is the problem being addressed significant enough to warrant a change to Swift?
* Does this proposal fit well with the feel and direction of Swift?
* If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
* How much effort did you put into your review? A glance, a quick reading, or an in-depth study?More information about the Swift evolution process is available at
https://github.com/apple/swift-evolution/blob/master/process.md