这个问题看起来非常类似于
为了回答这个问题,我将调整、纠正和详细说明那里给出的代码。
首先是一些定义:
abstract type BiTree{T} end
struct Branch{T} <: BiTree{T}
left::BiTree{T}
right::BiTree{T}
end
struct Leaf{T} <: BiTree{T}
value::T
end
Base.foldl(f, b::Branch) = f(foldl(f, b.left), foldl(f, b.right))
Base.foldl(f, l::Leaf) = f(l.value)
# fancy and concise constructor operations
(⊕)(l::Branch, r::Branch) = Branch(l, r) # just for illustration
(⊕)(l, r::Branch) = Branch(Leaf(l), r)
(⊕)(l::Branch, r) = Branch(l, Leaf(r))
(⊕)(l, r) = Branch(Leaf(l), Leaf(r))
这里我们有一个抽象类型和两个子类型,一种是树中内部节点的复合类型,另一种是叶子的子类型。我们还有两行递归操作来定义如何折叠或减少树中的值,以及一个简洁的树中缀构造函数。
如果我们定义my_tree
然后用加法折叠它,我们得到这个:
julia> my_tree = ((((6 ⊕ 7) ⊕ (6 ⊕ 7)) ⊕ ((7 ⊕ 7) ⊕ (0 ⊕ 7))) ⊕ (((8 ⊕ 7) ⊕ (7 ⊕ 7)) ⊕ ((8 ⊕ 8) ⊕ (8 ⊕ 0)))) ⊕ ((((2 ⊕ 4) ⊕ 7) ⊕ (6 ⊕ (0 ⊕ 5))) ⊕ (((6 ⊕ 8) ⊕ (2 ⊕ 8)) ⊕ ((2 ⊕ 1) ⊕ (4 ⊕ 5))));
julia> typeof(my_tree)
Branch{Int64}
julia> foldl(+, my_tree)
160
请注意,类型my_tree
完全暴露了它是一个带有某种子节点的内部节点,但我们无法真正看到它有多深。我们没有得到像这样的类型Branch{Branch{Leaf{Int32}, Branch{...
。事实是Branch{Int64}
is a BiTree{Int64}
可见使用
julia> isa(my_tree, BiTree{Int64})
true
但仅从价值上看不出来my_tree
单独的,并且深度在类型中不可见。
如果我们看看迄今为止作为我们工作的副作用生成的方法,我们会看到这一点
julia> using MethodAnalysis
julia> methodinstances(⊕)
4-element Vector{Core.MethodInstance}:
MethodInstance for ⊕(::Branch{Int64}, ::Branch{Int64})
MethodInstance for ⊕(::Int64, ::Branch{Int64})
MethodInstance for ⊕(::Branch{Int64}, ::Int64)
MethodInstance for ⊕(::Int64, ::Int64)
julia> methodinstances(foldl)
3-element Vector{Core.MethodInstance}:
MethodInstance for foldl(::typeof(+), ::Branch{Int64})
MethodInstance for foldl(::typeof(+), ::Leaf{Int64})
MethodInstance for foldl(::typeof(+), ::BiTree{Int64})
无论我们尝试构建哪种 32 位整数树,这就是我们所需要的。无论我们尝试减少什么树+
,这就是我们所需要的。
如果我们尝试使用不同的运算符进行折叠,我们可以获得更多方法
julia> foldl(max, my_tree)
8
julia> methodinstances(foldl)
6-element Vector{Core.MethodInstance}:
MethodInstance for foldl(::typeof(+), ::Branch{Int64})
MethodInstance for foldl(::typeof(max), ::Branch{Int64})
MethodInstance for foldl(::typeof(+), ::Leaf{Int64})
MethodInstance for foldl(::typeof(max), ::Leaf{Int64})
MethodInstance for foldl(::typeof(+), ::BiTree{Int64})
MethodInstance for foldl(::typeof(max), ::BiTree{Int64})
有趣的是,方法的数量增加了,但并没有爆炸。