Possible to make a specific parameterization into a subtype?

General Usage
,
1

In the master branch of DataStructures.jl, I have written new iteration methods for the three sorted containers, SortedSet, SortedDict, and SortedMultiDict. The main structure that defines an iteration is:

struct IterableObject{C <: SortedContainer,
                      R <: RangeTypes,
                      Kv <: KVIterTypes,
                      T <: TokenIterTypes,
                      D <: IterDirection}
    m::C
    r::R
end

(See: DataStructures.jl/sorted_container_iteration.jl at master · JuliaCollections/DataStructures.jl · GitHub) So a loop like:

for (st,k) in semitokens(Iterators.Reverse(keys(s)))
end

will compile into one of those objects. The five parameters are: C, the underlying container, R, whether the iteration is over the whole container or a range of it, Kv, whether the iteration is keys, values, or both, T, whether the iteration is also supposed to return tokens or semitokens, and D, whether the iteration is forward or reverse.

This new structure extends and cleans up previous code, but it falls short in one respect. The original plan for SortedDict was to make it, as much as possible, a plug-in replacement for Dict. However, the new iteration code fails one compatibility test:

julia> d = Dict(1=>"a", 2=>"b");

julia> k = keys(d)
KeySet for a Dict{Int64, String} with 2 entries. Keys:
  2
  1

julia> isa(k,AbstractSet)
true

julia> g = SortedDict(1=>"a", 2=>"b");

julia> k = keys(g)
DataStructures.IterableObject{SortedDict{Int64, String, Base.Order.ForwardOrdering}, DataStructures.EntireContainer, DataStructures.KeysIter, DataStructures.NoTokens, DataStructures.ForwardIter}(SortedDict(1 => "a", 2 => "b"), DataStructures.EntireContainer())

julia> isa(k,AbstractSet)
false

So my question is whether it is possible to declare that particular parameterized instances of IterableObject, namely, instances when C is a SortedDict, Kv is KeysIter, and T is NoTokens be a subtype of AbstractSet. The only solution that comes to mind requires a lot of special-casing.

2

I’m reviving my question from 2022 because nobody answered at the time, and maybe some new contributors will see a solution. The question is now more pressing because the master version of DataStructures.jl just became release 0.19, which has the issue. In case you don’t want to read my entire OP, the short version of my question is: for a parameterized type

struct A{B,C,D,E}
end

is it possible to declare that A{B,C,D,E} is a subtype of AbstractSet but only for particular choices of D and E?

3

That’s not possible. The type must be specified in one definition all at once, during which you can only give it 1 named supertype possibly parameterized by a subset of its type parameters (default to <: Any). I don’t know why exactly parametric types aren’t allowed to branch to different named supertypes, but it’d obviously make dispatch, type inference, and writing generics more complicated than it already is.

AFAIK, this isn’t a fundamental characteristic for keys(::Dict):

help?> keys(::Dict)
  keys(a::AbstractDict)

  Return an iterator over all keys in a dictionary.
  collect(keys(a)) returns an array of keys. When the keys
  are stored internally in a hash table, as is the case for
  Dict, the order in which they are returned may vary. But
  keys(a), values(a) and pairs(a) all iterate a and return
  the elements in the same order.
1 Like