[Review] SE-0094: Add sequence(initial:next:) and sequence(state:next:) to the stdlib


(Chris Lattner) #1

Hello Swift community,

The review of "SE-0094: Add sequence(initial:next:) and sequence(state:next:) to the stdlib" begins now and runs through May 23. This is a refinement of part of SE-0045. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0094-sequence-function.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 contribute to 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 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


(Brent Royal-Gordon) #2

  * What is your evaluation of the proposal?

This is an important and positive addition to the standard library. It allows us to quickly build ad-hoc sequences and, combined with `prefix(while:)`, easily simulates most of what the C-style `for` loop could do. I can easily imagine using this to convert complex `while let` loops like parent chain walking into `for` loops, create infinite sequences, prototype interesting generators, and do lots of other things that currently require much more work.

I especially like the way `sequence(state:next:)` is designed, with an `inout` state. The traditional functional design is quite awkward; this way is much better.

I could bikeshed the names a little—I'd prefer `sequence(first:next:)` and `sequence(state:each:)` to represent the slightly different roles the parameters have in the two calls—but ultimately this is a really solid design and I'm looking forward to seeing it in Swift.

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

Yes. Enough pixels have been spilled over the C-style for loop alone. Let's put it to bed.

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

Yes. This is a super-flexible and elegant design, inspired by functional programming languages but much more usable in many ways.

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

I've written a few loops that I would rewrite using `sequence(initial:next:)` now that it's available, but I've never actually used `unfold` or any equivalent to this function even in languages which supported them. They just seemed too abstract and disconnected from the problem I was trying to solve. `sequence(initial:next:)` avoids that problem by squarely addressing the common use case.

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

I've participated in discussions surrounding this feature from the beginning, including some private prototyping. (My prototype was `induce(from:while:by:)`; its naming turned out to be too clever by half, even in my own estimation, and the `while:` part turned out to be separable as `prefix(while:)`.)

···

--
Brent Royal-Gordon
Architechies


(Trent Nadeau) #3

* What is your evaluation of the proposal?
+1. I've used unfold/iterate functions in Haskell and Clojure, and they are
very useful.
        * Is the problem being addressed significant enough to warrant a
change to Swift?
Yes.
        * Does this proposal fit well with the feel and direction of Swift?
Yes.
        * If you have used other languages or libraries with a similar
feature, how do you feel that this proposal compares to those?
See above.
        * How much effort did you put into your review? A glance, a quick
reading, or an in-depth study?
Quick reading.

Also note that there's a typo in the second example:

for view in sequence(initial: someView, next: { $0.superview }) {
    // someView, someView.superview, someView.superview.superview, ...
}

should be:

for view in sequence(state: someView, next: { $0.superview }) {
    // someView, someView.superview, someView.superview.superview, ...
}

···

On Thu, May 19, 2016 at 6:29 PM, Chris Lattner via swift-evolution < swift-evolution@swift.org> wrote:

Hello Swift community,

The review of "SE-0094: Add sequence(initial:next:) and
sequence(state:next:) to the stdlib" begins now and runs through May 23.
This is a refinement of part of SE-0045. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0094-sequence-function.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 contribute to 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 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 mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Trent Nadeau


(David Rönnqvist) #4

* What is your evaluation of the proposal?
+1. These are useful additions to the standard library.

Naming the first argument `initial` (in the `T->T?` variant) is consistent with `reduce` and makes it clear (to me) that the initial value is part of the result.

  * 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. Using inout for the state argument nicely leverages the fact that Swift can be functional without some of the restrictions of a _purely_ functional language.

  * If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
I’ve used iterate and unfold in Haskell. These additions are true to the usefulness of those two functions, in a Swift style (see above).

  * How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
Participated in the discussion and review of SE-0045 and the discussion that followed it being accepted with modifications.

- David

···

On 20 May 2016, at 00:29, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift community,

The review of "SE-0094: Add sequence(initial:next:) and sequence(state:next:) to the stdlib" begins now and runs through May 23. This is a refinement of part of SE-0045. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0094-sequence-function.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 contribute to 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 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 mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Jeremy Pereira) #5

  * What is your evaluation of the proposal?

+1

I think I would find myself using this in loads of places, if it was implemented.

One question: what is the downside of making these functions `rethrows` and allowing the closure to throw?

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

Yes. I probably implement something similar to this in every project.

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

Yes

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

I’ve dabbled in Haskell but I wouldn’t claim to have used its equivalent of this feature.

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

I read the proposal and the previous responses.

···

On 19 May 2016, at 23:29, Chris Lattner via swift-evolution <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


(Lily Ballard) #6

The code as written is correct. The rewritten version would actually
just emit [someView.superview, someView.superview, someView.superview,
...] forever. I imagine the confusion stems from the fact that there's 2
examples but they both demonstrate just the first function, and there's
no examples of the second function, which is something I'll try to
address soon.

-Kevin Ballard

···

On Thu, May 19, 2016, at 04:20 PM, Trent Nadeau via swift-evolution wrote:

Also note that there's a typo in the second example:

for view in sequence(initial: someView, next: { $.superview }) { //
someView, someView.superview, someView.superview.superview, ... }

should be:

for view in sequence(state: someView, next: { $.superview }) { //
someView, someView.superview, someView.superview.superview, ... }


(Brent Royal-Gordon) #7

Also note that there's a typo in the second example:

for view in sequence(initial: someView, next: { $0.
superview }) {
    
// someView, someView.superview, someView.superview.superview, ...

}

should be:

for view in sequence(state: someView, next: { $0.
superview }) {
    
// someView, someView.superview, someView.superview.superview, ...

}

I don't think these are mistakes—in each iteration of the loop, $0 is supposed to be the view from the previous iteration.

If you wanted an example using `state`, here's one which is roughly equivalent to `stride(from: 1.0, to: 2.0, by: 0.1)`, using a non-error-accumulating algorithm:

  let start = 1.0
  let end = 2.0
  let distance = 0.1
  
  for color in sequence(state: -1.0, next: { $0 += 1; let next = start + $0 * distance; return next < end ? next : nil }) {
    …
  }

···

--
Brent Royal-Gordon
Architechies


(Trent Nadeau) #8

Ah, yes. I apologize. The fact that state is inout, and the same instance
is always passed in confused me. Thanks for the correction.

···

On Thu, May 19, 2016 at 7:46 PM, Brent Royal-Gordon <brent@architechies.com> wrote:

> Also note that there's a typo in the second example:
>
> for view in sequence(initial: someView, next: { $0.
> superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }
>
>
> should be:
>
> for view in sequence(state: someView, next: { $0.
> superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }

I don't think these are mistakes—in each iteration of the loop, $0 is
supposed to be the view from the previous iteration.

If you wanted an example using `state`, here's one which is roughly
equivalent to `stride(from: 1.0, to: 2.0, by: 0.1)`, using a
non-error-accumulating algorithm:

        let start = 1.0
        let end = 2.0
        let distance = 0.1

        for color in sequence(state: -1.0, next: { $0 += 1; let next =
start + $0 * distance; return next < end ? next : nil }) {
                …
        }

--
Brent Royal-Gordon
Architechies

--
Trent Nadeau


(Matthew Johnson) #9

        * What is your evaluation of the proposal?

+1. These functions are really handy. The standard library should definitely include commonly useful utilities like these.

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

Yes. It’s best to have these in the standard library rather than all creating our own versions.

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

Yes.

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

I like that this proposal modifies the signature of `sequence(state:next:) to use `inout`. The ability to do this is an advantage Swift has over functional languages.

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

Quick reading, but also followed the discussions and the prior review.

···

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 <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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


(Lily Ballard) #10

They wouldn't be lazy anymore.

-Kevin Ballard

···

On Mon, May 23, 2016, at 05:44 AM, Jeremy Pereira via swift-evolution wrote:

> On 19 May 2016, at 23:29, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:
>
>
> * What is your evaluation of the proposal?

+1

I think I would find myself using this in loads of places, if it was implemented.

One question: what is the downside of making these functions `rethrows` and allowing the closure to throw?


(Lily Ballard) #11

After having given this some thought, it seems apparent that
`sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where
the closure captures a single mutable variable. The microbenchmark
performance may differ slightly, as the AnyIterator version will
allocate a box on the heap to hold the captured variable (assuming it
can't get inlined entirely), whereas UnfoldSequence won't. But the
functionality is the same.

Thus the question: do we want to keep `sequence(state:next:)` or is it
too close to AnyIterator in functionality? Arguments in favor of
`sequence(state:next:)`:

* It's equivalent to unfold and the dual of reduce, so people who've
  used functional programming languages may expect it to exist.
* It allows you to create ad-hoc stateful sequences without polluting
  the current scope with a variable that exists solely to be captured.
* If the cost of a small heap allocation is significant for your code,
  it may be more performant than AnyIterator.

Personally, the most important reason here for me is not having to
pollute the current closure with a variable. And this could actually be
solved another way, by allowing the use of `var` in a capture list,
which would let you say something like `AnyGenerator({ [var state=foo]
in ... })`.

Given all this, at this point I'm actually leaning towards
saying`sequence(state:next:)` doesn't pull its own weight and we should
just go with `sequence(initial:next:)`.

-Kevin Ballard

···

On Thu, May 19, 2016, at 05:37 PM, Trent Nadeau via swift-evolution wrote:

Ah, yes. I apologize. The fact that state is inout, and the same
instance is always passed in confused me. Thanks for the correction.

On Thu, May 19, 2016 at 7:46 PM, Brent Royal-Gordon > <brent@architechies.com> wrote:

> Also note that there's a typo in the second example:
>
> for view in sequence(initial: someView, next: { $0. superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }
>
>
> should be:
>
> for view in sequence(state: someView, next: { $0. superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }

I don't think these are mistakes—in each iteration of the loop, $0 is
supposed to be the view from the previous iteration.

If you wanted an example using `state`, here's one which is roughly
equivalent to `stride(from: 1.0, to: 2.0, by: 0.1)`, using a non-error-
accumulating algorithm:

let start = 1.0
let end = 2.0
let distance = 0.1

for color in sequence(state: -1.0, next: { $0 += 1; let next = start
+ $0 * distance; return next < end ? next : nil }) {

}

--
Brent Royal-Gordon Architechies

--
Trent Nadeau
_________________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


Troubling `Sequence`
(Erica Sadun) #12

Adding on, to the best of my understanding the biggest win in the stateful variation is to be able to create a sequence from a starting state without declaring any external variables, as in the perfectly wrong and evil example I showed Kevin:

enum Finger: Int { case Thumb = 1, Pointer, Middle, Ring, Pinky }

extension Finger {
    static func members() -> AnySequence<Finger> {
        return sequence(Thumb.rawValue, next: {
            (inout idx: Int) in
            defer { idx += 1 }
            return Finger(rawValue: idx)
        })
    }
}

for finger in Finger.members() { print(finger) }

-- E

···

On May 19, 2016, at 6:52 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

After having given this some thought, it seems apparent that `sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure captures a single mutable variable. The microbenchmark performance may differ slightly, as the AnyIterator version will allocate a box on the heap to hold the captured variable (assuming it can't get inlined entirely), whereas UnfoldSequence won't. But the functionality is the same.

Thus the question: do we want to keep `sequence(state:next:)` or is it too close to AnyIterator in functionality? Arguments in favor of `sequence(state:next:)`:

* It's equivalent to unfold and the dual of reduce, so people who've used functional programming languages may expect it to exist.
* It allows you to create ad-hoc stateful sequences without polluting the current scope with a variable that exists solely to be captured.
* If the cost of a small heap allocation is significant for your code, it may be more performant than AnyIterator.

Personally, the most important reason here for me is not having to pollute the current closure with a variable. And this could actually be solved another way, by allowing the use of `var` in a capture list, which would let you say something like `AnyGenerator({ [var state=foo] in ... })`.

Given all this, at this point I'm actually leaning towards saying`sequence(state:next:)` doesn't pull its own weight and we should just go with `sequence(initial:next:)`.

-Kevin Ballard


(Patrick Smith) #13

Would `sequence(mutatingState:next:)` perhaps be clearer?

···

On 20 May 2016, at 10:37 AM, Trent Nadeau via swift-evolution <swift-evolution@swift.org> wrote:

Ah, yes. I apologize. The fact that state is inout, and the same instance is always passed in confused me. Thanks for the correction.

On Thu, May 19, 2016 at 7:46 PM, Brent Royal-Gordon <brent@architechies.com <mailto:brent@architechies.com>> wrote:
> Also note that there's a typo in the second example:
>
> for view in sequence(initial: someView, next: { $0.
> superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }
>
>
> should be:
>
> for view in sequence(state: someView, next: { $0.
> superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }

I don't think these are mistakes—in each iteration of the loop, $0 is supposed to be the view from the previous iteration.

If you wanted an example using `state`, here's one which is roughly equivalent to `stride(from: 1.0, to: 2.0, by: 0.1)`, using a non-error-accumulating algorithm:

        let start = 1.0
        let end = 2.0
        let distance = 0.1

        for color in sequence(state: -1.0, next: { $0 += 1; let next = start + $0 * distance; return next < end ? next : nil }) {
                …
        }

--
Brent Royal-Gordon
Architechies

--
Trent Nadeau
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Patrick Smith) #14

This sounds fair to me. I imagine a functional version would return two item tuple instead of mutating, so would it be that similar to what people expect?

···

On 20 May 2016, at 10:52 AM, Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

After having given this some thought, it seems apparent that `sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure captures a single mutable variable. The microbenchmark performance may differ slightly, as the AnyIterator version will allocate a box on the heap to hold the captured variable (assuming it can't get inlined entirely), whereas UnfoldSequence won't. But the functionality is the same.

Thus the question: do we want to keep `sequence(state:next:)` or is it too close to AnyIterator in functionality? Arguments in favor of `sequence(state:next:)`:

* It's equivalent to unfold and the dual of reduce, so people who've used functional programming languages may expect it to exist.
* It allows you to create ad-hoc stateful sequences without polluting the current scope with a variable that exists solely to be captured.
* If the cost of a small heap allocation is significant for your code, it may be more performant than AnyIterator.

Personally, the most important reason here for me is not having to pollute the current closure with a variable. And this could actually be solved another way, by allowing the use of `var` in a capture list, which would let you say something like `AnyGenerator({ [var state=foo] in ... })`.

Given all this, at this point I'm actually leaning towards saying`sequence(state:next:)` doesn't pull its own weight and we should just go with `sequence(initial:next:)`.

-Kevin Ballard

On Thu, May 19, 2016, at 05:37 PM, Trent Nadeau via swift-evolution wrote:

Ah, yes. I apologize. The fact that state is inout, and the same instance is always passed in confused me. Thanks for the correction.

On Thu, May 19, 2016 at 7:46 PM, Brent Royal-Gordon <brent@architechies.com <mailto:brent@architechies.com>> wrote:
> Also note that there's a typo in the second example:
>
> for view in sequence(initial: someView, next: { $0.
> superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }
>
>
> should be:
>
> for view in sequence(state: someView, next: { $0.
> superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }

I don't think these are mistakes—in each iteration of the loop, $0 is supposed to be the view from the previous iteration.

If you wanted an example using `state`, here's one which is roughly equivalent to `stride(from: 1.0, to: 2.0, by: 0.1)`, using a non-error-accumulating algorithm:

let start = 1.0
let end = 2.0
let distance = 0.1

for color in sequence(state: -1.0, next: { $0 += 1; let next = start + $0 * distance; return next < end ? next : nil }) {

}

--
Brent Royal-Gordon
Architechies

--
Trent Nadeau
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

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


(Patrick Smith) #15

I think that is a little confusing and has potential to be ‘abused’. I think it’s more confusing that a `for(;;)` loop for instance, and that got removed. I think var + AnyIterator is more explicit, and can become the canonical way to do this.

Hopefully AnyIterator can be optimized to the same performance.

···

On 20 May 2016, at 10:57 AM, Erica Sadun via swift-evolution <swift-evolution@swift.org> wrote:

On May 19, 2016, at 6:52 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

After having given this some thought, it seems apparent that `sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure captures a single mutable variable. The microbenchmark performance may differ slightly, as the AnyIterator version will allocate a box on the heap to hold the captured variable (assuming it can't get inlined entirely), whereas UnfoldSequence won't. But the functionality is the same.

Thus the question: do we want to keep `sequence(state:next:)` or is it too close to AnyIterator in functionality? Arguments in favor of `sequence(state:next:)`:

* It's equivalent to unfold and the dual of reduce, so people who've used functional programming languages may expect it to exist.
* It allows you to create ad-hoc stateful sequences without polluting the current scope with a variable that exists solely to be captured.
* If the cost of a small heap allocation is significant for your code, it may be more performant than AnyIterator.

Personally, the most important reason here for me is not having to pollute the current closure with a variable. And this could actually be solved another way, by allowing the use of `var` in a capture list, which would let you say something like `AnyGenerator({ [var state=foo] in ... })`.

Given all this, at this point I'm actually leaning towards saying`sequence(state:next:)` doesn't pull its own weight and we should just go with `sequence(initial:next:)`.

-Kevin Ballard

Adding on, to the best of my understanding the biggest win in the stateful variation is to be able to create a sequence from a starting state without declaring any external variables, as in the perfectly wrong and evil example I showed Kevin:

enum Finger: Int { case Thumb = 1, Pointer, Middle, Ring, Pinky }

extension Finger {
    static func members() -> AnySequence<Finger> {
        return sequence(Thumb.rawValue, next: {
            (inout idx: Int) in
            defer { idx += 1 }
            return Finger(rawValue: idx)
        })
    }
}

for finger in Finger.members() { print(finger) }

-- E

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


(Dave Abrahams) #16

On behalf of Dmitri Gribenko, Max Moiseev, and myself:

After having given this some thought, it seems apparent that `sequence
(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure
captures a single mutable variable.

Yes.

The microbenchmark performance may differ slightly, as the AnyIterator
version will allocate a box on the heap to hold the captured variable
(assuming it can't get inlined entirely), whereas UnfoldSequence
won't. But the functionality is the same. Thus the question: do we
want to keep `sequence(state:next:)` or is it too close to AnyIterator
in functionality?

We think the need to do a capture is icky, so the sequence form is
almost always better.

Arguments in favor of `sequence(state:next:)`: *
It's equivalent to unfold and the dual of reduce, so people who've
used functional programming languages may expect it to exist. * It
allows you to create ad-hoc stateful sequences without polluting the
current scope with a variable that exists solely to be captured. * If
the cost of a small heap allocation is significant for your code, it
may be more performant than AnyIterator. Personally, the most
important reason here for me is not having to pollute the current
closure with a variable. And this could actually be solved another
way, by allowing the use of `var` in a capture list, which would let
you say something like `AnyGenerator({ [var state=foo] in ... })`.
Given all this, at this point I'm actually leaning towards
saying`sequence (state:next:)` doesn't pull its own weight and we
should just go with `sequence (initial:next:)`. -Kevin Ballard

We forgot to mention this earlier: we prefer “first” over “initial” as the
label on the latter.

The design of AnySequence and AnyIterator dates from a time when the
compiler was very immature and many design avenues we might have taken
were not available. I find the `sequence` forms to be superior in
general, and IMO at some point we should re-evaluate the interfaces to
AnySequence and AnyIterator.

Cheers,
Dave

···

on Thu May 19 2016, Kevin Ballard <swift-evolution-m3FHrko0VLzYtjvyW6yDsg@public.gmane.org> wrote:

On Thu, May 19, 2016, at 05:37 PM, Trent Nadeau via swift-evolution wrote:

    Ah, yes. I apologize. The fact that state is inout, and the same instance is
    always passed in confused me. Thanks for the correction.

    On Thu, May 19, 2016 at 7:46 PM, Brent Royal-Gordon > <brent-iffxGAVYld63nE1h+Mp7gA@public.gmane.org> wrote:

        > Also note that there's a typo in the second example:
        >
        > for view in sequence(initial: someView, next: { $0.
        > superview }) {
        >
        > // someView, someView.superview, someView.superview.superview, ...
        >
        > }
        >
        >
        > should be:
        >
        > for view in sequence(state: someView, next: { $0.
        > superview }) {
        >
        > // someView, someView.superview, someView.superview.superview, ...
        >
        > }

        I don't think these are mistakes—in each iteration of the loop, $0 is
        supposed to be the view from the previous iteration.

        If you wanted an example using `state`, here's one which is roughly
        equivalent to `stride(from: 1.0, to: 2.0, by: 0.1)`, using a
        non-error-accumulating algorithm:

        let start = 1.0

        let end = 2.0

        let distance = 0.1

        for color in sequence(state: -1.0, next: { $0 += 1; let next = start +
        $0 * distance; return next < end ? next : nil }) {

        …

        }

        --
        Brent Royal-Gordon
        Architechies

    --

    Trent Nadeau

    _______________________________________________

    swift-evolution mailing list

    swift-evolution-m3FHrko0VLzYtjvyW6yDsg@public.gmane.org

    https://lists.swift.org/mailman/listinfo/swift-evolution

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

--
Dave


Troubling `Sequence`
(Erica Sadun) #17

Once you start using it, it's really hard to put it down.

-- E, who will not make the obvious "for" joke

···

On May 19, 2016, at 7:10 PM, Patrick Smith <pgwsmith@gmail.com> wrote:

I think that is a little confusing and has potential to be ‘abused’. I think it’s more confusing that a `for(;;)` loop for instance, and that got removed. I think var + AnyIterator is more explicit, and can become the canonical way to do this.

Hopefully AnyIterator can be optimized to the same performance.

On 20 May 2016, at 10:57 AM, Erica Sadun via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On May 19, 2016, at 6:52 PM, Kevin Ballard via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

After having given this some thought, it seems apparent that `sequence(state:next:)` is equivalent to `AnyIterator({ ... })` where the closure captures a single mutable variable. The microbenchmark performance may differ slightly, as the AnyIterator version will allocate a box on the heap to hold the captured variable (assuming it can't get inlined entirely), whereas UnfoldSequence won't. But the functionality is the same.

Thus the question: do we want to keep `sequence(state:next:)` or is it too close to AnyIterator in functionality? Arguments in favor of `sequence(state:next:)`:

* It's equivalent to unfold and the dual of reduce, so people who've used functional programming languages may expect it to exist.
* It allows you to create ad-hoc stateful sequences without polluting the current scope with a variable that exists solely to be captured.
* If the cost of a small heap allocation is significant for your code, it may be more performant than AnyIterator.

Personally, the most important reason here for me is not having to pollute the current closure with a variable. And this could actually be solved another way, by allowing the use of `var` in a capture list, which would let you say something like `AnyGenerator({ [var state=foo] in ... })`.

Given all this, at this point I'm actually leaning towards saying`sequence(state:next:)` doesn't pull its own weight and we should just go with `sequence(initial:next:)`.

-Kevin Ballard

Adding on, to the best of my understanding the biggest win in the stateful variation is to be able to create a sequence from a starting state without declaring any external variables, as in the perfectly wrong and evil example I showed Kevin:

enum Finger: Int { case Thumb = 1, Pointer, Middle, Ring, Pinky }

extension Finger {
    static func members() -> AnySequence<Finger> {
        return sequence(Thumb.rawValue, next: {
            (inout idx: Int) in
            defer { idx += 1 }
            return Finger(rawValue: idx)
        })
    }
}

for finger in Finger.members() { print(finger) }

-- E

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


(Lily Ballard) #18

This sounds fair to me. I imagine a functional version would return
two item tuple instead of mutating, so would it be that similar to
what people expect?

A functional version of `sequence(state:next:)` would indeed use the
type signature of `next` as `State -> (T, State)?`. This is precisely
how Haskell's `unfoldr` works. But doing that with Swift where the state
contains Copy-on-Write data structures will end up with unnecessary
copies if the COW data structure is mutated.

-Kevin

···

On Thu, May 19, 2016, at 05:59 PM, Patrick Smith wrote:

On 20 May 2016, at 10:52 AM, Kevin Ballard via swift-evolution <swift- >> evolution@swift.org> wrote:

After having given this some thought, it seems apparent that
`sequence(state:next:)` is equivalent to `AnyIterator({ ... })`
where the closure captures a single mutable variable. The
microbenchmark performance may differ slightly, as the AnyIterator
version will allocate a box on the heap to hold the captured variable
(assuming it can't get inlined entirely), whereas UnfoldSequence
won't. But the functionality is the same.

Thus the question: do we want to keep `sequence(state:next:)` or is
it too close to AnyIterator in functionality? Arguments in favor of
`sequence(state:next:)`:

* It's equivalent to unfold and the dual of reduce, so people who've
  used functional programming languages may expect it to exist.
* It allows you to create ad-hoc stateful sequences without polluting
  the current scope with a variable that exists solely to be
  captured.
* If the cost of a small heap allocation is significant for your
  code, it may be more performant than AnyIterator.

Personally, the most important reason here for me is not having to
pollute the current closure with a variable. And this could actually
be solved another way, by allowing the use of `var` in a capture
list, which would let you say something like `AnyGenerator({ [var
state=foo] in ... })`.

Given all this, at this point I'm actually leaning towards
saying`sequence(state:next:)` doesn't pull its own weight and we
should just go with `sequence(initial:next:)`.

-Kevin Ballard

On Thu, May 19, 2016, at 05:37 PM, Trent Nadeau via swift- >> evolution wrote:

Ah, yes. I apologize. The fact that state is inout, and the same
instance is always passed in confused me. Thanks for the correction.

On Thu, May 19, 2016 at 7:46 PM, Brent Royal-Gordon >>> <brent@architechies.com> wrote:

> Also note that there's a typo in the second example:
>
> for view in sequence(initial: someView, next: { $0. superview
> }) {
>
> // someView, someView.superview, someView.superview.superview,
> ...
>
> }
>
>
> should be:
>
> for view in sequence(state: someView, next: { $0. superview }) {
>
> // someView, someView.superview, someView.superview.superview,
> ...
>
> }

I don't think these are mistakes—in each iteration of the loop, $0
is supposed to be the view from the previous iteration.

If you wanted an example using `state`, here's one which is roughly
equivalent to `stride(from: 1.0, to: 2.0, by: 0.1)`, using a non-error-
accumulating algorithm:

let start = 1.0
let end = 2.0
let distance = 0.1

for color in sequence(state: -1.0, next: { $0 += 1; let next =
start + $0 * distance; return next < end ? next : nil }) {

}

--
Brent Royal-Gordon Architechies

--
Trent Nadeau
_________________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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


(Trent Nadeau) #19

It would certainly be clearer that the state is changing on each
"iteration", but I'm not sure it's worth such a long parameter label. Maybe
`sequence(state:update:)`?

···

On Thu, May 19, 2016 at 8:46 PM, Patrick Smith <pgwsmith@gmail.com> wrote:

Would `sequence(mutatingState:next:)` perhaps be clearer?

On 20 May 2016, at 10:37 AM, Trent Nadeau via swift-evolution < > swift-evolution@swift.org> wrote:

Ah, yes. I apologize. The fact that state is inout, and the same instance
is always passed in confused me. Thanks for the correction.

On Thu, May 19, 2016 at 7:46 PM, Brent Royal-Gordon < > brent@architechies.com> wrote:

> Also note that there's a typo in the second example:
>
> for view in sequence(initial: someView, next: { $0.
> superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }
>
>
> should be:
>
> for view in sequence(state: someView, next: { $0.
> superview }) {
>
> // someView, someView.superview, someView.superview.superview, ...
>
> }

I don't think these are mistakes—in each iteration of the loop, $0 is
supposed to be the view from the previous iteration.

If you wanted an example using `state`, here's one which is roughly
equivalent to `stride(from: 1.0, to: 2.0, by: 0.1)`, using a
non-error-accumulating algorithm:

        let start = 1.0
        let end = 2.0
        let distance = 0.1

        for color in sequence(state: -1.0, next: { $0 += 1; let next =
start + $0 * distance; return next < end ? next : nil }) {
                …
        }

--
Brent Royal-Gordon
Architechies

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

--
Trent Nadeau


(Lily Ballard) #20

On behalf of Dmitri Gribenko, Max Moiseev, and myself:

> After having given this some thought, it seems apparent that `sequence
> (state:next:)` is equivalent to `AnyIterator({ ... })` where the closure
> captures a single mutable variable.

Yes.

> The microbenchmark performance may differ slightly, as the AnyIterator
> version will allocate a box on the heap to hold the captured variable
> (assuming it can't get inlined entirely), whereas UnfoldSequence
> won't. But the functionality is the same. Thus the question: do we
> want to keep `sequence(state:next:)` or is it too close to AnyIterator
> in functionality?

We think the need to do a capture is icky, so the sequence form is
almost always better.

I agree that the need for a capture is ugly.

> Arguments in favor of `sequence(state:next:)`: *
> It's equivalent to unfold and the dual of reduce, so people who've
> used functional programming languages may expect it to exist. * It
> allows you to create ad-hoc stateful sequences without polluting the
> current scope with a variable that exists solely to be captured. * If
> the cost of a small heap allocation is significant for your code, it
> may be more performant than AnyIterator. Personally, the most
> important reason here for me is not having to pollute the current
> closure with a variable. And this could actually be solved another
> way, by allowing the use of `var` in a capture list, which would let
> you say something like `AnyGenerator({ [var state=foo] in ... })`.
> Given all this, at this point I'm actually leaning towards
> saying`sequence (state:next:)` doesn't pull its own weight and we
> should just go with `sequence (initial:next:)`. -Kevin Ballard

We forgot to mention this earlier: we prefer “first” over “initial” as the
label on the latter.

I agree. I almost suggested this a few days ago, but I didn't want to end up bikeshedding the parameter names. I'm inclined to say that the Swift core team should decide whether to change it to "first" instead of debating it, and if so, make that modification when accepting (assuming of course that it does get accepted).

The design of AnySequence and AnyIterator dates from a time when the
compiler was very immature and many design avenues we might have taken
were not available. I find the `sequence` forms to be superior in
general, and IMO at some point we should re-evaluate the interfaces to
AnySequence and AnyIterator.

That sounds like a reasonable justification for keeping sequence(state:next:).

-Kevin Ballard

···

On Wed, May 25, 2016, at 01:08 PM, Dave Abrahams wrote:

on Thu May 19 2016, Kevin Ballard <swift-evolution-m3FHrko0VLzYtjvyW6yDsg@public.gmane.org> wrote:

Cheers,
Dave

> On Thu, May 19, 2016, at 05:37 PM, Trent Nadeau via swift-evolution wrote:
>
> Ah, yes. I apologize. The fact that state is inout, and the same instance is
> always passed in confused me. Thanks for the correction.
>
> On Thu, May 19, 2016 at 7:46 PM, Brent Royal-Gordon > > <brent-iffxGAVYld63nE1h+Mp7gA@public.gmane.org> wrote:
>
> > Also note that there's a typo in the second example:
> >
> > for view in sequence(initial: someView, next: { $0.
> > superview }) {
> >
> > // someView, someView.superview, someView.superview.superview, ...
> >
> > }
> >
> >
> > should be:
> >
> > for view in sequence(state: someView, next: { $0.
> > superview }) {
> >
> > // someView, someView.superview, someView.superview.superview, ...
> >
> > }
>
> I don't think these are mistakes—in each iteration of the loop, $0 is
> supposed to be the view from the previous iteration.
>
> If you wanted an example using `state`, here's one which is roughly
> equivalent to `stride(from: 1.0, to: 2.0, by: 0.1)`, using a
> non-error-accumulating algorithm:
>
> let start = 1.0
>
> let end = 2.0
>
> let distance = 0.1
>
> for color in sequence(state: -1.0, next: { $0 += 1; let next = start +
> $0 * distance; return next < end ? next : nil }) {
>
> …
>
> }
>
> --
> Brent Royal-Gordon
> Architechies
>
> --
>
> Trent Nadeau
>
> _______________________________________________
>
> swift-evolution mailing list
>
> swift-evolution-m3FHrko0VLzYtjvyW6yDsg@public.gmane.org
>
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave