Sortable iterators makes it harder to make non-breaking feature additions

[LilithHafner]

As @rfourquet pointed out here, sort(::Dict) produces a Vector of Pairs. This is because of #46104 which, incidentally, has gone through triage twice already. An OrderedDict could be a better result and changing that after 1.10 is release would be breaking. Specifically, if in 1.13 we decide to add OrderedDict to Base and switched sort(::Dict) to return an OrderedDict that would break push!(sort(d::Dict), p::Pair).

This can be fixed by making sort(::Dict) throw, but then we get to the question of libraries. Adding support for sorting an iterable into a custom type that is not the same as the type of collect(itr) will become a breaking change.

#46104 is in 1.10.

Questions for triage:

• Should we add another exception to make sort(::Dict) throw?
• In light of this API design issue which IIRC triage did not explicitly discuss previously, should we revert Support sorting iterators #46104, or let it permanently land?

[KristofferC]

I'm in favor of reverting it and require an explicit collect + sort! call.

[adienes]

what about documenting that sort(::SomeType) must return something iterable with matching eltype, but the exact container is implementation dependent? then Vector{Pair} --> OrderedDict is not breaking semver

[PallHaraldsson]

Specifically, if in 1.13 we decide to add OrderedDict to Base and switched sort(::Dict) to return an OrderedDict that would break push!(sort(d::Dict), p::Pair).

[It would be surprising to many to get a different type out?]

I tried to add OrderedDict to Base, instead of Dict. It wasn't successful, nor were people happy with having both.

Do we need AbstractSortedDict <: AbstractDict in Base, and change Dict to be the OrderedDefaultDict implementation(also for compatibility with Python)?

I would support that, for 1.11, even for 1.10... Why did you only mention 1.13 (not even 1.12)?

You could define only sort(::AbstractSortedDict).

What does Julia itself need for itself? None of these sorted iterator since done without so far? Nor sort defined for it, nor actually unsorted Dict, we have now, I'm not sure an ordered one would be slower, does it depend on size, and is the size ever expected to be very large? We could have UDict, even unexported, if it helps Julia, with the current implementation, but I'm not sure it helps much. It needs to be benchmarked, and could go into DataStructures.jl only under some name?

[Moelf]

#46104 (comment)

we can just add an error message to disable Dict if you want? this feels like throwing the baby out

[JeffBezanson]

Arguably with sort(::Any) we are repeating the mistake we made with map, which necessitated the ugly hack of defining map on a Dict to throw an error. A vector is not generally the right thing to return from sort or map of an arbitrary container, so arguably the generic method is just not correct.

[vtjnash]

Both sort and map share the property that the result must be something vector-like, as they must return ordered containers (and in the intermediate phase, the container must support fairly general mutation). Dict is a weird case for map because iterating 0 or 2+ items works fine, but is only an error for the exact case of 1 Dict. That seems someone separate from sort, which doesn't have the Vararg behaviors to worry about

[MasonProtter]

I wasn't aware of this, until today, but I just want to chime in to say I think this method is a major potential footgun, and we should be really cautious releasing v1.10 with it in.

I'd say at the very least this feature should be deferred until v1.11 so we have more time to think over the API consequences. Ref: #52010