sort(keys(Dict(:a => 1, :b => 2))) throws MethodError

General Usage
1

I guess this is rather a discussion:

sort(keys(Dict(:a => 1, :b => 2)))

throws the following MethodError

ERROR: MethodError: no method matching sort(::Base.KeySet{Symbol, Dict{Symbol, Int64}})
Closest candidates are:
  sort(::AbstractUnitRange) at range.jl:1379
  sort(::AbstractRange) at range.jl:1382
  sort(::SparseArrays.SparseVector{Tv, Ti}; kws...) where {Tv, Ti} at /nix/store/0fxg4zpsp5rbjfxn3hic1534rhagymmr-julia-1.8.5/share/julia/stdlib/v1.8/SparseArrays/src/sparsevector.jl:1994
  ...
Stacktrace:
 [1] top-level scope
   @ REPL[3]:1

For me this looks like a bug, but it is also quite surprising to find such a bug in julia 1.8
Hence maybe it is intended? Why should this be intended?

2

I guess the clue is in the name Key*Set*, sets don’t have an order. You can collect the keys into a plain vector for sorting.

1 Like
3

thank you, apparently also sort(Set([1,2,3])) fails

Still, semantically this is exactly why I call sort, isn’t it? I input something unordered and would like to have it ordered.

And you at least can iterate over a Set, hence why not calling sort on top of it? (neither is sort in place)

From performance perspective it is also not good to collect everything into an intermediate array which you just drop again.

4

You can do sort!.

1 Like
5

okay, so the workaround is sort!(collect(Set([1,2,3])))

probably this is still slower than directly constructing the vector in a sorted manner
and it looks very error-prone, like you really don’t want to see this in end-user code, something which should be put into another function like sortset(set) = sort!(collect(set)).

Hence again I would guess that there should be something for this in Base

6

What is wrong with:

Base.sort(s::AbstractSet) = sort!(collect(s))

?

7

I think this is called type piracy if you do it in your own code

If it would be part of Base that would work, but apparently it is not there

8

I found this related older issue I found this related discussion, which also does not have a good answer

where an alternative solution is to use PriorityQueue, but that of course does not make too much sense in this context where I want to sort the keys from a Dict

9

This is what I meant. I think this is very unambiguous when it appears in code, so it can easily be in Base. If any special data-structures have better ways to implement this, they can overload more specific AbstractSet implementations. I invite you to pull-request that on base/sort.jl

1 Like
10

That would indeed be an awesome first pullrequest to Julia, especially if others can be convinced that this makes indeed sense.

I probably will only have time in about a month, but I will keep this on my todo list

1 Like
11

How would that work? If you were implementing this, what container would you use as the intermediate while sorting? (Sets do not preserve order, so you can’t “reorder” them.) Or how would you implement a container-free sort? (sounds basically impossible for anything other than toy examples)

An alternative to implementing sort(::Set) would be to throw a more descriptive error. I agree that we should do one of these (either implement the method, or implement the error).

3 Likes
12

my intuition would say that

  1. first constructing the vector with collect and then sorting inplace with sort! could have some overhead compared to
  2. allocating an empty vector and then performing the sort on it given the values coming from the iterator of the set

but this is just my intuition, probably not worth the effort anyway, hence I really like the above solution

Base.sort(s::AbstractSet) = sort!(collect(s))
13

Just wanted to point out that Dictionaries.jl are ordered and support sorting, among other nice features.

2 Likes
14

I am not sure why you find this error prone, and it is a too small of a tidbit to be in a function in my opinion.

I think this is only relevant if you are doing this step for multiple Sets without keeping the sorted vector long-term (i.e., you can reuse the vector). Then the best is to:

julia> s = Set([1, 2, 3])
Set{Int64} with 3 elements:
  2
  3
  1

julia> array = Vector{Int}(undef, 3)
3-element Vector{Int64}:
 0
 0
 0

julia> array .= s
3-element Vector{Int64}:
 2
 3
 1

julia> sort!(array)
3-element Vector{Int64}:
 1
 2
 3

EDIT: But this also assumes the Sets are all of the same size, otherwise resize!(array, length(s)) is needed at each iteration.