How to deal with recursive type dependencies in immutable structs?

Usage First steps
#1

I want to define structs with a parent-child relationship:

struct Parent
    children::Vector{Child}
end

struct Child
    parent::Parent
end

When I try to execute these definitions, I get:

ERROR: UnDefVarError: Child not defined

The following code, however, runs fine:

try
    struct Child
        parent::Parent
    end
catch
end

struct Parent
    children::Vector{Child}
end

struct Child
    parent::Parent
end

What is the right way to handle this? Can I somehow declare the types before I define them?

1 Like
#2

Here is the relevant issue: handle mutually-circular type declarations · Issue #269 · JuliaLang/julia · GitHub
Bottom line is that it is not resolved yet. The “accepted” solution is to use type-parameters (I think) handle mutually-circular type declarations · Issue #269 · JuliaLang/julia · GitHub

I haven’t come across your trick with try yet. It sure seems to work, the top example from 269 is:

julia> try 
           struct Foo
           a::Bar
           Foo() = new()
           Foo(a) = new(a)
       end
       catch
       end
       
    struct Bar
           b::Foo
           Bar() = new()
           Bar(b) = new(b)
    end

julia> struct Foo
           a::Bar
           Foo() = new()
           Foo(a) = new(a)
       end

julia> Foo(Bar(Foo()))
Foo(Bar(Foo(#undef)))
2 Likes
#3

I have used parametric types to solve this in the past:

struct Parent{T}
    children::Vector{T}
end

struct Child
    parent::Parent{Child}
end

p = Parent{Child}(Vector{Child}[])

push!(p.children, Child(p))
3 Likes
#4

Thanks! Weird gap in the language, though. It would be nice if something like this worked:

type Foo

struct Bar
    b::Foo
end

struct Foo
    b::Bar
end

I suppose you could do

macro type(t)
    quote
        try
            struct $t
                a::NotARealType
            end
        catch; end
    end
end
#5

It occurs to me that you could also define a single-child supertype, which I don’t think would affect performance:

abstract type SuperFoo
struct Bar
    b::SuperFoo
end

struct Foo <: SuperFoo
    b::Bar
end
1 Like
#6

Having a non-concrete field in a struct is indeed bad for performance. However, you could do

abstract type SuperFoo end
struct Bar{T <: SuperFoo}
    b::T
end

struct Foo <: SuperFoo
    b::Bar
end
2 Likes