Having a little trouble with recursively defined structs

General Usage
1

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.

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> 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. :sob:

Did I need it, just not for the reasons I thought?

2

I think you’re hitting this issue handle mutually-circular type declarations · Issue #269 · JuliaLang/julia · GitHub; you can see there for various workarounds.

3

This seems to be a broken link. Edit: found it. the semicolon seems to be the problem

https://github.com/JuliaLang/julia/issues/269

4

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

1 Like
5

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.

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> 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?

6

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> 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))
2 Likes
7

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.