Node utilities
Base
Various functions in Base
are overloaded to treat an AbstractNode
as a collection of its nodes.
Base.copy
— Methodcopy(tree::AbstractExpressionNode; break_sharing::Val=Val(false))
Copy a node, recursively copying all children nodes. This is more efficient than the built-in copy.
If break_sharing
is set to Val(true)
, sharing in a tree will be ignored.
Base.filter
— Methodfilter(f::Function, tree::AbstractNode; break_sharing::Val=Val(false))
Filter nodes of a tree, returning a flat array of the nodes for which the function returns true
.
Base.count
— Methodcount(f::F, tree::AbstractNode; init=0, break_sharing::Val{BS}=Val(false)) where {F<:Function,BS}
Count the number of nodes in a tree for which the function returns true
.
Base.foreach
— Methodforeach(f, c...) -> Nothing
Call function f
on each element of iterable c
. For multiple iterable arguments, f
is called elementwise, and iteration stops when any iterator is finished.
foreach
should be used instead of map
when the results of f
are not needed, for example in foreach(println, array)
.
Examples
julia> tri = 1:3:7; res = Int[];
julia> foreach(x -> push!(res, x^2), tri)
julia> res
3-element Vector{Int64}:
1
16
49
julia> foreach((x, y) -> println(x, " with ", y), tri, 'a':'z')
1 with a
4 with b
7 with c
foreach(f::Function, tree::AbstractNode; break_sharing::Val=Val(false))
Apply a function to each node in a tree without returning the results.
Base.sum
— Methodsum(f::Function, tree::AbstractNode; result_type=Undefined, f_on_shared=_default_shared_aggregation, break_sharing::Val{BS}=Val(false)) where {F<:Function,BS}
Sum the results of a function over a tree. For graphs with shared nodes such as GraphNode
, the function f_on_shared
is called on the result of each shared node. This is used to avoid double-counting shared nodes (default behavior).
Base.mapreduce
— Methodmapreduce(f::Function, op::Function, tree::AbstractNode; result_type, f_on_shared, break_sharing)
Map a function over a tree and aggregate the result using an operator op
.
Base.any
— Methodany(f::Function, tree::AbstractNode)
Reduce a flag function over a tree, returning true
if the function returns true
for any node. By using this instead of tree_mapreduce, we can take advantage of early exits.
Base.all
— Methodall(f::Function, tree::AbstractNode)
Reduce a flag function over a tree, returning true
if the function returns true
for all nodes, false
otherwise.
Base.map
— Methodmap(f::F, tree::AbstractNode, result_type::Type{RT}=Nothing; break_sharing::Val{BS}=Val(false)) where {F<:Function,RT,BS}
Map a function over a tree and return a flat array of the results in depth-first order. Pre-specifying the result_type
of the function can be used to avoid extra allocations.
Base.convert
— Methodconvert(::Type{<:AbstractExpressionNode{T1}}, n::AbstractExpressionNode{T2}) where {T1,T2}
Convert a AbstractExpressionNode{T2}
to a AbstractExpressionNode{T1}
. This will recursively convert all children nodes to AbstractExpressionNode{T1}
, using convert(T1, tree.val)
at constant nodes.
Arguments
::Type{AbstractExpressionNode{T1}}
: Type to convert to.tree::AbstractExpressionNode{T2}
: AbstractExpressionNode to convert.
Base.hash
— Methodhash(tree::AbstractExpressionNode{T}[, h::UInt]; break_sharing::Val=Val(false)) where {T}
Compute a hash of a tree. This will compute a hash differently if nodes are shared in a tree. This is ignored if break_sharing
is set to Val(true)
.
Printing
Trees are printed using the string_tree
function, which is very configurable:
DynamicExpressions.StringsModule.string_tree
— Methodstring_tree(
tree::AbstractExpressionNode{T},
operators::Union{AbstractOperatorEnum,Nothing}=nothing;
f_variable::F1=string_variable,
f_constant::F2=string_constant,
variable_names::Union{Array{String,1},Nothing}=nothing,
# Deprecated
varMap=nothing,
)::String where {T,F1<:Function,F2<:Function}
Convert an equation to a string.
Arguments
tree
: the tree to convert to a stringoperators
: the operators used to define the tree
Keyword Arguments
f_variable
: (optional) function to convert a variable to a string, with arguments(feature::UInt8, variable_names)
.f_constant
: (optional) function to convert a constant to a string, with arguments(val,)
variable_names::Union{Array{String, 1}, Nothing}=nothing
: (optional) what variables to print for each feature.
The standard show
and print
methods will use the most recently-created OperatorEnum
in a string_tree
.
Sampling
There are also methods for random sampling of nodes:
DynamicExpressions.RandomModule.NodeSampler
— TypeNodeSampler(; tree, filter::Function=Returns(true), weighting::Union{Nothing,Function}=nothing, break_sharing::Val=Val(false))
Defines a sampler of nodes in a tree.
Arguments
tree
: The tree to sample nodes from. For a regularNode
, nodes are sampled uniformly. For aGraphNode
, nodes are also sampled uniformly (e.g., insin(x) + {x}
, thex
has equal probability of being sampled from thesin
or the+
node, because it is shared), unlessbreak_sharing
is set toVal(true)
.filter::Function
: A function that takes a node and returns a boolean indicating whether the node should be sampled. Defaults toReturns(true)
.weighting::Union{Nothing,Function}
: A function that takes a node and returns a weight for the node, if it passes the filter, proportional to the probability of sampling the node. Ifnothing
, all nodes are sampled uniformly.break_sharing::Val
: IfVal(true)
, the sampler will break sharing in the tree, and sample nodes uniformly from the tree.
Base.rand
— Methodrand(rng::AbstractRNG, tree::AbstractNode)
Sample a node from a tree according to the default sampler NodeSampler(; tree)
.
Base.rand
— Methodrand(rng::AbstractRNG, sampler::NodeSampler)
Sample a node from a tree according to the sampler sampler
.
Internal utilities
Almost all node utilities are crafted using the tree_mapreduce
function, which evaluates a mapreduce over a tree-like (or graph-like) structure:
DynamicExpressions.NodeModule.tree_mapreduce
— Functiontree_mapreduce(
f::Function,
[f_branch::Function,]
op::Function,
tree::AbstractNode,
[result_type::Type=Undefined];
f_on_shared::Function=(result, is_shared) -> result,
break_sharing::Val=Val(false),
)
Map a function over a tree and aggregate the result using an operator op
. op
should be defined with inputs (parent, child...) ->
so that it can aggregate both unary and binary operators. op
will not be called for leafs of the tree. This differs from a normal mapreduce
in that it allows different treatment for parent nodes than children nodes. If this is not necessary, you may use the regular mapreduce
instead. The argument break_sharing
can be used to break connections in a GraphNode
.
You can also provide separate functions for leaf (variable/constant) nodes and branch (operator) nodes.
Examples
julia> operators = OperatorEnum(; binary_operators=[+, *]);
julia> tree = Node(; feature=1) + Node(; feature=2) * 3.2;
julia> tree_mapreduce(t -> 1, +, tree) # count nodes. (regular mapreduce also works)
5
julia> tree_mapreduce(t -> 1, (p, c...) -> p + max(c...), tree) # compute depth. regular mapreduce would fail!
5
julia> tree_mapreduce(vcat, tree) do t
t.degree == 2 ? [t.op] : UInt8[]
end # Get list of binary operators used. (regular mapreduce also works)
2-element Vector{UInt8}:
1
2
julia> tree_mapreduce(vcat, tree) do t
(t.degree == 0 && t.constant) ? [t.val] : Float64[]
end # Get list of constants. (regular mapreduce also works)
1-element Vector{Float64}:
3.2
Various other utility functions include the following:
DynamicExpressions.NodeModule.filter_map
— Functionfilter_map(filter_fnc::Function, map_fnc::Function, tree::AbstractNode, result_type::Type, break_sharing::Val=Val(false))
A faster equivalent to map(map_fnc, filter(filter_fnc, tree))
that avoids the intermediate allocation. However, using this requires specifying the result_type
of map_fnc
so the resultant array can be preallocated.
DynamicExpressions.NodeModule.filter_map!
— Functionfilter_map!(filter_fnc::Function, map_fnc::Function, stack::Vector{GT}, tree::AbstractNode)
Equivalent to filter_map
, but stores the results in a preallocated array.