[swift-evolution] Proposal: CollectionType.cycle property for an infinite sequence

[Kevin Ballard]

On Tue, Dec 29, 2015, at 10:12 PM, Andrew Bennett wrote:
> Hi Kevin,
>
> The issue I was seeing was because AnySequence uses the protocol
> extension on SequenceType for its implementations of
> filter/suffix/prefix etc. So I don't think it's taking into account
> any implementations of those on the base sequence's type.
>
> The problem basically comes down to this:
>> AnySequence([1,2,3].cycle).suffix(1) uses SequenceType's
>> implementation of suffix. [1,2,3].cycle.suffix(1) uses
>> CycleSequence's implementation of suffix.
> If you provide any custom implementations for CycleSequence
> AnySequence will not preserve that intent. This is probably a bug.

The only way to actually fix this is to have AnySequence contain a
closure for each method defined in SequenceType that calls the
underlying implementation (and wraps the result in AnySequence as
necessary). This is rather heavy-weight, which is probably why it
doesn't do that.

Really, I don't think it's particularly surprising that wrapping a
sequence in AnySequence causes the sequence's own implementations of the
optional methods to not be called. It would be great if there was a
simple way to fix this, but it's not worth the cost of reifying all the
runtime type information necessary.

> Another side-effect of AnySequence is that @available(*, unavailable,
> message="this cannot be used on an infinite sequence") onCycleSequence
> will not work if you wrap it with AnySequence. It would still be nice
> to do this, it's just not robust.

Since that's a compile-time check, it is quite impossible to ever
support that on a sequence that's wrapped in AnySequence.

-Kevin Ballard

> I've added a bug report (SR-413[1]) to add missing SequenceType
> methods to AnySequence so that they use the correct version. I think
> this should address my concerns.
>
> If that bug is fixed then the only remaining problem I have is to
> decide is if suffix/array should enter an infinite loop or fatalError.
> Personally I'm leaning towards fatalError as it's more likely to let a
> developer know what's wrong.
>
>
> On Wed, Dec 30, 2015 at 5:44 AM, Kevin Ballard <kevin at sb.org> wrote:
>> __
>>
>> On Tue, Dec 29, 2015, at 02:27 AM, Andrew Bennett wrote:
>>> +1 looks good, I had a go at implementing it and I think it may
>>> require changes not discussed in the proposal.
>>>
>>> You've covered the potential issues fairly well, to be a little more
>>> explicit these are the issues I've found:
>>>> 1) LazySequenceType's property array cannot be defined without an
>>>> infinite sized array.
>>
>>
>> Good point, I forgot about that one. But that's really just the same
>> thing as saying `Array(seq)`, so I don't have any problems with just
>> saying that it's an error to access that property on an infinite
>> sequence (in this case I'd just make it fatalError()).
>>
>> I do wish I could mark those sorts of things with @available(*,
>> unavailable, message="this cannot be used on an infinite sequence")
>> to provide a compile-time error for anyone accessing it on the
>> concrete type (generic access via the protocol wouldn't catch that of
>> course), but I discovered that if you try and use that on a function
>> like map(), Swift actually goes ahead and adds the default
>> implementation to your type anyway (basically throwing away your marked-as-
>> unavailable method). Which I suppose makes some sense, but I wish
>> there was an alternative that worked.
>>
>>
>>>> 2) what should [1,2,3].cycle.suffix(4) return? [3,1,2,3] probably
>>>> has the least surprises, but it's like asking what's the number
>>>> before infinity.
>>
>>
>> Nothing. You can't take a suffix on an infinite list. There is no end
>> to it. That method should be overridden to fatalError() (or if not,
>> it would just loop forever).
>>
>>
>>>> 3) dropLast should return AnySequence(self), but requires
>>>> specialisation, this may have to also be a fatalError (see below).
>>
>>
>> Good point. Since there is no end to the sequence, dropLast() on an
>> infinite sequence is still an infinite sequence. Honestly, the
>> default implementation should work fine, but it's probably a good
>> idea to just override it to return AnySequence(self) as you suggest
>> anyway because it's an easy win.
>>
>>
>>> One issue I don't think you've mentioned, and I don't seem to be
>>> able to resolve is this:
>>>> let mySequence = [1,2,3].cycle.dropLast(1) mySequence.suffix(7)
>>>
>>> This could have well defined behaviour (see part 2 above), however
>>> the implementation has some issues.
>>
>>
>> The only well-defined behavior this can have is to loop forever (or
>> to abort with a fatalError). It's simply an error to take a suffix()
>> of an infinite sequence.
>>
>>
>>> In this case mySequence is an AnySequence<Int>, mySequence.suffix(7)
>>> uses AnySequence's specialisation and so tries to iterate over the
>>> entire sequence to find the suffix. AnySequence<Int> is type-erased
>>> so there's no way to specialise when the underlying sequence is
>>> infinite (to get a valid implementation of suffix).
>>
>>
>> That's fine, looping forever is a perfectly reasonable course of
>> action when you try and take a suffix() of an infinite sequence.
>>
>>
>>> Potential solutions: * Replace erased Any* types with a more
>>> flexible alternative that doesn't remove type information (higher
>>> kinded types perhaps).
>>
>>
>> The whole point of the Any* types is they do remove type information.
>>
>>
>>> * Replace SequenceType with two protocols FiniteSequenceType and
>>> InfiniteSequenceType, have type erased versions of each, duplicate
>>> all the things.
>>
>>
>> What's the point of this? All you can do with that is get rid of a
>> couple of methods that would loop forever on infinite sequences, but
>> it's a lot of work and a lot of duplication for what seems like an
>> extremely small win.
>>
>> I'd much rather just come up with some alternative to @available(*,
>> unavailable) that actually leaves the method intact but provides a
>> compile-time error if you call it. This would be strictly intended
>> for protocol methods, as you'd still need to provide an
>> implementation (such as `fatalError("not supported")`) that would be
>> called when the method is accessed via a generic type bound on the
>> protocol (or via an existential protocol value, for protocols that
>> support that).
>>
>>
>>> * Add a property to SequenceType to indicate if it's definitely
>>> finite (undefined?), AnySequence uses a different backing
>>> implementation depending on this boolean.
>>
>>
>> And what would AnySequence do with that information? All it could
>> really do is make sure to call fatalError() instead of looping
>> forever when a method like suffix() is called.
>>
>>
>> -Kevin Ballard
>>



Links:

  1. https://bugs.swift.org/browse/SR-413
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151229/bc4871dd/attachment.html>