Arrays of abstract type in julia in functions

Question

I try to understand typing in Julia and encounter the following problem with Array. I wrote a function bloch_vector_2d(Array{Complex,2}); the detailed implementation is irrelevant. When calling, here is the complaint:

julia> bloch_vector_2d(rhoA)
ERROR: MethodError: no method matching bloch_vector_2d(::Array{Complex{Float64},2})
Closest candidates are:
  bloch_vector_2d(::Array{Complex,2}) at REPL[56]:2
  bloch_vector_2d(::StateAB) at REPL[54]:1
Stacktrace:
 [1] top-level scope at REPL[64]:1

The problem is that an array of parent type is not automatically a parent of an array of child type.

julia> Complex{Float64} <: Complex
true

julia> Array{Complex{Float64},2} <: Array{Complex,2}
false

I think it would make sense to impose in julia that Array{Complex{Float64},2} <: Array{Complex,2}. Or what is the right way to implement this in Julia? Any helps or comments are appreciated!

Answer 1

This issue is discussed in detail in the Julia Manual here.

Quoting the relevant part of it:

In other words, in the parlance of type theory, Julia's type parameters are invariant, rather than being covariant (or even contravariant). This is for practical reasons: while any instance of Point{Float64} may conceptually be like an instance of Point{Real} as well, the two types have different representations in memory:

• An instance of Point{Float64} can be represented compactly and efficiently as an immediate pair of 64-bit values;
• An instance of Point{Real} must be able to hold any pair of instances of Real. Since objects that are instances of Real can be of arbitrary size and structure, in practice an instance of Point{Real} must be represented as a pair of pointers to individually allocated Real objects.

Now going back to your question how to write a method signature then you have:

julia> Array{Complex{Float64},2} <: Array{<:Complex,2}
true

Note the difference:

• Array{<:Complex,2} represents a union of all types that are 2D arrays whose eltype is a subtype of Complex (i.e. no array will have this exact type).
• Array{Complex,2} is a type that an array can have and this type means that you can store Complex values in it that can have mixed parameter.

Here is an example:

julia> x = Complex[im 1im;
                   1.0im Float16(1)im]
2×2 Array{Complex,2}:
   im         0+1im
 0.0+1.0im  0.0+1.0im

julia> typeof.(x)
2×2 Array{DataType,2}:
 Complex{Bool}     Complex{Int64}
 Complex{Float64}  Complex{Float16}

Also note that the notation Array{<:Complex,2} is the same as writing Array{T,2} where T<:Complex (or more compactly Matrix{T} where T<:Complex).

Answer 2

This is more of a comment, but I can't hesitate posting it. This question apprars so often. I'll tell you why that phenomenon must arise.

A Bag{Apple} is a Bag{Fruit}, right? Because, when I have a JuicePress{Fruit}, I can give it a Bag{Apple} to make some juice, because Apples are Fruits.

But now we run into a problem: my fruit juice factory, in which I process different fruits, has a failure. I order a new JuicePress{Fruit}. Now, I unfortunately get delivered a replacement JuicePress{Lemon} -- but Lemons are Fruits, so surely a JuicePress{Lemon} is a JuicePress{Fruit}, right?

However, the next day, I feed apples to the new press, and the machine explodes. I hope you see why: JuicePress{Lemon} is not a JuicePress{Fruit}. On the contrary: a JuicePress{Fruit} is a JuicePress{Lemon} -- I can press lemons with a fruit-agnostic press! They could have sent me a JuicePress{Plant}, though, since Fruits are Plants.

Now we can get more abstract. The real reason is: function input arguments are contravariant, while function output arguments are covariant (in an idealized setting)². That is, when we have

f : A -> B

then I can pass in supertypes of A, and end up with subtypes of B. Hence, when we fix the first argument, the induced function

(Tree -> Apple) <: (Tree -> Fruit)

whenever Apple <: Fruit -- this is the covariant case, it preserves the direction of <:. But when we fix the second one,

(Fruit -> Juice) <: (Apple -> Juice)

whenever Fruit >: Apple -- this inverts the diretion of <:, and therefore is called contravariant.

This carries over to other parametric data types, since there, too, you usually have "output-like" parameters (as in the Bag), and "input-like" parameters (as with the JuicePress). There can also be parameters that behave like neither (e.g., when they occur in both fashions) -- these are then called invariant.

There are now two ways in which languages with parametric types solve this problem. The, in my opinion, more elegant one is to mark every parameter: no annotation means invariant, + means covariant, - means contravariant (this has technical reasons -- those parameters are said to occur in "positive" and "negative position"). So we had the Bag[+T <: Fruit], or the JuicePress[-T <: Fruit] (should be Scala syntax, but I haven't tried it). This makes subtyping more complicated, though.

The other route to go is what Julia does (and, BTW, Java): all types are invariant¹, but you can specify upper and lower unions at the call site. So you have to say

makejuice(::JoicePress{>:T}, ::Bag{<:T}) where {T}

And that's how we arrive at the other answers.

---

¹Except for tuples, but that's weird.

²This terminology comes from category theory. The Hom-functor is contravariant in the first, and covariant in the second argument. There's an intuitive realization of subtyping through the "forgetful" functor from the category Typ to the poset of Types under the <: relation. And the CT terminology in turn comes from tensors.