julia - Julia 中的多参数递归类型和类型推断

Question

我已经创建了这种数据结构

abstract type Node end

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

这种类型的结构让我可以方便地根据子节点的类型来寻址树的节点。

我可以举个例子

struct Character <: Node
    c::Char
end

并制定一个专门的方法来识别具有两个 Character child 的树

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

但我也可以定义一个类似的函数

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

它寻址一个 Tree，最左边的分支包含两个 Character 和一个任意的 Tree 在右边。

我的实现以类似的方式分派(dispatch)许多方法。

这种类型的结构有效，但对于相当大的树，我注意到一些速度变慢，尤其是在尝试使用 typeof 确定类型时。这种模式被认为是有效的吗？如果不是，有没有办法提高效率？

Answer 1

根据特定场景，可能会有很多关于树定义的提议。但是，您肯定希望避免导致性能不佳的递归嵌套类型结构。

这是我的建议。这个二叉树可以保存任何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))

现在让我们看看那棵树:

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