[swift-evolution] Passing an optional first argument to sequence(first:next:)

Dave Abrahams dabrahams at apple.com
Thu Sep 1 16:47:14 CDT 2016

```on Tue Aug 30 2016, Max Moiseev <moiseev-AT-apple.com> wrote:

> FWIW, the ‘classical’ way of doing what I think you’re trying to do is:
>
> extension Sequence {
>   var pairs: AnySequence<(Iterator.Element, Iterator.Element)> {
>     return AnySequence(zip(self, self.dropFirst()))
>   }
> }
>
> Does it have the right behavior?

Cute, but that one requires that self is a collection (depends on
multipass behavior)

>
> Max
>
>> On Aug 29, 2016, at 9:45 AM, Tim Vermeulen via swift-evolution <swift-evolution at swift.org> wrote:
>>
>> The intent of my function wasn’t very clear, but it was supposed to
>> return a sequence that contains *all* consecutive pairs, i.e. (0 ..<
>> 4).pairs would result in [(0, 1), (1, 2), (2, 3)].
>>
>>> on Fri Aug 26 2016, Tim Vermeulen<swift-evolution at swift.org>wrote:
>>>
>>>> This is when I first wanted to pass an optional for the `first` parameter:
>>>>
>>>> extension Sequence {
>>>>
>>>> /// Returns a sequence of pairs of consecutive elements
>>>> /// of the sequence, in order.
>>>> var pairs: AnySequence<(Iterator.Element, Iterator.Element)>{
>>>> var iterator = makeIterator()
>>>>
>>>> let firstPair = iterator.next().flatMap { first in
>>>> iterator.next().map { second in (first, second) }
>>>> }
>>>>
>>>> // I can't do this, because `firstPair` is optional
>>>> let seq = sequence(first: firstPair) { _, second in
>>>> guard let next = iterator.next() else { return nil }
>>>> return (second, next)
>>>> }
>>>>
>>>> return AnySequence(seq)
>>>> }
>>>>
>>>> }
>>>>
>>>> In this particular case, finding a workaround is fairly easy (with a
>>>> guard and `return AnySequence([])` in the `else` block). However, this
>>>> becomes less elegant if you just want to iterate over it rather than
>>>> wrap it in AnySequence.
>>> This is why we have sequence(state:next:)
>>>
>>>
>>> extension Sequence {
>>> /// Returns a sequence of pairs of consecutive elements
>>> /// of the sequence, in order.
>>> var pairs: AnySequence<(Iterator.Element, Iterator.Element)>{
>>> return AnySequence(
>>> sequence(
>>> state: makeIterator(),
>>> next: { (iter: inout Iterator) in
>>> iter.next().flatMap { first in
>>> iter.next().map { (first, \$0) }
>>> }
>>> })
>>> )
>>> }
>>> }
>>>
>>> for j in 0..<10 {
>>> print(Array((0..<j).pairs))
>>> }
>>>
>>> HTH,
>>> Dave
>>>>
>>>>> Hi Tim,
>>>>>
>>>>> After having a quick conversation with Dave, here is the question I
>>>>> should have asked right away: can you share the typical problem you
>>>>> function?
>>>>>
>>>>> Max
>>>>>
>>>>>
>>>>>> On Aug 20, 2016, at 2:26 AM, Tim
>>>>>> Vermeulen<tvermeulen at me.com(mailto:tvermeulen at me.com)>wrote:
>>>>>> What you’re saying makes sense, and I might not have brought this
>>>>>> up in the first place if `first.map { sequence(first: \$0, next:
>>>>>> next } ?? []` worked. The main annoyance is that the best solution
>>>>>> (currently) seems to be to copy the source code and make a change.
>>>>>>
>>>>>> (cc-ing Jordan Rose because of a related swift-users thread) This
>>>>>> might be a bit of a stretch, but can’t Swift upcast sequences to
>>>>>> AnySequence implicitly, like is done with AnyHashable? That would
>>>>>> make `first.map { sequence(first: \$0, next: next } ?? []`
>>>>>> instantly valid, I think. There’s also something to be said for
>>>>>> consistency between type erasers. (I’m not necessarily talking
>>>>>>> On 20 Aug 2016, at 02:22, Max
>>>>>>> Moiseev<moiseev at apple.com(mailto:moiseev at apple.com)>wrote:
>>>>>>> Hi Tim,
>>>>>>>
>>>>>>> I still believe that having 2 termination conditions is
>>>>>>> wrong. But I guess we need a tie breaker here, someone with a
>>>>>>> strong opinion about the problem.
>>>>>>> As Kevin mentioned we are very late in the release process, so
>>>>>>> waiting for another opinion for a day or two won’t change
>>>>>>> anything, really.
>>>>>>>
>>>>>>> Meanwhile, I played a little bit with an idea of making `first.map { sequence(first \$0, next: next} ?? []` work.
>>>>>>> Turns out, if we add an `ExpressibleByArrayLiteral` protocol
>>>>>>> conformance to the `UnfoldSequence`, this snippet will compile
>>>>>>> just fine. One downside is that the `ExpressibleByArrayLiteral`
>>>>>>> protocol allows creating non-empty sequences as well, which does
>>>>>>> not make sense for the `UnfoldSequence`.
>>>>>>>
>>>>>>>
>>>>>>> Max
>>>>>>>
>>>>>>>> On Aug 19, 2016, at 3:48 PM, Tim Vermeulen via
>>>>>>>> swift-evolution<swift-evolution at swift.org(mailto:swift-evolution at swift.org)>wrote:
>>>>>>>>>
>>>>>>>>> On 19 Aug 2016, at 19:48, Kevin Ballard<kevin at sb.org(mailto:kevin at sb.org)>wrote:
>>>>>>>>> AFAIK this issue has never been discussed with
>>>>>>>>> sequence(first:next:) before. It certainly wasn't brought up
>>>>>>>>> during review.
>>>>>>>>>
>>>>>>>>> As for my opinion, I'm really not sure. I was going to point
>>>>>>>>> out that right now sequence(first:next:) guarantees that the
>>>>>>>>> first element of the resulting sequence is the value
>>>>>>>>> provided as "first", but it occurs to me that if you treat
>>>>>>>>> the nil result from next() as an element, then this still
>>>>>>>>> holds true. So I guess my biggest worry is this change will
>>>>>>>>> make it harder to use sequence(first:next:) to produce
>>>>>>>>> sequences of optional values.
>>>>>>>>
>>>>>>>> I don’t think producing sequences of optional values would
>>>>>>>> really be a problem, because type inference will figure this
>>>>>>>> out based on whether you treat the argument to the `next`
>>>>>>>> closure as an optional or not. And if you only do things in
>>>>>>>> `next` that work both with optionals and non-optionals (very
>>>>>>>> unlikely), you can always manually specify the type of the
>>>>>>>> sequence.
>>>>>>>>> So I guess I'm ambivalent, and would prefer to defer to the wisdom of the Swift core team on this matter.
>>>>>>>>>
>>>>>>>>> That said, didn't the deadline for source-breaking changes already come and go?
>>>>>>>>>
>>>>>>>>> -Kevin Ballard
>>>>>>>>>
>>>>>>>>> On Fri, Aug 19, 2016, at 10:37 AM, Max Moiseev wrote:
>>>>>>>>>> + Erica, Kevin, as the authors of the original proposal.
>>>>>>>>>>
>>>>>>>>>> Do you remember the problem of non-emptiness being
>>>>>>>>>> discussed before? And if not, what’s your opinion on the
>>>>>>>>>> proposed change?
>>>>>>>>>>
>>>>>>>>>> Thanks,
>>>>>>>>>> Max
>>>>>>>>>>
>>>>>>>>>>> On Aug 19, 2016, at 7:53 AM, Tim
>>>>>>>>>>> Vermeulen<tvermeulen at me.com(mailto:tvermeulen at me.com)>wrote:
>>>>>>>>>>>
>>>>>>>>>>> Hi Max, thanks for having a look.
>>>>>>>>>>>
>>>>>>>>>>> A big part of why I’m not really happy with the current
>>>>>>>>>>> implementation is that the function always produces a
>>>>>>>>>>> nonempty sequence, though the compiler doesn’t know
>>>>>>>>>>> it. `sequence(first: first, next: next).last` returns an
>>>>>>>>>>> optional, even though it can’t possibly be nil. The same
>>>>>>>>>>> goes for something like `sequence(first: 5, next: { \$0 *
>>>>>>>>>>> 3 }).first(where: { \$0>1000 })`, because the sequence is
>>>>>>>>>>> infinite, which means `first(while:)` will either keep
>>>>>>>>>>> running forever, or return a non-optional.
>>>>>>>>>>>
>>>>>>>>>>> Ideally, we’d have three types of sequences, with three corresponding `sequence(first:next:)` functions:
>>>>>>>>>>>
>>>>>>>>>>> func sequence<T>(first: T?, next: (T) ->T?)—returns any sequence
>>>>>>>>>>> func sequence<T>(first: T,next: (T) ->T?)—returns a nonempty sequence
>>>>>>>>>>> func sequence<T>(first: T,next: (T) ->T)—returns an infinite sequence
>>>>>>>>>>>
>>>>>>>>>>> Default implementations for methods on sequences would
>>>>>>>>>>> either return optionals or non-optionals depending on
>>>>>>>>>>> their emptiness/finiteness. We just have the first kind
>>>>>>>>>>> of sequence right now, so in that regard it would make
>>>>>>>>>>> sense to also give `sequence(first:next)` the
>>>>>>>>>>> corresponding signature.Later, when the language /
>>>>>>>>>>> standard library supports the other two kinds of
>>>>>>>>>>> sequences (if that ever happens), the other versions
>>>>>>>>>>>
>>>>>>>>>>> Another reason that makes me think that the version that
>>>>>>>>>>> accepts an optional `first` argument is more natural, is
>>>>>>>>>>> the fact that the function body doesn’t need to be
>>>>>>>>>>> changed at all. It supports optional seeds by design;
>>>>>>>>>>> only the signature prevents it.
>>>>>>>>>>>
>>>>>>>>>>> I know these arguments might not be very convincing, but
>>>>>>>>>>> I feel like Swift misses an opportunity if it
>>>>>>>>>>> unnecessarily constrains the `first` parameter to be
>>>>>>>>>>> non-optional. The `.lazy.flatMap({ \$0 })` alternative
>>>>>>>>>>> that you pointed out does work, but it makes everything
>>>>>>>>>>> very unreadable: not just the `.lazy.flatMap({ \$0 })`
>>>>>>>>>>> part, but also the body of the `next` parameter because
>>>>>>>>>>> you’re now dealing with optionals (i.e. you have to
>>>>>>>>>>> `flatMap` over the closure argument). The best solution
>>>>>>>>>>> I’ve come up with is to copy the `sequence(first:next)`
>>>>>>>>>>> implementation from the source code and change the
>>>>>>>>>>> signature. :-/
>>>>>>>>>>>
>>>>>>>>>>> `sequence(state:next:)` isn’t very appropriate for this
>>>>>>>>>>> task either, because naive usage with an optional seed
>>>>>>>>>>> has the downside of being unnecessarily eager just like
>>>>>>>>>>> a naive `sequence(first:next)` implementation (as
>>>>>>>>>>> described in a comment in the source code).
>>>>>>>>>>>
>>>>>>>>>>>> On 19 Aug 2016, at 00:18, Max
>>>>>>>>>>>> Moiseev<moiseev at apple.com(mailto:moiseev at apple.com)>wrote:
>>>>>>>>>>>>
>>>>>>>>>>>> Hi Tim,
>>>>>>>>>>>>
>>>>>>>>>>>> Thanks for bringing this up.
>>>>>>>>>>>> Here are my thoughts on the change you’re proposing.
>>>>>>>>>>>>
>>>>>>>>>>>> func sequence<T>(first: T, next: (T) ->T?) ->UnfoldFirstSequence<T>
>>>>>>>>>>>>
>>>>>>>>>>>> To me the type of the function as it is tells a clear
>>>>>>>>>>>> story of what’s going to happen: take the `first`,
>>>>>>>>>>>> make it a head of the resulting sequence, and then try
>>>>>>>>>>>> to produce the tail by a series of applications of
>>>>>>>>>>>> `next`. The only thing that controls when the sequence
>>>>>>>>>>>> generation terminates is the result of `next`.
>>>>>>>>>>>>
>>>>>>>>>>>> If we change the type of `first` to an Optional<T>, it
>>>>>>>>>>>> would make the termination condition
>>>>>>>>>>>> non-trivial. After all, the only thing it would do is
>>>>>>>>>>>> try to unwrap the `first`, before doing what it needs
>>>>>>>>>>>> to, but we already have a `map` for that. One should
>>>>>>>>>>>> be able to simply do the `first.map { sequence(first:
>>>>>>>>>>>> \$0, next: next) } ?? []` but that won’t work with the
>>>>>>>>>>>> types very well, unfortunately.
>>>>>>>>>>>>
>>>>>>>>>>>> As an alternative, `let first: Int? = ...;
>>>>>>>>>>>> sequence(first: first, next: next).flatMap({\$0})` (or
>>>>>>>>>>>> even `.lazy.flatMap({\$0})`) will do the right thing
>>>>>>>>>>>> without making an API more complex.
>>>>>>>>>>>>
>>>>>>>>>>>> I see the point of `sequence(first:next:)` to be
>>>>>>>>>>>> precisely the "generate the non-empty sequence using a
>>>>>>>>>>>> seed and a simple producer", for anything more than
>>>>>>>>>>>> that, there is `sequence(state:next:)`.
>>>>>>>>>>>>
>>>>>>>>>>>> What do you think?
>>>>>>>>>>>>
>>>>>>>>>>>> Max
>>>>>>>>>>>>
>>>>>>>>>>>>> On Aug 14, 2016, at 4:27 PM, Tim Vermeulen via
>>>>>>>>>>>>> swift-evolution<swift-evolution at swift.org(mailto:swift-evolution at swift.org)>wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>> sequence(first:next:) takes a non-optional first
>>>>>>>>>>>>> argument. Is there a reason for that?
>>>>>>>>>>>>> sequence(state:next:) allows empty sequences, and I
>>>>>>>>>>>>> don’t see why sequence(first:next:) shouldn’t. The
>>>>>>>>>>>>> fix would be to simply add the `?` in the function
>>>>>>>>>>>>> signature; no other changes are required to make it
>>>>>>>>>>>>> work.
>>>>>>>>>>>>>
>>>>>>>>>>>>> I considered just filing a bug report, but since this is a change of the public API...
>>>>>>>>>>>>> _______________________________________________
>>>>>>>>>>>>> swift-evolution mailing list
>>>>>>>>>>>>> swift-evolution at swift.org(mailto:swift-evolution-m3FHrko0VLw at public.gmane.orgg)
>>>>>>>>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> swift-evolution mailing list
>>>>>>>> swift-evolution at swift.org(mailto: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
>>> --
>>> -Dave
>>>
>>>
>>>
>>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution

--
-Dave
```