Tree structure with parametric type

General Usage
2

Both are possible (and different), but neither is ideal, in my opinion. The issue with A{A}(...) is that A is a non-concrete type, so the outer layer will contain a Vector{A} whose elements are non-concrete. That may harm performance.

A{A{B}} does fix that particular issue, but it’s starting to feel like an abuse of the type system. You definitely can do this, but it means, for example, compiling new native code for every layer in the tree (because every layer is a different type).

In RegionTrees.jl I essentially make every node both and A and a B. That is, every node can contain data and/or a vector of children. I use Nullables to keep everything concretely typed, and it seems to work pretty well.

Another option would be to use a small Union:

struct A
  children::Vector{Union{A, B}}
end

struct B
  data::Vector{Float64}
end

In particular, this may end up performing better on Julia v0.7 (nightly) than on the current v0.6 release.

But, really, the most important thing is: there is no single answer to efficiency questions like this. The only way to know for sure what the right approach is is to benchmark it.

1 Like