SortedDict construction tripped up by tuples and Any

[garborg]

julia> using DataStructures

julia> ks = ["a", "c", "b"]
3-element Array{String,1}:
 "a"
 "c"
 "b"

julia> vs = [1,2,3]
3-element Array{Int64,1}:
 1
 2
 3

julia> Dict(zip(ks,vs))
Dict{String,Int64} with 3 entries:
  "c" => 2
  "b" => 3
  "a" => 1

julia> SortedDict(zip(ks,vs))
ERROR: MethodError: no method matching sorteddict_with_eltype(::Base.Zip2{Array{String,1},Array{Int64,1}}, ::Type{Tuple{String,Int64}}, ::Base.Order.ForwardOrdering)

julia> Dict(k => counter(Int) for k in ks)
Dict{String,DataStructures.Accumulator{Int64,Int64}} with 3 entries:
  "c" => DataStructures.Accumulator{Int64,Int64}(Dict{Int64,Int64}())
  "b" => DataStructures.Accumulator{Int64,Int64}(Dict{Int64,Int64}())
  "a" => DataStructures.Accumulator{Int64,Int64}(Dict{Int64,Int64}())

julia> SortedDict(k => counter(Int) for k in ks)
ERROR: MethodError: no method matching sorteddict_with_eltype(::Base.Generator{Array{String,1},##21#22}, ::Type{Any}, ::Base.Order.ForwardOrdering)

julia> print(eltype(zip(ks, vs)))
Tuple{String,Int64}

julia> print(eltype(k => counter(Int) for k in ks))
Any

[garborg]

Here are a few more constructor issues to get them in one place:

#134

Raw pairs:

julia> using DataStructures

julia> Dict("a" => 1)
Dict{String,Int64} with 1 entry:
  "a" => 1

julia> SortedDict("a" => 1)
ERROR: MethodError: DataStructures.SortedDict{K,D,Ord<:Base.Order.Ordering}(::Pair{String,Int64}) is ambiguous. Candidates:
  (::Type{DataStructures.SortedDict}){K,D}(ps::Pair{K,D}...) at /Users/sean/.julia/v0.5/DataStructures/src/sorted_dict.jl:35
  (::Type{DataStructures.SortedDict})(kv) at /Users/sean/.julia/v0.5/DataStructures/src/sorted_dict.jl:57

[StephenVavasis]

Someone already reported a problem like this, but I can't find the issue or PR right now. A temporary workaround is to use SortedDict(Dict(...)) where the troublesome constructor arguments go into the inner parentheses. The permanent fix is to supply the missing constructors, but at the present time I'm a bit fuzzy on how all the constructors for plain Dict are used and interact with each other.

[kmsquire]

#168 adds a bunch of the needed constructors, and I updated it recently (did I push?). I forget now why I didn't ask for a review and merge. :-/ will try to take a look today.

[garborg]

Thanks Kevin. I saw it handled at least some of the constructors I mentioned.

[daniel-thom]

There is still a remaining issue where the constructor unexpectedly returns an eltype of Pair{Any,Any}. DataStructures v0.18.7

julia> SortedDict(i => i for i in 1:2)
SortedDict{Any,Any,Base.Order.ForwardOrdering} with 2 entries:
  1 => 1
  2 => 2

whereas with Dict:

julia> Dict(i => i for i in 1:2)
Dict{Int64,Int64} with 2 entries:
  2 => 2
  1 => 1

This is causing a minor problem that I can workaround by explicitly passing the types or by wrapping the contents with Dict or collect. Do you have any plans to address this? Thanks.

[oxinabox]

A PR to address it would be welcome.
It probably needs some digging.
I suspect it is something like
JuliaCollections/OrderedCollections.jl#53

[StephenVavasis]

I am the oriignal author of this code, but I do not know how to fix this. I'm not even sure it's possible without adding a lot of inefficient code. The basic issue is that generators do not return useful eltypes:

julia> eltype(i for i=1:2)
Any

So routines in Base like dict and collect use complicated logic to get around this. I believe that they expand the type as they pull in generator elements. Observe:

julia> a = Vector{Any}();
julia> push!(a,2);
julia> push!(a,3.3);
julia> a
2-element Array{Any,1}:
 2
 3.3
julia> collect(a[i] for i=1:1)
1-element Array{Int64,1}:
 2
julia> collect(a[i] for i=1:2)
2-element Array{Real,1}:
 2
 3.3

This kind of incremental type expansion would be difficult for SortedSet and SortedDict because the containers need to insert the elements on the fly using the sort-ordering, which is presumably linked to the type.

I suggest you use the simple workaround: SortedDict{Int,Int}(i=>i for i = 1:3)

[StephenVavasis]

Closed via #787