Higher order generics are useful to write very generic libraries over container data structures.
In Julia such a type would look like C1{C2{T}} with C1 & C2 container types (Arrays,Lists,…) for a second order type. There could be even more abstract n-order types.
If we ignore very theoretical languages like Agda,Idris,Coq, the only languages that have this - that I know of - are Haskell & Scala. Both are very powerful languages. I think Julia could benefit from such a feature as well.
I wonder if this point has been discussed already in the past and dismissed or that this might be considered in the future.
You can already dispatch on types like Vector{Vector{T}}. To dispatch on T{T2{T3}} where T<:AbstractVector … is called triangular dispatch. This will be in v0.6 due to this PR:
Hey Chris,
Thanks for the reply. So gathering from your reply there will a form of second order generics in 0.6 but less general than what one has in Haskell/Scala (but still very powerfull!).
This is great news.
Well I actually said “less general” but ok. Maybe I misinterpreted the reply of Chris but I took it as meaning
T{T2{T3}} where T,T2 are subtypes of AbstractVector and in that case it’s less general than Haskell where T & T2 do not have to have a common ancestor. But reading it again now I see he only said T <: AbstractVector so maybe I misunderstood.
See the whole PR. You can where T <: AbstractVector where T2 <: Foo .... I am not familiar with it in detail because I haven’t used it yet, but I know that there is not a restriction here in “where you can where”.
Rather than ask such general and imprecise questions, it would be more useful if you gave a specific example that you have tried in another language and are unable to do in Julia.
I don’t understand why you’re giving me grief about this. This is a perfectly valid specific question about a general feature of a programming language. Not every question has to be “how do I do code this specific case”. There are also valid more general questions.
I think it is a little bit hard to understand exactly what you’re asking, and it would be more clear if you could illustrate it with an example. Then you avoid talking past each other.
Personally I don’t understand your question, but I would be interested to.
Stevens question was certainly not imprecise and I don’t see the issue here. Since the requested feature was just merged one week ago and I am pretty sure most users are not yet familiar with its syntax it may be indeed a good thing to compare our triangular dispatch mechanism with that of Haskell / Scala. Are they equivalent? Can we express things in a similar way?
Since the surface syntax is different (where) maybe there could be some documentation how to express similar meanings in Julia.
It actually took me quite a while to figure out the correct syntax to make it work, but here is an example:
julia> C2 where C2<:(AbstractVector{C1} where C1<:(Associative{K,V} where K<:Number where V<:AbstractString))
AbstractArray{C1,1} where C1<:(Associative{K,V} where K<:Number where V<:AbstractString)
That restricts C2 to be an AbstractVector container type, and C1 to be an Associative container type, and for the keys (K) to be some subtype of Numbers, and the values (V) to be of some subtype of AbstractString.
Some time ago I had similar thoughts, and I wrote up my findings here.
For example, one question is: if C1{T} and C2{T} are collections, can you define a new collection C1{C2{T}}? In Haskell, this would be something like Compose{C1,C2}{T}. I don’t think it’s easily possible in Julia, and it’s also not straightforward in C++.
With v0.6, it is easily possible (hurrah for Jeff and #18457!):
julia> MyT = C2 where C2<:(AbstractVector{C1} where C1<:(Associative{K,V} where K<:Number where V<:AbstractString))
AbstractArray{C1,1} where C1<:(Associative{K,V} where K<:Number where V<:AbstractString)
julia> typealias VecDictIntStr Vector{Dict{Int,String}}
Array{Dict{Int64,String},1}
julia> VecDictIntStr <: MyT
true
julia> c = push!(VecDictIntStr(), Dict(1=>"foo"), Dict(2=>"bar"))
2-element Array{Dict{Int64,String},1}:
Dict(1=>"foo")
Dict(2=>"bar")
julia> c isa MyT
true
Maybe you could post an updated version of your blog post (which I liked very much!) as v0.6 comes out?
typealias VV{T} Compose{Vector, Vector, T}
function f{T}(xs::VV{T})
@assert eltype(xs) === T # not Vector{T}
end
That is, I want to combine two collections (one inside the other) in such a way that it appears as a single collection. Currently, it is not possible to define Compose this way, since types cannot take type constructors (such as Vector) as arguments. Writing directly Vector{Vector{T}} also doesn’t work, since its elements have type Vector{T}, whereas I want to define a new, nested collection that has elements of type T.
I can, of course, define a new type VectorVector{T} directly (with respective iterators etc.). However, what I want to do is something more generic: I want to define a generic way (here called Compose) that takes any two collections and glues them together this way. And it turns out that Julia’s type system does not allow me to express this, at least not in an elegant or simple manner.
Ah, that’s interesting. How would you index into a VV{T}? Would you do x[row, col] or x[row][col]?
I’m still exploring what’s possible with the new type system, but you are saying that’s not possible even in v0.6?
I’m not saying that VV{T} should behave like an array; I’m looking for generic properties of collections here. For example, using a single iterator (a single for loop) would iterate over all elements. A reduction would reduce over all elements, etc. There are not too many operations that are generic enough to work with all collections, and it’s only those I want to support.
But if you want to treat it as array, then it would have a single index only. If a single array is like a String, then VV{T} would be like a Rope – an array that is broken into sub-arrays, e.g. to simplify inserting elements.