It's not just that some collections can't be reversed, though that's part of it.
The thing to bear in mind is that reversed() needs to be implemented both generically and as efficiently as possible. We don't want every single collection type to have to implement it itself by hand. And whenever possible, it would want to be able to return a reversed version in constant time. For bidirectional collections you can implement a generic efficient constant-time (almost "for free") reversal by returning a generic wrapper that just wraps Self and reverses the direction of iteration.
Many types are able to return Self from reversed, but not in constant time. Reversing a String into another String takes linear time. You could even write a generic linear-time reversed on any RangeReplaceableCollection. But putting String inside a ReversedCollection takes constant time.
And this cannot be done generically at all for unidirectional collections or sequences. Range could in theory reverse itself in constant time (assuming you wrote it to count down from a greater lower bound). But how would you express that capability generically, on what protocol? And how would you reverse UnfoldSequence generically? It can only really be done on a case-by-case basis.
TIL UnfoldSequence, it is indeed irreversible as a Sequence. I was actually thinking there should be a ReverableSequence protocol.
Let's ignore the irreversible ones first. So reversed() can't be generically implemented is the only issue left? If so I don't think that is a real issue to Swift users. Yes, it makes stdlib more tedious to implement, however whether "We don't want every single collection type to have to implement it itself by hand" or not should depend on the trade-offs. Does it make Swift a better language to most users?
If you mean, issues with reversed returning Self? In which case no, there is also the issue of efficiency. You want a collection to reverse itself as quickly as possible. If array.reversed() returned Self, it would take linear time. But a reversed collection view can be returned in (very low) constant time.
The reason to make the implementation of reversed generic is not to make life easy for standard library programmers.
The standard library defines both concrete collection types and protocols for collections. The protocols allow two things: you can write extensions on them that work on any collection. And you can write your own collections conforming to them that get all the features of collection extensions for free.
reversed must be generic, because we want anyone who writes their own collection type to get reversed for free, without having to write it themselves; and because we want it to be available when writing an extension on collection (i.e. every collection must provide it, no exceptions).
But Array.reversed() is an overload not an implementation of Sequence.reversed(). It can just keep its current efficient implementation. I don't understand how making Sequence.reversed() return Self would change that.
I'm not sure how many people write their own Sequence types but I believe not many of these sequences need to be reversible. So if there is a separate ReversibleSequence it should be OK because only reversible sequences need to implement reversed().
What's the consequence of missing default implementation when writing an extension on collection? It still compiles. Worse performance? Due to missing opportunity for inlining?
There is no Array.reversed(). There is only an extension on Sequence that returns an [Element], and an extension on BidirectionalCollection that returns ReversedCollection<Self>. You get the most specific overload by default, so reversing an array gives you the latter, but you can call the less-specific version via type context.
There is no meaning to the phrase "making Sequence.reversed() return Self". It's not something you could write. Sequence doesn't provide sufficient building blocks to make it possible as a default implementation. How would you implement it?
I'm not sure what you mean by "missing default implementation".
Currently, all implementations of Sequence get an implementation of reversed, because it's defined entirely in terms of capabilities Sequence has. This means that you can write, for example:
extension Sequence where Element: Equatable {
var isPalindrome: Bool {
// not the most efficient algorithm but hey
return self.elementsEqual(self.reversed())
}
}
To clarify your question: are you asking, what happens if a type doesn't implement reversed? It isn't possible. It is defined by definition on all sequences, because all it uses is iteration (and array construction).
If it wasn't defined as en extension on Sequence, but instead defined concretely on various types, then it would not be possible to write the above generic code. reversed just wouldn't be a method available on Sequence. Only on concrete types.
Alternatively, if what you mean is "Sequence should have a requirement that it provide a method, reversed that returns Self", then this would eliminate a large number of concrete types from implementing Sequence. This would not be a good thing.
For more on why ReversibleSequence probably isn't a good road to go down, I'd suggest watching Doug's discussion of this as part of the "Swift Generics" WWDC video this year.
Having said that, it think having Sequence.reversed(_:) be a required method that returns an opaque Sequence where _.Element == Element might have been nice. But I'm not sure that could be retrofitted in even if we had opaque types.
Tangentially related, in a world with opaque types, if a protocol requirement returned an opaque type could a type implementing that protocol publicly return a concrete type and have it get treated as opaque in a generic context, or would it have to be written as returning an opaque type?
What makes you think returning an opaque type would be better? It is very user friendly to return an array than to return an opaque type, and the only reasonable implementation of reversed() on non-bidirectional things involves filling up an array, so there's no good reason not to return one.*
* one small optimization would be to return a ReversedCollection<[Element]>, to avoid the final reversal of the result needed in the current implementation of reversed. But this would still be better than an opaque type, since unreversing it can return an array again.
Do you mean Sequence doesn't have API like append? I just realized that and I think it is the first and most important reason why Sequence.reverse can't return Self. If you pointed this out first I wouldn't have those questions .
I've never noticed that. I always thought reversed() is declared in Sequence protocol. Many of my points before are futile then. But why? What's the consideration for putting it outside the protocol? Because we are sure that dynamic dispatch is not needed since reversed() -> [Element] can be implemented well enough in protocol extension?
Right. That is defined much further up the hierarchy in RangeReplaceableCollection.
So RangeReplaceableCollection could define a version of reversed that returned Self. This would still be undesirable whenever the collection was bidirectional too. The number of realistic range replaceable forward-only collections is pretty few. Singly-linked lists and... that's it?
Yes, exactly. There are no realistic opportunities for improving on it on a type-by-type basis.
Was it talked in the video? I've actually already watched this one but don't have any memory about it. I just went through the PDF again but couldn't find the relevant information, also searched the transcript to no avail. Can you point me to the start point of that part in the video?
.