[swift-evolution] [swift-evolution-announce] [Review] SE-0045: Add scan, prefix(while:), drop(while:), and iterate to the stdlib

[Kevin Ballard]

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.

-Kevin