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

[Kevin Ballard]

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/20151229/94be5bd9/attachment.html>