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

[Kevin Ballard]

On Thu, May 19, 2016, at 05:59 PM, Patrick Smith wrote:
> 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 20 May 2016, at 10:52 AM, Kevin Ballard via swift-evolution <swift-
>> evolution at 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 at 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 at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160519/3220ff7f/attachment.html>