# Having a little trouble with recursively defined structs
**URL:** https://discourse.julialang.org/t/having-a-little-trouble-with-recursively-defined-structs/22285
**Category:** General Usage
**Created:** [March 24, 2019, 9:28pm UTC](https://discourse.julialang.org/t/having-a-little-trouble-with-recursively-defined-structs/22285 "2019-03-24T21:28:16Z")
**Posts on this page:** 7
**Page:** 1
### Author:  [@ninjaaron](https://discourse.julialang.org/u/ninjaaron)
#### Post date: [March 24, 2019, 9:28pm UTC](https://discourse.julialang.org/t/having-a-little-trouble-with-recursively-defined-structs/22285/1 "2019-03-24T21:28:16Z")
I’m trying to build something that looks like a linked list but ain’t. That isn’t really the important part. `InnerVector` optionally contains a `FakeList` and `FakeList` contains an `InnerVector`.
```julia
Opt = Union{T,Nothing} where T
struct InnerVector{T}
_tail::Opt{FakeList{T}}
_v::Vector{T}
end
struct FakeList{T}
_idx::UInt
_iv::InnerVector{T}
end
```
I know how to do this in C, but it didn’t work in Julia.
got this error:
```julia
julia> using FakeLists
[Info: Precompiling FakeLists [670117f4-4e66-11e9-3c80-85603a181f4e]
ERROR: LoadError: UndefVarError: FakeList not defined
[...]
```
I initially had an `AbstractFakeList` and that worked fine, but I took it out because I realized I didn’t need it, and now my code doesn’t compile. 😭
Did I need it, just not for the reasons I thought?
---
### Author:  [@bpr](https://discourse.julialang.org/u/bpr)
#### Post date: [March 24, 2019, 10:28pm UTC](https://discourse.julialang.org/t/having-a-little-trouble-with-recursively-defined-structs/22285/2 "2019-03-24T22:28:30Z")
I think you’re hitting this issue [handle mutually-circular type declarations · Issue #269 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/issues/269); you can see there for various workarounds.
---
### Author:  [@ninjaaron](https://discourse.julialang.org/u/ninjaaron)
#### Post date: [March 24, 2019, 11:08pm UTC](https://discourse.julialang.org/t/having-a-little-trouble-with-recursively-defined-structs/22285/3 "2019-03-24T23:08:08Z")
This seems to be a broken link. Edit: found it. the semicolon seems to be the problem
[https://github.com/JuliaLang/julia/issues/269](https://github.com/JuliaLang/julia/issues/269)
---
### Author:  [@bpr](https://discourse.julialang.org/u/bpr)
#### Post date: [March 25, 2019, 1:06am UTC](https://discourse.julialang.org/t/having-a-little-trouble-with-recursively-defined-structs/22285/4 "2019-03-25T01:06:15Z")
In Julia code I’ve written that has mutually recursive structs, I’ve broken the cycle by using an abstract type. Another way to do it is via type parameters, there’s an example here [https://github.com/JuliaLang/julia/issues/269#issuecomment-441446899](https://github.com/JuliaLang/julia/issues/269#issuecomment-441446899) and in a few other places.
It might be nice if this could be expressed more elegantly in Julia, but the workarounds are not bad.
---
### Author:  [@ninjaaron](https://discourse.julialang.org/u/ninjaaron)
#### Post date: [March 26, 2019, 5:01pm UTC](https://discourse.julialang.org/t/having-a-little-trouble-with-recursively-defined-structs/22285/5 "2019-03-26T17:01:23Z")
So, I got some code which compiles, but it seems it can’t be instantiated. I think this is something about a quirk with union types that I remember reading about, but I’m not sure what to do about it.
```julia
module FakeLists
export cons, list
const Opt = Union{Nothing,T} where T
abstract type AbstractFakeList{T} end
struct InnerVector{L<:Opt{<:AbstractFakeList},T}
_tail::L
_v::Vector{T}
end
struct FakeList{T} <: AbstractFakeList{T}
_idx::UInt
_iv::InnerVector{Opt{FakeList{T}},T}
end
FakeList(i, v, tail) = FakeList(UInt(i), InnerVector(tail, v))
# ...
end # module
```
So that all compiles fine, but:
```julia
julia> FakeLists.FakeList(0, FakeLists.InnerVector(nothing, Char[]))
ERROR: MethodError: no method matching FakeLists.FakeList(::Int64, ::FakeLists.InnerVector{Nothing,Char})
Closest candidates are:
FakeLists.FakeList(::Any, ::Any, ::Any) at /home/ninjaaron/src/julia/FakeLists/src/FakeLists.jl:19
Stacktrace:
[1] top-level scope at none:0
julia> FakeLists.FakeList(0, [], nothing)
ERROR: MethodError: no method matching FakeLists.FakeList(::UInt64, ::FakeLists.InnerVector{Nothing,Any})
Closest candidates are:
FakeLists.FakeList(::Any, ::Any, ::Any) at /home/ninjaaron/src/julia/FakeLists/src/FakeLists.jl:19
FakeLists.FakeList(::UInt64, ::FakeLists.InnerVector{Union{Nothing, FakeList{T}},T}) where T at /home/ninjaaron/src/julia/FakeLists/src/FakeLists.jl:15
Stacktrace:
[1] FakeLists.FakeList(::Int64, ::Array{Any,1}, ::Nothing) at /home/ninjaaron/src/julia/FakeLists/src/FakeLists.jl:19
[2] top-level scope at none:0
```
I don’t get it. I would have thought `InnerVector{Union{Nothing, FakeList{T}},T}) where T` would include `InnerVector{Nothing,Any}`, but it appears I am mistaken. Any suggestions?
---
### Author:  [@rdeits](https://discourse.julialang.org/u/rdeits)
#### Post date: [March 26, 2019, 5:25pm UTC](https://discourse.julialang.org/t/having-a-little-trouble-with-recursively-defined-structs/22285/6 "2019-03-26T17:25:29Z")
> [@ninjaaron](#):
>
> I would have thought `InnerVector{Union{Nothing, FakeList{T}},T}) where T` would include `InnerVector{Nothing,Any}`
Nope, for the same reason that `Vector{Int}` is not a subtype of `Vector{Integer}` nor of `Vector{Union{Int, Nothing}}` (i.e. Julia types are _invariant_).
I would suggest simplifying your design and moving the type checking into the inner constructor. Doing so has no performance cost, and it allows your code to be much simpler. For example, here are two mutually-recursive types :
```julia
julia> struct Foo{T}
x::Union{T, Nothing}
function Foo{T}(x = nothing) where {T}
T <: Bar || throw(ArgumentError("invalid type"))
new{T}(x)
end
end
julia> struct Bar{T}
x::Foo{Bar{T}}
end
julia> f = Foo{Bar{Int}}()
Foo{Bar{Int64}}(nothing)
julia> b = Bar(f)
Bar{Int64}(Foo{Bar{Int64}}(nothing))
```
---
### Author:  [@ninjaaron](https://discourse.julialang.org/u/ninjaaron)
#### Post date: [March 26, 2019, 5:39pm UTC](https://discourse.julialang.org/t/having-a-little-trouble-with-recursively-defined-structs/22285/7 "2019-03-26T17:39:22Z")
> [@rdeits](#):
>
> Nope, for the same reason that `Vector{Int}` is not a subtype of `Vector{Integer}` nor of `Vector{Union{Int, Nothing}}` (i.e. Julia types are _invariant_ ).
I think I need to read this part of the manual again… and then read it again every day until it sinks into my thick head…
Anyway, thanks for the suggestion about the inner constructor. I hadn’t thought about that, but it’s a great idea.