Just in terms of implementing trees, I would do something like:
abstract Node;
type Leaf <: Node
value::Float64;
end
type Branch <: Node
left::Node;
right::Node;
end
This should allow you to write methods that target either branch or leafs
accordingly:
function sum(node::Branch)
value::Float64 = 0;
value += !isEmpty(node.left) ? sum(node.left) : 0;
value += !isEmpty(node.right) ? sum(node.right) : 0;
end
function sum(node::Leaf)
return node.value;
end
On Tuesday, May 13, 2014 11:47:14 PM UTC-4, Abram Demski wrote:
>
> Hi all,
>
> I'm implementing BSP trees, and I've run into a style issue which I'm
> uncertain about.
>
> For my current purposes, the trees will be holding floats, but I wanted to
> write things in a way which allowed other possibilities later. At first, I
> made an explicit Leaf type:
>
> *Version 1*
>
>
> abstract Leaf
>
>
> type FloatLeaf <: Leaf
>
> value::Float64
>
> end
>
>
> abstract Split # abstract type for space partition
>
>
> # starting out with axis-aligned splits, to implement arbitrary-angle later.
>
> # Axis-aligned splits make rectangles, hence RectSplit
>
> type RectSplit <: Split
>
> var::Int
>
> loc::Float64
>
> end
>
>
> # internal tree node. Two sides of a split are pos and neg.
>
> type TreeNode
>
> split::Split # split definition
>
> pos::Union(TreeNode, Leaf) # negative side
>
> neg::Union(TreeNode, Leaf) # positive side
>
> end
>
>
> (This is actually a bit simplified; I also had a special Nothing type to
> indicate an empty case. The NA type from dataframes was not appropriate
> because I wanted different behavior.)
>
> I implemented functions on the trees mainly by using multi-dispatch in a
> pattern-matching style, matching against TreeNode or Leaf types to
> differentiate between the recursive case and the base case.
>
> I eventually decided that the Leaf type seemed rather pointless, because
> it was just a container for a value. Using a Leaf type created some
> annoyance with defining functions to operate on leaves, when the obvious
> thing to do was just apply those functions to the leaf values. Also, I was
> a little worried that putting stuff inside a Leaf container would be a
> small efficiency hit (probably not much?).
>
> End result, I modified to this:
>
> *Version 2*
>
> abstract Split
>
>
> type RectSplit <: Split
>
> var::Int
>
> loc::Float64
>
> end
>
>
> type TreeNode{a}
>
> split::Split # split definition
>
> pos::Union(TreeNode{a}, a) # negative side
>
> neg::Union(TreeNode{a}, a) # positive side
>
> end
>
>
> This is shorter, which seems like a good sign. It also manages to indicate
> that all leafs should have the same type, which the previous version
> didn't. However, I couldn't keep using multiple dispatch to define the
> different cases for my functions. The closest thing I could do would be to
> make the cases which match to Leaf type match to Float instead. This works
> when the tree is only holding floats, but I wanted to handle more general
> cases.
>
> Since this didn't seem right, I switched most of my code to use if-else in
> one function rather than multiple dispatch on the types. Leaving the leaf
> case for the final "else" allows me to write things in a generic way (no
> explicit assumption that I'm dealing with Floats in functions that don't
> need to interact with this assumption).
>
> However, this approach still doesn't work if I want to write a method
> which applies to trees (be they internal nodes or leaf nodes) but allows
> other function definitions for other types. Anything which isn't a TreeNode
> is now assumed to be a leaf, the way I've done it. This isn't actually a
> problem yet, but it could be at some point.
>
> Does this mean I was wrong to switch to the 2nd version?
>
> Any other suggestions for how this should go?
>
> Best,
>
> Abram
>
