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

[Andrew Bennett]

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.

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

I've added a bug report (SR-413 <https://bugs.swift.org/browse/SR-413>) 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151230/7ee7db11/attachment.html>