Adding `Self`-returning overload of `sorted()` for `OrderedDictionary` and `OrderedSet`?

[marcomasser]

There are mutating methods on OrderedDictionary and OrderedSet that sort them in-place, so sorting is well-defined on these types. But there are no copy-returning sorted() variants for these types.

The question is: Is there a specific reason why these are not included so far? I realize that adding this would be a source-breaking change for OrderedSet, so I guess the bar for including this is very high by now.

FYI, I asked on the Swift Forums about this (but I was confused a bit and didn’t see the Sequence.sorted() version): https://forums.swift.org/t/why-is-there-a-sort-but-no-sorted-method-on-ordereddictionary-and-orderedset/79978/2

---

A little more info:

OrderedSet uses the default implementation from Sequence, which returns an Array instead of an OrderedSet, which is unfortunate if you want to keep working with an OrderedSet:

let set: OrderedSet = [3, 2, 1]
print(type(of: set.sorted())) // Array<Int>

let sortedSet = OrderedSet(set.sorted()) // Possible, but not ideal 😕

And OrderedDictionary sees the default implementation from Sequence, but the compiler rightly errors out:

let dict: OrderedDictionary = [1: "one", 2: "two", 3: "three"]
print(type(of: dict.sorted())) // error: Type 'OrderedDictionary<Int, String>.Element' (aka '(key: Int, value: String)') cannot conform to 'Comparable'

Adding Self-returning variants and thereby shadowing the Sequence implementations is very easy, of course, e.g.:

extension OrderedSet {
    func sorted() -> Self where Element: Comparable {
        var copy = self
        copy.sort()
        return copy
    }
}

extension OrderedDictionary {
    func sorted() -> Self where Key: Comparable {
        var copy = self
        copy.sort()
        return copy
    }
}

…which results in this:

let dict: OrderedDictionary = [1: "one", 2: "two", 3: "three"]
print(type(of: dict.sorted())) // OrderedDictionary<Int, String>

let set: OrderedSet = [3, 2, 1]
print(type(of: set.sorted())) // OrderedSet<Int>

…which is what I personally would have expected 🙂

[lorentey]

This package is intended to hold precursors of future stdlib additions, so it tries its best not to violate the patterns of Standard Library. Early on, the stdlib project has decided that sorted()/map() and similar algorithms always return an Array, on every type; note that this was a deliberate choice, not an accident. I don't think this was a great choice, but I did not feel strongly enough for this package to start a movement for changing this convention for Sequence/Collection types.

As you say, this package has been shipping OrderedSet for a number of years now, and it would be source breaking for it to change the return value of OrderedSet.sorted(); it is not possible to do that. However, this change would be something to consider when/if we propose OrderedSet as a stdlib addition. I'll keep this issue open to remind us to consider this as a potential design tweak, if it ever comes to that.

Aside: I'm currently drafting noncopyable container protocols, including algorithms around them. That work gives us a new chance to come up with an alternative API designs that are specific to those protocols. It seems unlikely though that we'd have sorted/map/etc return Self there: I believe that the most likely outcome is that the equivalent algorithms on containers will take an explicitly configurable type (and/or result instance) to populate with the results, so that they provide more control over performance characteristics like allocation behavior. (Which is ultimately the reason we are working on these protocols.)

[lorentey]

Note that I see no clever insight that a custom sorted() implementation can apply to make it faster than your extension -- so if you really want a Self-returning variant, there are no performance drawbacks to defining it outside of this package.

OrderedSet(uncheckedUniqueElements: foo.sorted()) is another, more dangerous way of spelling the same, with pretty much the same characteristics.

[marcomasser]

Thank you for the historical context and all the other info! I suspected that the Array-returning variants on Sequence/Collection were a deliberate choice and I agree that this feels a bit unfortunate now – but this should be taken with a huge grain of salt since the people who made this decision are/were surely smarter and more informed than me 🙂

[xwu]

Early on, the stdlib project has decided that sorted()/map() and similar algorithms always return an Array, on every type; note that this was a deliberate choice, not an accident. I don't think this was a great choice, but I did not feel strongly enough for this package to start a movement for changing this convention for Sequence/Collection types.

I would surmise that the original design was chosen in large part for the same reason that filter would originally always return an Array, which is to say that a more sophisticated alternative design was not originally expressible without recursive requirements, etc.

However, in SE-0165, we made Dictionary.filter return a Dictionary and in SE-0174 we extended that possibility for all RangeReplaceableCollection types. Obviously, sorting never made sense to reconsider in the same way for Set and Dictionary since they are fundamentally unordered. However, I suspect that if we had had OrderedSet and OrderedDictionary in the stdlib at the time, Sequence.sorted could have been considered in parallel for the same treatment as filter.

Which is to say, now that we have the tools to express an associated type for sorted, it might make sense to do so for the replacement Container hierarchy and for conforming types as they're moved into the stdlib. I don't know that we should take the existing design decision as gospel without duly considering that it was made under different constraints.

[lorentey]

Which is to say, now that we have the tools to express an associated type for sorted, it might make sense to do so for the replacement Container hierarchy and for conforming types as they're moved into the stdlib. I don't know that we should take the existing design decision as gospel without duly considering that it was made under different constraints.

Great to hear we are on the same page on that.