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

  * 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

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

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

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

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.

  * 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

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.

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

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

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

    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

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.

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

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>

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

I really don't want to see this discussion die as I have a vested interest in getting this functionality into
Swift 3. So let me suggest that

`sequence(_:, next:) -> AdHocSequence`

might be a Swift acceptable solution. We're not going to see fold/unfold pair happen. It's a given that
`reduce` is a fixed point in Swift space and `sequence` well describes what this should be doing.

So is it possible to push forward with `sequence`, whose only negative seems to be that it's not as well
loved as `unfold`?

-- Erica

···

On May 1, 2016, at 5:13 AM, Brent Royal-Gordon via swift-evolution <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. 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.)

+1!

···

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

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` which aligns pretty nicely with the
    `reduce` counterpart.

I like it.

--
Dave

I do like `sequence`, though I'm not sold on the name AdHocSequence
(just from that name it's hard to figure out what it does). An
alternative is `expand`, which is nice because it pairs with `reduce`,
but it's less obvious that it produces a sequence and the name isn't as
good with the stateful version.

As for return type name, we could go ahead and use UnfoldSequence<T>
anyway even though the function isn't named `unfold`, because this name
will make sense to people who do know what unfold is, and I'm not
convinced we can have a meaningful name for people who don't (since
SequenceSequence is too silly).

So given that, I'll suggest the following:

func sequence<T>(initial: T, next: T -> T?) -> UnfoldSequence<T>
func sequence<T, State>(state: State, next: (inout State) -> T?) ->
UnfoldSequence<T>

I'm suggesting `sequence(initial:next:)` instead of the previously-
suggested `sequence(from:applying:)` because the term "from" could
equally well mean the first element or the state, whereas "initial"
should make it more obvious that this value is the first element of the
resulting sequence. And I'm using "next" as suggested by Erica because
the function does return the next element, and it's similar to the
IteratorProtocol method. I've also chosen to change the stateful version
to use an inout parameter, as previously suggested, because it's
equivalent to the State -> (T, State)? in functionality but is less
likely to produce unwanted COW copies.

-Kevin Ballard

···

On Fri, May 13, 2016, at 11:08 AM, Erica Sadun wrote:

On May 1, 2016, at 5:13 AM, Brent Royal-Gordon via swift-evolution <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. 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.)

I really don't want to see this discussion die as I have a vested
interest in getting this functionality into
Swift 3. So let me suggest that

`sequence(_:, next:) -> AdHocSequence`

might be a Swift acceptable solution. We're not going to see
fold/unfold pair happen. It's a given that
`reduce` is a fixed point in Swift space and `sequence` well describes
what this should be doing.

So is it possible to push forward with `sequence`, whose only negative
seems to be that it's not as well
loved as `unfold`?

Would there be any issue with the return type being AnySequence? It’s used in other areas:

LazySequence & FlattenSequence’s
dropFirst(n: Int) -> AnySequence<Generator.Element>
dropLast(n: Int) -> AnySequence<Generator.Element>

No need to introduce another type, and it’s straight forward to implement with AnySequence.

···

On 14 May 2016, at 5:07 AM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

On Fri, May 13, 2016, at 11:08 AM, Erica Sadun wrote:

On May 1, 2016, at 5:13 AM, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org <mailto: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. 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.)

I really don't want to see this discussion die as I have a vested interest in getting this functionality into
Swift 3. So let me suggest that

`sequence(_:, next:) -> AdHocSequence`

might be a Swift acceptable solution. We're not going to see fold/unfold pair happen. It's a given that
`reduce` is a fixed point in Swift space and `sequence` well describes what this should be doing.

So is it possible to push forward with `sequence`, whose only negative seems to be that it's not as well
loved as `unfold`?

I do like `sequence`, though I'm not sold on the name AdHocSequence (just from that name it's hard to figure out what it does). An alternative is `expand`, which is nice because it pairs with `reduce`, but it's less obvious that it produces a sequence and the name isn't as good with the stateful version.

As for return type name, we could go ahead and use UnfoldSequence<T> anyway even though the function isn't named `unfold`, because this name will make sense to people who do know what unfold is, and I'm not convinced we can have a meaningful name for people who don't (since SequenceSequence is too silly).

So given that, I'll suggest the following:

  func sequence<T>(initial: T, next: T -> T?) -> UnfoldSequence<T>
  func sequence<T, State>(state: State, next: (inout State) -> T?) -> UnfoldSequence<T>

I'm suggesting `sequence(initial:next:)` instead of the previously-suggested `sequence(from:applying:)` because the term "from" could equally well mean the first element or the state, whereas "initial" should make it more obvious that this value is the first element of the resulting sequence. And I'm using "next" as suggested by Erica because the function does return the next element, and it's similar to the IteratorProtocol method. I've also chosen to change the stateful version to use an inout parameter, as previously suggested, because it's equivalent to the State -> (T, State)? in functionality but is less likely to produce unwanted COW copies.

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

AnySequence is specifically used to erase the type of an underlying
sequence, and I'm guessing that using it here will make it harder to
optimize loops that use this.

-Kevin Ballard

···

On Fri, May 13, 2016, at 10:20 PM, Patrick Smith wrote:

Would there be any issue with the return type being AnySequence? It’s
used in other areas:

LazySequence & FlattenSequence’s
dropFirst(n: Int) -> AnySequence<Generator.Element>
dropLast(n: Int) -> AnySequence<Generator.Element>

No need to introduce another type, and it’s straight forward to
implement with AnySequence.

On 14 May 2016, at 5:07 AM, Kevin Ballard via swift-evolution <swift- >> evolution@swift.org> wrote:

On Fri, May 13, 2016, at 11:08 AM, Erica Sadun wrote:

On May 1, 2016, at 5:13 AM, Brent Royal-Gordon via swift-evolution >>> <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. 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.)

I really don't want to see this discussion die as I have a vested
interest in getting this functionality into
Swift 3. So let me suggest that

`sequence(_:, next:) -> AdHocSequence`

might be a Swift acceptable solution. We're not going to see
fold/unfold pair happen. It's a given that
`reduce` is a fixed point in Swift space and `sequence` well
describes what this should be doing.

So is it possible to push forward with `sequence`, whose only
negative seems to be that it's not as well
loved as `unfold`?

I do like `sequence`, though I'm not sold on the name AdHocSequence
(just from that name it's hard to figure out what it does). An
alternative is `expand`, which is nice because it pairs with
`reduce`, but it's less obvious that it produces a sequence and the
name isn't as good with the stateful version.

As for return type name, we could go ahead and use UnfoldSequence<T>
anyway even though the function isn't named `unfold`, because this
name will make sense to people who do know what unfold is, and I'm
not convinced we can have a meaningful name for people who don't
(since SequenceSequence is too silly).

So given that, I'll suggest the following:

func sequence<T>(initial: T, next: T -> T?) -> UnfoldSequence<T>
func sequence<T, State>(state: State, next: (inout State) -> T?) ->
UnfoldSequence<T>

I'm suggesting `sequence(initial:next:)` instead of the previously-
suggested `sequence(from:applying:)` because the term "from" could
equally well mean the first element or the state, whereas "initial"
should make it more obvious that this value is the first element of
the resulting sequence. And I'm using "next" as suggested by Erica
because the function does return the next element, and it's similar
to the IteratorProtocol method. I've also chosen to change the
stateful version to use an inout parameter, as previously suggested,
because it's equivalent to the State -> (T, State)? in functionality
but is less likely to produce unwanted COW copies.

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