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

[Dave Abrahams]

on Fri Apr 29 2016, Kevin Ballard <swift-evolution at swift.org> wrote:

> 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, 

That's easy; you just mutate the whole state using assignment in the
closure:

  state = nonmutating(state)

> though you could also say that there's mutating methods that don't
> have trivial non-mutating versions too).

That one is harder unless you know you have value semantics; you need a
way to copy the state to create a non-mutating operation from a mutating one.

> 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.

Good point.

-- 
Dave