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


(Chris Lattner) #1

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

Thank you,

-Chris Lattner
Review Manager


(Joe Groff) #2

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


Troubling `Sequence`
(Mark Lacey) #3

I haven’t read through the complete proposal in detail, but regarding the ‘scan’ operation I would like to point out that the definition given in the example matches the semantics of what is usually called ‘prescan' or 'exclusive scan', whereas ‘scan’ (aka ‘inclusive scan’ or ‘prefix sum’) would not include the identity element, and each position of the result would include applying the operator to the elements up to and including the element in the same position of the source array, e.g.:

  (1..<6).scan(combine: +) // [1, 3, 6, 10, 15, 21]

Sources:
  https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf
  https://en.wikipedia.org/wiki/Prefix_sum

Mark

···

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

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution-announce mailing list
swift-evolution-announce@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution-announce


(Chris Lattner) #4

I’m passing on some feedback from a contributor who preferred to remain anonymous / offlist and emailed the review manager. These are not my personal comments:

···

On Apr 28, 2016, at 11:11 AM, Chris Lattner <clattner@apple.com> wrote:

Proposal:
  https://github.com/apple/swift-evolution/blob/master/proposals/0045-scan-takewhile-dropwhile.md

I would really like a different name for scan. While it’s the term of art for Haskell and co, it really seems meaningless to regular programmers (why is “scanning” the way you produce an array of intermediate reduces?), and it would be better to follow the pattern already established elsewhere in the library to give friendlier names e.g. flatMap instead of bind, reduce instead of fold.

I think Python calls it accumulate: http://docs.python.org/3/library/itertools.html#itertools.accumulate

While this isn’t great either, because you can think of reduce as “accumulating” a value, I still think it’ll be easy for people to understand the difference and remember which is which (since reducing sounds like boiling down, accumulating more like gathering multiple things and sounds similar to “cumulative”).

I also think it would be nice for both scan and reduce to have overloads that take the first value as the initial (and return an optional) but that’s probably a separate proposal.

Other than that, I think these will all make very useful additions to the library.


(Dave Abrahams) #5

FWIW, I'm posting this review on behalf of Dmitri Gribenko, and Maxim
Moiseev, and me:

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

  * What is your evaluation of the proposal?

We like the bones, but we have some issues with the proposal as
submitted:

1. The proposal should be revised to account for language and standard
   library changes, most notably, the first argument label rules and API
   names have been overhauled since the proposal was written. There are
   still many occurrences of obsolete names such as `SequenceType`.

   One good way to get there is to make the APIs compile (with
   `fatalError()` in method bodies if necessary) against the master
   branch in GitHub. I realize it's been a long time since it was
   originally submitted, but it's really hard to evaluate a proposal if
   we'd have to change the APIs before they could even be incorporated
   into the codebase.

   The fact that names are out of date also casts doubt upon whether a
   first argument label is being proposed or not. IMO it's really
   crucial that the proposal be revised this way *before* it is accepted.

2. In the “Detailed design” section it would have helped to have an
   explanation of the remark about “matching expected behavior.” We were
   scratching our heads over this one until we figured out it’s about
   the policy of not making multiple passes using a user-defined closure
   without an explicit appearance of `.lazy`.

3. We would prefer that `scan`’s first argument label was changed from
   `initial` to `startingWith`, and we would like to update `reduce` to
   use the same argument label. Whatever we do, `reduce` and `scan`
   should be consistent in this respect.

4. We find the name `iterate` problematic, in part because it is an
   active verb on a non-mutating method, but also because to us, it
   strongly implies eager evaluation. In lieu of `iterate`, we'd prefer
   to see two overloads of `unfold` as shown below. Although `unfold`
   is also an active verb, it is very much the correct term of art for
   the more general method and it allows us to establish the semantic
   relationship between the single- and two-argument forms.

    func unfold<T, State>(
      _ initialState: State,
      applying nextElementAndState: (State)->(T, State)?
    ) -> UnfoldSequence<T>

    func unfold<T>(
      _ initialElement: T, applying nextElement: (T)->T?
    ) -> UnfoldSequence<T>

The second overload returns, approximately,

  unfold(initialElement) { state in nextElement(state).map { (state, $0) } }

though that implementation would be a bit more eager than necessary; a
fully-lazy implementation is at
https://github.com/apple/swift-evolution/pull/195#issuecomment-214927063

  * Is the problem being addressed significant enough to warrant a
    change to Swift?

Yes, it is crucial that Swift have a complete vocabulary of high-level
algorithms. While these are simple, they are also fundamental missing
pieces.

  * Does this proposal fit well with the feel and direction of
  Swift?

Yes.
        

      * If you have you used other languages or libraries with
  a similar feature, how do you feel that this proposal compares
  to those?

We don't have anything to say as a group about this, but Max or Dmitri
may have individual feedback.

      * How much effort did you put into your review? A
  glance, a quick reading, or an in-depth study?

An in-depth, collaborative, study.

···

on Thu Apr 28 2016, Chris Lattner <swift-evolution@swift.org> wrote:

More information about the Swift evolution process is available at

  https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Chris Lattner
Review Manager

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave, Dmitri, and Maxim


(Brent Royal-Gordon) #6

  * What is your evaluation of the proposal?

Great and necessary. I particularly like that the combination of `iterate(1, apply: { $0 * 2 }).prefix(while: { $0 < 100_000 })` mimics the abilities of the old C-style for loop.

Bikeshedding time!

* * *

I really like the `reduce`/`reductions` pairing instead of `reduce`/`scan`; it does a really good job of explaining the relationship between the two functions. I also think the `startingWith` label may be a good idea, although if we do that, we might want to change the second label to `combiningWith`.

* * *

I believe that `prefix(while:)` and `dropFirst(while:)` would be most consistent with the current standard library, but frankly, I consider that an indictment of the current names.

`skip` is better than `drop`, but they are both pigs; one's just wearing lipstick. The whole area of APIs which grab subsets of Sequences or Collections could use some renaming. It is rife with both inconsistencies (`prefix(_:)` and `dropFirst(_:)` are inverses, but look unrelated) and names which appear to mutate but don't (all the `drop` APIs). These APIs are currently grandfathered in with the term-of-art rule, which I normally agree with, but I think the results here are so bad that we can't let them stand.

I would suggest that we systematically rename these APIs to achieve a consistent, non-verb-based pattern which the new APIs can slot into nicely:

  first // Currently first
  prefix(_: Int) // Currently prefix(_:slight_smile:
  prefix(while: Element -> Bool) // Proposed as prefix(while:)
  
  afterFirst() or afterFirst // Currently dropFirst()
  afterPrefix(_: Int) // Currently dropFirst(_:slight_smile:
  afterPrefix(while: Element -> Bool) // Proposed as drop(while:)

  last // Currently last
  suffix(_: Int) // Currently suffix(_:slight_smile:
  suffix(while: Element -> Bool) // Unproposed
  
  beforeLast() or beforeLast // Currently dropLast()
  beforeSuffix(_: Int) // Currently dropLast(_:slight_smile:
  beforeSuffix(while: Element -> Bool) // Unproposed

  before(to: Index) // Currently prefix(upTo:)
  before(through: Index) // Currently prefix(through:)
  
  after(to: Index) // Unproposed?
  after(through: Index) // suffix(from:)?

Several of these APIs are listed as "unproposed"; they are neither in the current standard library, nor in this proposal. I am not suggesting we add them, but simply showing how they would be named if they *were* provided.

If the core team wants to protect `dropFirst` and `dropLast` as terms of art, I think our best alternative is to make `first` and `last` nullary methods, and rename the `prefix` methods to `first` and `suffix` to `last`. It seems like the decision to make `first` and `last` properties was a little bit uncertain to begin with; I think the naming issues here tip the scales.

In any case, though, the core team might prefer to consider this relatively large renaming as a separate proposal. If so, as I said, I think `prefix(while:)` and `dropFirst(while:)` are the best matches for the current APIs.

* * *

I think `iterate` is the best basic approach to the name. My own prototypes used `induce` since the sequence was produced by induction from a starting value and transformation function, but this approach was too clever by half: people were confused by the name until it was explained, and then they thought it was clever but had trouble remembering it.

There is precedent in the current standard library for using an imperative verb to lazily construct a list: the `repeatElement(_:count:)` function. However, if we don't like that for this case, an alternative is to use the noun `iteration`. And if we're going with the noun, well, that suggests that what we really want to define is not a function, but a type:

  struct Iteration<T>: Sequence {
    init(start startingValue: T, apply transformation: T -> T)
  }

This reads fairly well in common uses:

  for i in Iteration(start: 1, apply: { $0 * 2 }) { … }

  * Is the problem being addressed significant enough to warrant a change to Swift?

Yes. As I mentioned before, the combination of `iterate` and `prefix(while:)` is particularly important.

  * Does this proposal fit well with the feel and direction of Swift?

Yes; these fill important holes in our ability to create and manipulate sequences.

  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

Most languages I've used which have these features give them terrible names; these names help make them less accessible. I'm hoping that Swift will do better.

  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Read the review a few times, independently re-invented about half of it in various discussions and explorations of the C-style for loop removal.

···

--
Brent Royal-Gordon
Architechies


(Lily Ballard) #7

The proposal has been updated as per feedback from the core team (https://github.com/apple/swift-evolution/pull/275). This includes removing some last vestiges of Swift 2 naming as well as replacing `iterate(_:apply:)` with an overloaded function `unfold(_:applying:)`.

-Kevin Ballard

···

On Thu, Apr 28, 2016, at 11:11 AM, Chris Lattner via swift-evolution 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


(David Rönnqvist) #8

  * What is your evaluation of the proposal?

+1 This is a useful addition.

As other have already pointed out, I also feel that `scan` is the least intuitive name among these and that the `reduce`/`reductions` pairing would do a good job at explaining the relation between the two.

If I’ve understood the evolution process correctly, the broader naming of existing prefix, suffix, split, dropFirst, dropLast, etc. functions is not in scope of this proposal. Given that, I feel that the main goal regarding naming the proposed functions is to fit in well with the existing name. I feel that there is a small “term of art” argument to be made for takeWhile/dropWhile, but also that prefix(while:)/drop(while:) is a closer match to Swifts naming of similar existing functions. I don’t have strong preferences for either of these naming and would be absolutely fine with either.

  * Is the problem being addressed significant enough to warrant a change to Swift?

Yes, these are good building blocks for other functionality and are useful additions to the standard library

  * Does this proposal fit well with the feel and direction of Swift?

Yes, in both naming and functionality it fits well with existing functions for operating on sequences and collections

  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

I wonder if something like Haskell’s [`span`][1] (returning a tuple of `prefix(while:)` and `drop(while:)` would be a good addition alongside these. It also doesn’t have a very intuitive name, so in that case we would have to come up with something better.

[1]: http://hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:span

  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Read of the proposal, read the evolution proposal thread, and a small study of similar features in other languages.


(Pyry Jahkola) #9

I would really like a different name for scan. While it’s the term of art for Haskell and co, it really seems meaningless to regular programmers (why is “scanning” the way you produce an array of intermediate reduces?), and it would be better to follow the pattern already established elsewhere in the library to give friendlier names e.g. flatMap instead of bind, reduce instead of fold.

I think Python calls it accumulate: http://docs.python.org/3/library/itertools.html#itertools.accumulate

FWIW, Clojure calls it `reductions <http://clojure.github.io/clojure/clojure.core-api.html#clojure.core/reductions>` which aligns pretty nicely with the `reduce` counterpart.

I also think it would be nice for both scan and reduce to have overloads that take the first value as the initial (and return an optional) but that’s probably a separate proposal.

+1

— Pyry


(Erica Sadun) #10

This is a great place to bring up "terms of art", again. When looking to other languages as our muse, trying to adapt syntax into Swift's tortured guidance system is less successful than retaining those terms, which have already been extensively bikeshedded in their original development. I much prefer takeWhile dropWhile, etc.

-- E

···

On Apr 28, 2016, at 10:15 PM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:
I believe that `prefix(while:)` and `dropFirst(while:)` would be most consistent with the current standard library, but frankly, I consider that an indictment of the current names.
`skip` is better than `drop`, but they are both pigs; one's just wearing lipstick.


Troubling `Sequence`
(Matthew Johnson) #11

  * What is your evaluation of the proposal?

+1 in general, with some reservations about naming.

+1 This is a useful addition.

As other have already pointed out, I also feel that `scan` is the least intuitive name among these and that the `reduce`/`reductions` pairing would do a good job at explaining the relation between the two.

I agree that scan is not a great name and reductions is much more clear.

If I’ve understood the evolution process correctly, the broader naming of existing prefix, suffix, split, dropFirst, dropLast, etc. functions is not in scope of this proposal. Given that, I feel that the main goal regarding naming the proposed functions is to fit in well with the existing name. I feel that there is a small “term of art” argument to be made for takeWhile/dropWhile, but also that prefix(while:)/drop(while:) is a closer match to Swifts naming of similar existing functions. I don’t have strong preferences for either of these naming and would be absolutely fine with either.

I think the “term of art” argument for “take” rather than “prefix” is significant. I would much prefer that name be used. It is immediately clear, while “prefix" isn’t nearly as clear IMO.

It would be fine with me if we accept this proposal as-is and have a future proposal to address the broader naming issue.

···

On Apr 29, 2016, at 9:44 AM, David Rönnqvist via swift-evolution <swift-evolution@swift.org> wrote:

  * Is the problem being addressed significant enough to warrant a change to Swift?

Yes, these are good building blocks for other functionality and are useful additions to the standard library

  * Does this proposal fit well with the feel and direction of Swift?

Yes, in both naming and functionality it fits well with existing functions for operating on sequences and collections

  * If you have you used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

I wonder if something like Haskell’s [`span`][1] (returning a tuple of `prefix(while:)` and `drop(while:)` would be a good addition alongside these. It also doesn’t have a very intuitive name, so in that case we would have to come up with something better.

[1]: http://hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:span

  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Read of the proposal, read the evolution proposal thread, and a small study of similar features in other languages.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Lily Ballard) #12

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

···

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.


(Lily Ballard) #13

Interesting, I was not aware of the distinction here. The `scan` method
as proposed here matches the behavior of Haskell's `scanl` method
(http://hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:scanl)
.

I'm in favor of keeping the behavior as-is, because the "inclusive scan"
behavior can be recovered trivially by calling `.dropFirst()` on the
resulting sequence, whereas recovering prescan from inclusive scan is
not so trivial.

-Kevin Ballard

···

On Thu, Apr 28, 2016, at 12:30 PM, Mark Lacey via swift-evolution wrote:

I haven’t read through the complete proposal in detail, but regarding
the ‘scan’ operation I would like to point out that the definition
given in the example matches the semantics of what is usually called
‘prescan' or 'exclusive scan', whereas ‘scan’ (aka ‘inclusive scan’ or
‘prefix sum’) would not include the identity element, and each
position of the result would include applying the operator to the
elements up to and including the element in the same position of the
source array, e.g.:

(1..<6).scan(combine: +) // [1, 3, 6, 10, 15, 21]

Sources:
https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf
https://en.wikipedia.org/wiki/Prefix_sum


(Dave Abrahams) #14

Thanks, Kevin!

···

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

On Thu, Apr 28, 2016, at 11:11 AM, Chris Lattner via swift-evolution 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

The proposal has been updated as per feedback from the core team
(https://github.com/apple/swift-evolution/pull/275). This includes
removing some last vestiges of Swift 2 naming as well as replacing
`iterate(_:apply:)` with an overloaded function `unfold(_:applying:)`.

--
Dave


(Brent Royal-Gordon) #15

The proposal has been updated as per feedback from the core team (https://github.com/apple/swift-evolution/pull/275). This includes removing some last vestiges of Swift 2 naming as well as replacing `iterate(_:apply:)` with an overloaded function `unfold(_:applying:)`.

The proposal says this:

  public func unfold<T, State>(_ initialState: State, applying: State -> (T, State)?) -> UnfoldSequence<T>
  public func unfold<T>(_ initialElement: T, apply: T -> T) -> UnfoldSequence<T>

However, the comment implies that the second one should instead be this:

  public func unfold<T>(_ initialElement: T, applying: T -> T?) -> UnfoldSequence<T>

I'm not sure I like having these be overloaded on only the return type of the closure. Maybe we could do something like this?

  public func unfold<T, State>(fromState initialState: State, applying: State -> (T, State)?) -> UnfoldSequence<T>
  public func unfold<T>(fromFirst initialElement: T, apply: T -> T) -> UnfoldSequence<T>

That way you're calling either `unfold(fromState:applying:)` or `unfold(fromFirst:applying:)`. (Some further bikeshedding might be needed here—it's late and I'm tired.)

···

--
Brent Royal-Gordon
Architechies


(Dave Abrahams) #16

    I would really like a different name for scan. While it’s the term of art
    for Haskell and co, it really seems meaningless to regular programmers (why
    is “scanning” the way you produce an array of intermediate reduces?), and it
    would be better to follow the pattern already established elsewhere in the
    library to give friendlier names e.g. flatMap instead of bind, reduce
    instead of fold.

    I think Python calls it accumulate:
    http://docs.python.org/3/library/itertools.html#itertools.accumulate

FWIW, Clojure calls it `reductions` which aligns pretty nicely with the `reduce
` counterpart.

That's cute.

···

on Thu Apr 28 2016, Pyry Jahkola <swift-evolution@swift.org> wrote:

    I also think it would be nice for both scan and reduce to have overloads
    that take the first value as the initial (and return an optional) but that’s
    probably a separate proposal.

+1

— Pyry

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave


(Lily Ballard) #17

I like it.

-Kevin Ballard

Links:

  1. http://clojure.github.io/clojure/clojure.core-api.html#clojure.core/reductions

···

On Thu, Apr 28, 2016, at 02:13 PM, Pyry Jahkola via swift-evolution wrote:

I would really like a different name for scan. While it’s the term of
art for Haskell and co, it really seems meaningless to regular
programmers (why is “scanning” the way you produce an array of
intermediate reduces?), and it would be better to follow the pattern
already established elsewhere in the library to give friendlier names
e.g. flatMap instead of bind, reduce instead of fold.

I think Python calls it accumulate:
http://docs.python.org/3/library/itertools.html#itertools.accumulate

FWIW, Clojure calls it `reductions[1]` which aligns pretty nicely with
the `reduce` counterpart.


(Dave Abrahams) #18

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.

···

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

On Thu, Apr 28, 2016, at 11:48 AM, Joe Groff via swift-evolution wrote:

--
Dave


(Lily Ballard) #19

Oops, you're right, that was a mistake.

-Kevin

···

On Sun, May 1, 2016, at 04:13 AM, Brent Royal-Gordon wrote:

> The proposal has been updated as per feedback from the core team (https://github.com/apple/swift-evolution/pull/275). This includes removing some last vestiges of Swift 2 naming as well as replacing `iterate(_:apply:)` with an overloaded function `unfold(_:applying:)`.

The proposal says this:

  public func unfold<T, State>(_ initialState: State, applying: State -> (T, State)?) -> UnfoldSequence<T>
  public func unfold<T>(_ initialElement: T, apply: T -> T) -> UnfoldSequence<T>

However, the comment implies that the second one should instead be this:

  public func unfold<T>(_ initialElement: T, applying: T -> T?) -> UnfoldSequence<T>


(Dave Abrahams) #20

Why not? It's a type, like anything else we might overload on.

···

on Sun May 01 2016, Brent Royal-Gordon <swift-evolution@swift.org> wrote:

The proposal has been updated as per feedback from the core team

(https://github.com/apple/swift-evolution/pull/275). This includes
removing some last vestiges of Swift 2 naming as well as replacing
`iterate(_:apply:)` with an overloaded function `unfold(_:applying:)`.

The proposal says this:

  public func unfold<T, State>(_ initialState: State, applying: State -> (T, State)?) -> UnfoldSequence<T>
  public func unfold<T>(_ initialElement: T, apply: T -> T) -> UnfoldSequence<T>

However, the comment implies that the second one should instead be this:

  public func unfold<T>(_ initialElement: T, applying: T -> T?) -> UnfoldSequence<T>

I'm not sure I like having these be overloaded on only the return type
of the closure.

--
Dave