Multiple parametric recursive types and type inference in Julia

user_9143142 0
Viewed 145

I have created a data structure of this sort

abstract type Node end

struct Tree{A <: Node, B <: Node} <: Node
    a::A
    b::B
end

This type of structure allows me to conveniently address nodes of a tree by the type of the children.

As an example I can have

struct Character <: Node
    c::Char
end

and make a specialized method that recognizes a tree with two Character children

function test(node::Tree{Character, Character}) end

But I could also potentially define a function like

function test(node::Tree{Tree{Character, Character}, Tree}) end

which address a Tree with the leftmost branch containing two Character and an arbitrary Tree on the right one.

My implementation dispatches many methods in a similar fashion.

This type of structure works, but for quite large trees I have noticed some slowdowns, especially when trying to determine the types using typeof. Is this pattern considered efficient? If not, is there a way to make it more efficient?

julia
1 Answers

There will be probably many proposals for tree definition depending on a particular scenario. However, for sure you want to avoid recursively nested type structure that leads to poor performance.

Here is my proposal. This binary tree can hold any data of type T

struct Tree{T}
    val::T
    a::Union{Tree{T}, Nothing}
    b::Union{Tree{T}, Nothing}
end

Tree(val::A) where A=Tree{A}(val,nothing,nothing)

leaf1 = Tree(4)
leaf2 = Tree(5)
subb1 = Tree(555,leaf1,leaf2)
tree = Tree(1000,subb1, Tree(888))

Now let us see that tree :

juila> dump(tree)
Tree{Int64}
  val: Int64 1000
  a: Tree{Int64}
    val: Int64 555
    a: Tree{Int64}
      val: Int64 4
      a: Nothing nothing
      b: Nothing nothing
    b: Tree{Int64}
      val: Int64 5
      a: Nothing nothing
      b: Nothing nothing
  b: Tree{Int64}
    val: Int64 888
    a: Nothing nothing
    b: Nothing nothing
user_99577100
Related