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

**URL:** <https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080>\
**Category:** General Usage\
**Tags:** question\
**Created:** [March 25, 2024, 11:20am UTC](https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080 "2024-03-25T11:20:20Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![HenriDeh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrideh/32/8316_2.png) [@HenriDeh](https://discourse.julialang.org/u/HenriDeh)\
**Post date:** [March 25, 2024, 11:20am UTC](https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080/1 "2024-03-25T11:20:20Z")

</div>

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

```julia
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.

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [March 25, 2024, 11:35am UTC](https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080/2 "2024-03-25T11:35:44Z")

</div>

I don’t understand what your problem is here:

```julia-repl
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.

---

<div class="post-metadata">

**Author:** ![HenriDeh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrideh/32/8316_2.png) [@HenriDeh](https://discourse.julialang.org/u/HenriDeh)\
**Post date:** [March 25, 2024, 11:43am UTC](https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080/3 "2024-03-25T11:43:52Z")

</div>

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](https://aka.ms/AAb9ysg)

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [March 25, 2024, 11:55am UTC](https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080/4 "2024-03-25T11:55:53Z")

</div>

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-repl
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))

```

> [@HenriDeh](#):
>
> The compile times you mention are my problem

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.

---

<div class="post-metadata">

**Author:** ![HenriDeh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrideh/32/8316_2.png) [@HenriDeh](https://discourse.julialang.org/u/HenriDeh)\
**Post date:** [March 25, 2024, 12:10pm UTC](https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080/5 "2024-03-25T12:10:28Z")

</div>

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](https://docs.julialang.org/en/v1/manual/constructors/#Incomplete-Initialization)) but I can’t figure it out for parametric types.

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

Thanks.

---

<div class="post-metadata">

**Author:** ![abraemer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abraemer/32/51403_2.png) [@abraemer](https://discourse.julialang.org/u/abraemer)\
**Post date:** [March 25, 2024, 12:18pm UTC](https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080/6 "2024-03-25T12:18:29Z")

</div>

> [@HenriDeh](#):
>
> You can do self-referencial types if they are non-parametric ([Constructors · The Julia Language](https://docs.julialang.org/en/v1/manual/constructors/#Incomplete-Initialization)) but I can’t figure it out for parametric types.
> 
> But if it’s impossible then I’ll find another way.

This is indeed not possible:

> [@Mutually recursive type](https://discourse.julialang.org/t/mutually-recursive-type/25536):
>
> struct A b::B end struct B a::A end how to do this?

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.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 25, 2024, 1:03pm UTC](https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080/7 "2024-03-25T13:03:19Z")

</div>

> [@HenriDeh](#):
>
> I’m trying to build two tree node types that keep track of a set of instances of each other.

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

- [Tree structure with parametric type - #2 by rdeits](https://discourse.julialang.org/t/tree-structure-with-parametric-type/9300/2)
- [Why are self-referential struct parameters impossible? - #2 by stevengj](https://discourse.julialang.org/t/why-are-self-referential-struct-parameters-impossible/110982/2)

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [March 25, 2024, 4:25pm UTC](https://discourse.julialang.org/t/i-dont-understand-how-to-do-self-referencial-parametric-typing/112080/8 "2024-03-25T16:25:48Z")

</div>

> [@HenriDeh](#):
>
> I’m trying to build two tree node types that keep track of a set of instances of each other.

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`](https://github.com/JuliaCollections/DataStructures.jl/blob/77692eaf9fedafdefbfa1c135bea4886ca11f984/src/list.jl). But it is not necessarily the ideal solution in Julia for most problems, compared to eg Common Lisp.