CODEWITHSUNDEEP
julia
MPaga
MPaga

Reputation: 329

Multiple parametric recursive types and type inference in Julia

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?

Upvotes: 3

Views: 260

Answers (1)

Przemyslaw Szufel
Przemyslaw Szufel

Reputation: 42214

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

Upvotes: 1

Related Questions