# Mutually recursive type

**URL:** <https://discourse.julialang.org/t/mutually-recursive-type/25536>\
**Category:** General Usage\
**Created:** [June 21, 2019, 6:55pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536 "2019-06-21T18:55:58Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![Freddy\_Chua](https://avatars.discourse-cdn.com/v4/letter/f/bc8723/32.png) [@Freddy\_Chua](https://discourse.julialang.org/u/Freddy_Chua)\
**Post date:** [June 21, 2019, 6:55pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/1 "2019-06-21T18:55:58Z")

</div>

struct A  
b::B  
end

struct B  
a::A  
end

how to do this?

---

<div class="post-metadata">

**Author:** ![ninjaaron](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ninjaaron/32/6392_2.png) [@ninjaaron](https://discourse.julialang.org/u/ninjaaron)\
**Post date:** [June 21, 2019, 7:13pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/2 "2019-06-21T19:13:57Z")

</div>

Hi Freddy and welcome!

fyi, [dependent type](https://en.wikipedia.org/wiki/Dependent_type) means something else. What you’re trying are usually called _mutually recursive types_.

an internal constructor is the normal method.

```julia
julia> struct A{T}
           b::T
           A(x) = new{B}(x)
       end

julia> struct B
           a::Union{A,Nothing}
       end

julia> A(B(A(B(nothing))))
A{B}(B(A{B}(B(nothing))))

```

This is kind of a workaround until Julia gets forward declarations or becomes aware of mutually recursive types.

But it works. Let us know if you want further explanation of this idiom.

---

<div class="post-metadata">

**Author:** ![Freddy\_Chua](https://avatars.discourse-cdn.com/v4/letter/f/bc8723/32.png) [@Freddy\_Chua](https://discourse.julialang.org/u/Freddy_Chua)\
**Post date:** [June 21, 2019, 8:14pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/3 "2019-06-21T20:14:31Z")

</div>

[https://github.com/JuliaLang/julia/issues/269](https://github.com/JuliaLang/julia/issues/269)

---

<div class="post-metadata">

**Author:** ![ninjaaron](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ninjaaron/32/6392_2.png) [@ninjaaron](https://discourse.julialang.org/u/ninjaaron)\
**Post date:** [June 21, 2019, 8:47pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/4 "2019-06-21T20:47:21Z")

</div>

Yes, it doesn’t work in this exact syntax. At the moment, you need a generic parameter and an internal constructor. It’s not ideal. Did my example not work for you? Do you need additional help? Give me a sign.

---

<div class="post-metadata">

**Author:** ![Freddy\_Chua](https://avatars.discourse-cdn.com/v4/letter/f/bc8723/32.png) [@Freddy\_Chua](https://discourse.julialang.org/u/Freddy_Chua)\
**Post date:** [June 21, 2019, 8:57pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/5 "2019-06-21T20:57:01Z")

</div>

[https://groups.google.com/forum/#!topic/julia-users/kVKUK3Hd6ok](https://groups.google.com/forum/#!topic/julia-users/kVKUK3Hd6ok)

it’s been 5 years! I asked the same thing.

---

<div class="post-metadata">

**Author:** ![ninjaaron](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ninjaaron/32/6392_2.png) [@ninjaaron](https://discourse.julialang.org/u/ninjaaron)\
**Post date:** [June 21, 2019, 9:07pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/6 "2019-06-21T21:07:23Z")

</div>

I see your conundrum. I can’t make the syntax you want materialize because I’m not a core dev. I can only tell you what different syntax accomplishes the same thing, and it’s in the example I posted.

My impression is that this is more of an ideological issue than about solving a real problem–which isn’t to say it’s not important. Julia should be smart enough to handle mutually recursive types automatically, but it is possible to do what you want, just not in the way you want to write it.

---

<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:** [June 22, 2019, 4:54am UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/7 "2019-06-22T04:54:59Z")

</div>

> [@Freddy\_Chua](#):
>
> it’s been 5 years! I asked the same thing.

Since you are presumably aware of the issue mentioned in that discussion and it is still open, it is not clear why you asked again.

---

<div class="post-metadata">

**Author:** ![pablosanjose](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pablosanjose/32/7006_2.png) [@pablosanjose](https://discourse.julialang.org/u/pablosanjose)\
**Post date:** [June 22, 2019, 11:00am UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/8 "2019-06-22T11:00:27Z")

</div>

A small off-topic comment, if I may.

There is a tension in open-source development that I see frequently. This thread is another instance of it. Some people tend to approach an open-source projects like one approaches the products of a private venture in a capitalist culture. They feel entitled to improvements, fast development, requested features… This of course causes some grief in developers, which don’t get payed for that work. I think it is very important to get people to understand the type of relation here. It is more like science than business. It’s important, I believe, to keep an attitude of respect and gratitude whenever offering criticism on an open-source project. It’s been 5 years, yes, probably for very good reasons. Probably because of the overwhelming weight carried by very few shoulders, while most of us stand aside watching and enjoying the result of their work. Usually, the work of open-source developers grows out of personal passion for the project. We don’t want to burn that passion down. Let them feel the love, please!

(End of rant.)

---

<div class="post-metadata">

**Author:** ![ninjaaron](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ninjaaron/32/6392_2.png) [@ninjaaron](https://discourse.julialang.org/u/ninjaaron)\
**Post date:** [June 22, 2019, 12:31pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/9 "2019-06-22T12:31:03Z")

</div>

Alternatively, pay Julia Computing to do the work. Then, it’s more like a business than a science. 😆

---

<div class="post-metadata">

**Author:** ![oheil](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oheil/32/220745_2.png) [@oheil](https://discourse.julialang.org/u/oheil)\
**Post date:** [June 22, 2019, 1:06pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/10 "2019-06-22T13:06:02Z")

</div>

If the forward declarations would be implemented, would this lead to longer compile times?

There are some “complaints” about the time it takes to the first plot already.

My naive thinking is, that forward declarations could double (or so) compile time therefor benefits and downsides must be balanced in this case.

---

<div class="post-metadata">

**Author:** ![ninjaaron](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ninjaaron/32/6392_2.png) [@ninjaaron](https://discourse.julialang.org/u/ninjaaron)\
**Post date:** [June 22, 2019, 5:48pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/11 "2019-06-22T17:48:17Z")

</div>

It definitely shouldn’t double compile-times, but it would probably add to them a little. _My_ naive thinking is that you’d only have to pay for it if you’re using it. i.e. if you use an undeclared symbol while declaring a struct, the compiler will have to tuck it away for later and use it then.

Alternatively, the compiler could just postpone evaluation of the struct bodies until they are actually required, or until all top-level symbols in the module/script have been declared.

It shouldn’t be too expensive, if my musings are correct.

---

<div class="post-metadata">

**Author:** ![pixel27](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pixel27/32/8902_2.png) [@pixel27](https://discourse.julialang.org/u/pixel27)\
**Post date:** [June 22, 2019, 8:24pm UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/12 "2019-06-22T20:24:41Z")

</div>

I would think that would lead to infinite memory utilization, i.e struct A needs space for struct B which needs space for struct A and on and on?

Wouldn’t both of them need to be mutable so they become objects on the heap rather than stack to even begin to work? Like:

```julia
mutable struct A
    foo::B
end

mutable struct B
    foo::A
end 

```

I did run into something where I kind of wanted two objects to reference each other but I ended up doing:

```julia
struct C
    foo::UInt
end

struct A
    common::C
end

struct B
    common::C
end 

```

Which worked in my case.

---

<div class="post-metadata">

**Author:** ![Gnimuc](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gnimuc/32/2194_2.png) [@Gnimuc](https://discourse.julialang.org/u/Gnimuc)\
**Post date:** [June 23, 2019, 2:34am UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/13 "2019-06-23T02:34:33Z")

</div>

This may be a little bit off-topic, but since the forward declaration is ubiquitously used in C, it’s a pain point when mapping such C struct to Julia. AFAIK, workarounds like `struct A{T}` cannot guarantee the underlying memory layout consistency between Julia and C.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [June 23, 2019, 4:02am UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/14 "2019-06-23T04:02:06Z")

</div>

No. Using a type parameter has nothing to do with the layout. It’s also not really a work around since it force you to explicitly introduce a break to the cycle. This does not matter much right now but if we ever going to allow non-pointerfree immutable types to be stored inline, such a property will be very important.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [June 23, 2019, 4:05am UTC](https://discourse.julialang.org/t/mutually-recursive-type/25536/15 "2019-06-23T04:05:07Z")

</div>

> [@pixel27](#):
>
> Wouldn’t both of them need to be mutable so they become objects on the heap rather than stack to even begin to work? Like:

no. mutability does not equal storage type of a field. At least one of `A` or `B` must not be stored inline but they could well be both immutable. That’s exactly why explicitly breaking the cycle is important if pointerfree-ness is uncoupled from field storage type since then the layout of the storage type will not depend on the type paramter