[swift-evolution] [swift-evolution-announce] [Review] SE-0045: Add scan, prefix(while:), drop(while:), and iterate to the stdlib
kevin at sb.org
Fri Apr 29 16:51:34 CDT 2016
On Thu, Apr 28, 2016, at 11:48 AM, Joe Groff via swift-evolution wrote:
> 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.
That's an interesting idea. Taking the state as an inout parameter seems useful, but it does mean breaking with precedent from other languages and I do worry slightly about the ergonomics (not all operations have mutating counterparts, though you could also say that there's mutating methods that don't have trivial non-mutating versions too).
That said, regarding using `scan` to produce a sequence of tree data structures, I'd expect non-mutating operations to be able to share state just as effectively as COW mutating operations.
More information about the swift-evolution