> On Dec 29, 2015, at 1:17 PM, Kevin Ballard via swift-evolution > <swift-evolution@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). `cycle` is useful but not useful enough to be the standard library’s first “pathological” type, so it’s still a -1 as proposed. This is nothing specific to `cycle` and my opinion here could change were the language or the standard library to evolve in various ways. > >> You’d also want to call `fatalError` for at least `reduce`, `reverse`, >> `sort`, `split`(?), `flatMap`, `dropLast`, `suffix`, and `forEach`. > > You can only do it for the ones defined in the protocol, not ones defined in > extensions. This means map, filter, forEach, and suffix. > > split is actually perfectly implementable for a CycleSequence, although it > does need a custom implementation. split is bounded by at most Int.max > splits, which means it is guaranteed to terminate even for an infinite > sequence (although the final subsequence does need to be infinite[1]). Even > if there are no separators in the cycle, it can just return the cycle itself. > > [1] Interestingly, the current implementation actually dumps the remainder > into an Array and returns that (wrapped in AnySequence), which is curious > because it would be perfectly legal for it to just wrap the generator up in > AnySequence and return that instead. I'm tempted to submit a PR to change > that now, as it just seems like unnecessary work to use an array. > >> `startsWith` and `elementsEqual` and `lexicographicComparison` are all >> broken if you call them like e.g. `self.startsWith(self)`. > > That's true, but what do you really expect when you're calling them with two > infinite sequences? It's not so much that they're broken as it is that you're > creating an infinite loop without any way to break out. And FWIW, > lexicographicalCompare is actually something you might want to explicitly > support on infinite sequences if you know your sequences aren't equal and > want to find out which one is less than the other. > > There are plenty of ways to shoot yourself in the foot. I don't think > infinite sequences are really the big problem you're making them out to be. > >> 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. > >> Which illustrates why this is a -1 for me; there's nothing wrong with the >> functionality in isolation and there’s nothing wrong with infinite >> sequences, but the standard library should play well with itself, and this >> wouldn’t play well with the rest of the standard library. > > Ultimately, there's not much difference between an infinite sequence and a > sequence of Int.max elements. The latter is finite, but it's so massive > (especially on 64-bit) that any kind of eager processing is going to hit the > same problems as an infinite sequence. Every problem you describe will be a > problem with the simple sequence `(0..<Int.max)` as well. > > -Kevin Ballard > >> That opinion could change as the language changes or the standard library >> evolves. >> >>> On Dec 28, 2015, at 1:20 AM, Kevin Ballard via swift-evolution >>> <swift-evolution@swift.org> wrote: >>> >>> ## Introduction >>> >>> Add a new property `cycle` to CollectionType that returns an infinite >>> SequenceType that yields the elements of the collection in a loop. >>> >>> ## Motivation >>> >>> It's sometimes useful to be able to have an infinite sequence. For example, >>> `CollectionOfOne(x).cycle` could be used to have an infinite sequence of a >>> single element (similar to Repeat but without a count). A common use for >>> infinite sequences is zipping with a finite sequence. As far as I'm aware, >>> the stdlib does not currently provide any way to create such an infinite >>> sequence. >>> >>> ## Proposed solution >>> >>> Extend CollectionType with a new property `cycle` that yields a type that >>> conforms to SequenceType. This sequence yields each element of the >>> collection in an infinite loop. >>> >>> ## Detailed design >>> >>> 2 new types would be added: >>> >>> struct CycleSequence<Base : CollectionType> : LazySequenceType { ... } >>> struct CycleGenerator<Base : CollectionType> : GeneratorType { ... } >>> >>> CollectionType would be extended with a property: >>> >>> extension CollectionType { >>> public var cycle: CycleSequence<Self> { get } >>> } >>> >>> This is an extension of CollectionType instead of SequenceType because it >>> requires a multi-pass sequence (and SequenceType does not provide that >>> guarantee). The returned type conforms to SequenceType instead of >>> CollectionType because there is no possible `endIndex` that satisfies the >>> requirement of being reachable from `startIndex` by zero or more >>> applications of `successor()`. >>> >>> Because the default eager versions of map and filter will execute forever >>> on an infinite sequence, CycleSequence conforms to LazySequenceType instead >>> of SequenceType in order to provide lazy versions of those functions. >>> Additionally, it will provide implementations of the eager versions that >>> simply trigger a fatalError(), as the alternative is an infinite loop that >>> consumes more and more memory. >>> >>> ## Impact on existing code >>> >>> None >>> >>> -Kevin Ballard >>> _______________________________________________ >>> swift-evolution mailing list >>> swift-evolution@swift.org >>> https://lists.swift.org/mailman/listinfo/swift-evolution >> >> _______________________________________________ >> swift-evolution mailing list >> swift-evolution@swift.org <mailto:swift-evolution@swift.org> >> https://lists.swift.org/mailman/listinfo/swift-evolution >> <https://lists.swift.org/mailman/listinfo/swift-evolution> > _______________________________________________ > swift-evolution mailing list > swift-evolution@swift.org <mailto:swift-evolution@swift.org> > https://lists.swift.org/mailman/listinfo/swift-evolution > <https://lists.swift.org/mailman/listinfo/swift-evolution>
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution