Why are self-referential struct parameters impossible?

Internals & Design
, , ,
13

No, my tone is just “I’m not gonna write a whole essay here.” I figured a quick response would be more useful than nothing at all. Brevity is a virtue, both for the writer and the reader.

So fundamentally, the constraint is what @Benny already mentioned and linked to above — that we don’t have forward declarations for types. But because you’re dealing with subtyping within the parameters, you just need to have an abstract type to reference. This works (but only for perfectly balanced trees):

julia> abstract type AbstractTree; end;

julia> struct Tree{V,T<:Union{AbstractTree,Nothing}} <: AbstractTree
           value::V
           left::T
           right::T
       end

julia> Tree(1, Tree(2, nothing, nothing), Tree(3, nothing, nothing))
Tree{Int64, Tree{Int64, Nothing}}(1, Tree{Int64, Nothing}(2, nothing, nothing), Tree{Int64, Nothing}(3, nothing, nothing))

You can fix that, of course, either by using two different parameters for the two leafs or with a custom constructor as you’ve already discovered. The default constructors try to get a concrete type because that’s generally what you want and is best for performance.

But note that the structure of the tree is reflected both in its type and in its data. We’re not talking about trouble with recursive data, but rather you’re seeking to put the exact structure of that information into the type domain. And that’s where you need to consider the tradeoffs on values vs. types.

3 Likes