I don't understand how to do self-referencial parametric typing

General Usage
1

I’m trying to build two tree node types that keep track of a set of instances of each other.

FooNode{T, C <: Set}
    childs::C
    foo::T
end

BarNode{G, D <: Set}
   childs::D
   bar::G
end

T and G are other parametric types that we know at construct time. The constructor methods would thus be Foo(foo::T) and Bar(bar::G). After construction, the type of Foo should look like Foo{T, Set{Bar{G, Set{Foo{T, ...}}}}}.
I don’t understand how to make the inner constructors for these two functions. Specifically, I don’t understand how to make the new{...} call with the correct parameters because of the recursion.

2

I don’t understand what your problem is here:

julia> struct FooNode{T, C <: Set}
           childs::C
           foo::T
       end

julia> struct BarNode{G, D <: Set}
          childs::D
          bar::G
       end

julia> b1 = BarNode(Set(), 4)
BarNode{Int64, Set{Any}}(Set{Any}(), 4)

julia> FooNode(Set(b1=>4.0), 6)
FooNode{Int64, Set{Union{Float64, BarNode{Int64, Set{Any}}}}}(Set(Union{Float64, BarNode{Int64, Set{Any}}}[BarNode{Int64, Set{Any}}(Set{Any}(), 4), 4.0]), 6)

Just note that it likely is not a good idea to use such a complicated, nested type architecture since it might cause huge compile times. You should treat “putting information into the type domain” as a potential optimization that comes with drawbacks and needs to evaluated in a case-by-case basis. If you have already working code that you deem too slow and this is an attempt at optimization, then I’d recommend asking for help with your working code directly. If you develop something from scratch then I’d recommend taking a simpler approach since it is unclear whether the complex type shenanigans will pay off.

1 Like
3

The compile times you mention are my problem. What you show is full of Any and this is what I want to avoid.

Envoyé à partir de Outlook pour Android

4

The Any in my example stem from the fact that the inner most set is a Set{Any}. I can be whatever you want though:

julia> b1 = BarNode(Set([1,2,3]), nothing)
BarNode{Nothing, Set{Int64}}(Set([2, 3, 1]), nothing)

julia> FooNode(Set([3,4]), b1)
FooNode{BarNode{Nothing, Set{Int64}}, Set{Int64}}(Set([4, 3]), BarNode{Nothing, Set{Int64}}(Set([2, 3, 1]), nothing))

I thought writing the constructors is your problem as stated in the OP?

Maybe to directly answer the question from the title of the topic: You can’t make self-referential types.

I am confused. Please try to explain your problem again. Or maybe try explaining what you want to achieve, then we can think about how to do that.

1 Like
5

Sorry I was in a hurry when I wrote the OP. I’d like to write the constructor in a way that avoids the Any types. You can do self-referencial types if they are non-parametric (Constructors · The Julia Language) but I can’t figure it out for parametric types.

But if it’s impossible then I’ll find another way.

Thanks.

6

This is indeed not possible:

There are workarounds (e.g. abstract types and mutable structs) which you probably won’t like even though they are likely cheap from a runtime perspective.

7

Beware of trying to use parametric types like this for a tree, because then you are encoding the tree structure into the type — every distinct tree structure will have a distinct type, forcing the compiler to recompile/specialize code for every tree.

See also

7 Likes
8

I would suggest backing up a bit and describing what kind of data structure you would like to end up with: ie the typical operations and access patterns, and relevant type parameters for the data.

Generally you can avoid deeply nested recursive types by parametrizing the field indirectly. See eg DataStructures.LinkedList. But it is not necessarily the ideal solution in Julia for most problems, compared to eg Common Lisp.