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

[Kevin Ballard]

On Tue, Dec 29, 2015, at 03:39 PM, plx via swift-evolution wrote:
>
>> On Dec 29, 2015, at 1:17 PM, Kevin Ballard via swift-evolution <swift-
>> evolution at swift.org> wrote:
>>
>> On Tue, Dec 29, 2015, at 08:14 AM, plx via swift-evolution wrote:
>>> Personally I’d say this should be a -1 for standard-library
>>> inclusion.
>>>
>>> Swift’s not really built to handle infinite sequences right now;
>>> until they are handed better by the standard library convenience
>>> methods for creating them shouldn’t be in the standard library.
>>
>> As far as I can tell, the only way in which it's "not really built"
>> to handle this is that there are multiple constructs that attempt to
>> eagerly consume an entire sequence, and using these with an infinite
>> sequence would end up looping forever. But I don't consider that to
>> be a particularly serious problem. You could "fix" it by refactoring
>> SequenceType into two protocols, SequenceType (for possibly-infinite
>> sequences) and FiniteSequenceType (for known-finite sequences) and
>> then going over the entire standard library and updating various
>> spots to use FiniteSequenceType, except this would be very limiting
>> (sequences that are not known if they're infinite to the compiler
>> could still be valid for various eager algorithms if the programmer
>> knows it will be finite in practice).
>
> Indeed, on my wishlist I would like to see the standard protocols
> refactored to something more like this:
>
> SequenceType // can be iterated FiniteSequenceType : SequenceType, //
> of finite length StableSequenceType : SequenceType, // can be re-
> iterated identically CollectionType : StableSequenceType,
> FiniteSequenceType, (etc.) // otherwise as it is now
>
> …but can understand the wish to not overly-complicate the basic
> protocol hierarchy (and also to avoid baking-in nice-to-have, but impossible-to-really-
> enforce semantic requirements; I’d trust the standard library to use
> them properly, but not typical 3rd party code, somewhat defeating the
> purpose).
>
> Everything else is a difference of outlook; we agree on the facts and
> differ in interpretation.
>
> I consider concrete types that adopt a protocol only to simply call
> `fatalError` for most of the protocol methods to be pathological —
> often useful, but still pathological — and thus far the standard
> library doesn’t contain any such pathological types (to my knowledge).

It only calls `fatalError` because the default implementation would loop
forever anyway (and consume more and more memory until this eventually
causes a crash). You can trivially remove the `fatalError()`
implementations and still have the CycleSequence type, the only reason
to have them is because we may as well tell the user exactly what they
did wrong instead of letting the program enter an infinite loop that
tries to eat all the memory in the system.

> `cycle` is useful but not useful enough to be the standard library’s
> first “pathological” type, so it’s still a -1 as proposed.

There's plenty of use for infinite sequences. And all infinite sequences
are "pathological" in the same sense. The fact that the stdlib doesn't
provide any convenient ways to produce infinite sequences right now is a
deficiency, not an advantage. As previously stated, the issues with
infinite sequences also manifest with extremely long finite sequences
(such as `(1..<Int.max)`). Also, the stdlib does already provide a way
to make your own infinite sequences already, which is to use
`anyGenerator()` with a function that can never return `nil`.

Which is to say, the only thing special about Cycle is that it can
eagerly detect some infinite loops and trigger a fatalError().

It's also worth pointing out here that CycleSequence is inherently lazy
(it conforms to LazySequenceType), which provides lazy versions of
map/filter/etc., so you're only ever going to actually hit the eager
SequenceType variants when either working generically with <T:
SequenceType> or if you explicitly constrain the return value of
map()/filter() to Array (which will cause it to resolve to the
SequenceType version). But in both cases, the problems with Cycle are,
as I said before, the same problems you'd get with something like
`(1..<Int.max)`.

>>> You can conceivably implement a non-crashing `contains`,
>>> `minElement` and `maxElement` on `CycleSequence` by calling through
>>> to the wrapped collection, but that’ll seemingly evaporate as soon
>>> as your `CycleSequence` winds up hidden inside an `AnySequence`.
>>
>> You can't override those anyway in a generic context, because they're
>> not members of the protocol, they're just extensions. You could
>> implement them such that your implementation is called when working
>> on the concrete CycleSequence type, but I'm not sure if that's a
>> great idea to do that when the actual behavior differs from calling
>> it generically on SequenceType (well, triggering a fatalError()
>> instead of an infinite loop is fine because they're both Bottom, but
>> returning a valid result in one context and looping infinitely in the
>> other seems bad).
>>
>> Of course, these methods could actually be moved into the protocol
>> itself, which would let us override them. I'm not entirely sure why
>> they aren't in the protocol to begin with, I guess because there's
>> not much need for overriding these outside of infinite sequences
>> (well, finite sorted sequences could provide an optimized
>> min/maxElement, and an optimized version of contains(_:
>> Self.Generator.Element), but maybe there's tradeoffs to doing this,
>> e.g. maybe there's some reason why having a large protocol witness
>> table is a bad idea).
>
> I don’t think `contains` or `minElement/maxElement` *can* be part of
> the protocol (in the sense of overridable) at this time (they require
> `Element` satisfy certain type constraints), but they certainly should
> be if the type system someday would support that.

They actually can. There's two variants of each function; one which
takes a comparison function, and one which requires the
Comparable/Equatable bound. The version for Comparable/Equatable can't
be part of the protocol itself (and shouldn't be; it's just a
convenience for providing the appropriate comparison function), but the
version that takes a function has no bounds on it and could be part of
the protocol itself.

-Kevin Ballard
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151229/60574d98/attachment-0001.html>