# Reversing sequences

**URL:** <https://forums.swift.org/t/reversing-sequences/16874>\
**Category:** Using Swift\
**Created:** [October 10, 2018, 10:36pm UTC](https://forums.swift.org/t/reversing-sequences/16874 "2018-10-10T22:36:56Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [October 10, 2018, 10:36pm UTC](https://forums.swift.org/t/reversing-sequences/16874/1 "2018-10-10T22:36:56Z")

</div>

Continuing the discussion from [SE-0231 — Optional iteration](https://forums.swift.org/t/se-0231-optional-iteration/16737/203):

> [@SE-0231 — Optional iteration](https://forums.swift.org/t/se-0231-optional-iteration/16737/203):
>
> I get the ubiquitousness and usefulness of Array. But any Sequence can be easily converted to Array. Anyway I believe that's not the reason Sequence.reversed() can't return Self. One reason I can think of is some Sequences are not reversable, for example, lowerBound must be less that upperBound for Range so Range is irreversable as a Sequence. Is that the only reason though?

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.

---

<div class="post-metadata">

**Author:** ![Ling\_Wang](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ling_wang/32/2691_2.png) [@Ling\_Wang](https://forums.swift.org/u/Ling_Wang)\
**Post date:** [October 10, 2018, 10:52pm UTC](https://forums.swift.org/t/reversing-sequences/16874/2 "2018-10-10T22:52:39Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [October 11, 2018, 12:23am UTC](https://forums.swift.org/t/reversing-sequences/16874/3 "2018-10-11T00:23:00Z")

</div>

> [@Ling\_Wang](#):
>
> So reversed() can't be generically implemented is the only issue left?

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.

> [@Ling\_Wang](#):
>
> Yes, it makes stdlib more tedious to implement

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).

---

<div class="post-metadata">

**Author:** ![Ling\_Wang](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ling_wang/32/2691_2.png) [@Ling\_Wang](https://forums.swift.org/u/Ling_Wang)\
**Post date:** [October 11, 2018, 1:30am UTC](https://forums.swift.org/t/reversing-sequences/16874/4 "2018-10-11T01:30:55Z")

</div>

> [@ben-cohen](#):
>
> If `array.reversed()` returned `Self` , it would take linear time. But a reversed collection view can be returned in (very low) constant time.

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.

> [@ben-cohen](#):
>
> `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

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()`.

> [@ben-cohen](#):
>
> and because we want it to be available when writing an extension on collection (i.e. every collection must provide it, no exceptions).

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?

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [October 11, 2018, 1:46am UTC](https://forums.swift.org/t/reversing-sequences/16874/5 "2018-10-11T01:46:42Z")

</div>

> [@Ling\_Wang](#):
>
> But `Array.reversed()` is an overload not an implementation of `Sequence.reversed()`

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?

> [@Ling\_Wang](#):
>
> 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?

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:

```swift
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.

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [October 11, 2018, 1:49am UTC](https://forums.swift.org/t/reversing-sequences/16874/6 "2018-10-11T01:49:03Z")

</div>

> [@ben-cohen](#):
>
> "making `Sequence.reversed()` return `Self` "

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.

---

<div class="post-metadata">

**Author:** ![Nobody1707](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nobody1707/32/2169_2.png) [@Nobody1707](https://forums.swift.org/u/Nobody1707)\
**Post date:** [October 11, 2018, 2:22am UTC](https://forums.swift.org/t/reversing-sequences/16874/7 "2018-10-11T02:22:31Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [October 11, 2018, 2:33am UTC](https://forums.swift.org/t/reversing-sequences/16874/8 "2018-10-11T02:33:39Z")

</div>

> [@Nobody1707](#):
>
> Having said that, it think having `Sequence.reversed(_:)` be a required method that returns an `opaque Sequence where _.Element == Element` might have been nice.

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.

---

<div class="post-metadata">

**Author:** ![Ling\_Wang](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ling_wang/32/2691_2.png) [@Ling\_Wang](https://forums.swift.org/u/Ling_Wang)\
**Post date:** [October 11, 2018, 2:36am UTC](https://forums.swift.org/t/reversing-sequences/16874/9 "2018-10-11T02:36:28Z")

</div>

> [@ben-cohen](#):
>
> 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?

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 😛.

> [@ben-cohen](#):
>
> If it wasn't defined as en extension on `Sequence` , but instead defined concretely on various types,

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?

---

<div class="post-metadata">

**Author:** ![Nobody1707](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nobody1707/32/2169_2.png) [@Nobody1707](https://forums.swift.org/u/Nobody1707)\
**Post date:** [October 11, 2018, 2:38am UTC](https://forums.swift.org/t/reversing-sequences/16874/10 "2018-10-11T02:38:41Z")

</div>

Yeah, that makes sense.

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [October 11, 2018, 2:40am UTC](https://forums.swift.org/t/reversing-sequences/16874/11 "2018-10-11T02:40:50Z")

</div>

> [@Ling\_Wang](#):
>
> Do you mean `Sequence` doesn't have API like `append` ?

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?

> [@Ling\_Wang](#):
>
> Because we are sure that dynamic dispatch is not needed since `reversed() -> [Element]` can be implemented well enough in protocol extension?

Yes, exactly. There are no realistic opportunities for improving on it on a type-by-type basis.

---

<div class="post-metadata">

**Author:** ![Ling\_Wang](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ling_wang/32/2691_2.png) [@Ling\_Wang](https://forums.swift.org/u/Ling_Wang)\
**Post date:** [October 11, 2018, 3:02am UTC](https://forums.swift.org/t/reversing-sequences/16874/13 "2018-10-11T03:02:21Z")

</div>

> [@ben-cohen](#):
>
> 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.

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?
