## A third view on trees

A few recent posts have played with trees from two perspectives. The more commonly used I call "top-down", because the top-level structure is most immediately apparent. A top-down binary tree is either a leaf or a pair of such trees, and that pair can be accessed without wading through intervening structure. Much less commonly used are "bottom-up" trees. A bottom-up binary tree is either a leaf or a single such tree of pairs. In the non-leaf case, the pair structure of the tree elements is accessible by operations like mapping, folding, or scanning. The difference is between a pair of trees and a tree of pairs.

As an alternative to the top-down and bottom-up views on trees, I now want to examine a third view, which is a hybrid of the two. Instead of pairs of trees or trees of pairs, this hybrid view is of trees of trees, and more specifically of bottom-up trees of top-down trees. As we’ll see, these hybrid trees emerge naturally from the top-down and bottom-up views. A later post will show how this third view lends itself to an in-place (destructive) scan algorithm, suitable for execution on modern GPUs.

Edits:

• 2011-06-04: "Suppose we have a bottom-up tree of top-down trees, i.e., `t ∷ TB (TT a)`. Was backwards. (Thanks to Noah Easterly.)
• 2011-06-04: Notation: "`f ➶ n`" and "`f ➴ n`".

The post Parallel tree scanning by composition defines "top-down" and a "bottom-up" binary trees as follows (modulo type and constructor names):

``data TT a = LT a | BT { unBT ∷ Pair (TT a) } deriving Functordata TB a = LB a | BB { unBB ∷ TB (Pair a) } deriving Functor``

So, while a non-leaf `TT` (top-down tree) has a pair at the top (outside), a non-leaf `TB` (bottom-up tree) has pairs at the bottom (inside).

Combining these two observations leads to an interesting possibility. Suppose we have a bottom-up tree of top-down trees, i.e., `t ∷ TB (TT a)`. If `t` is not a leaf, then `t ≡ BB tt` where `tt` is a bottom-up tree whose leaves are pairs of top-down trees, i.e., `tt ∷ TB (Pair (TT a))`. Each of those leaves of type `Pair (TT a)` can be converted to type `TT a` (single tree), simply by applying the `BT` constructor. Moreover, this transformation is invertible. For convenience, define a type alias for hybrid trees:

``type TH a = TB (TT a)``

Then the two conversions:

``upT   ∷ TH a → TH aupT   = fmap BT ∘ unBBdownT ∷ TH a → TH adownT = BB ∘ fmap unBT``

Exercise: Prove `upT` and `downT` are inverses where defined.

Answer:

``  upT ∘ downT≡ fmap BT ∘ unBB ∘ BB ∘ fmap unBT≡ fmap BT ∘ fmap unBT≡ fmap (BT ∘ unBT)≡ fmap id≡ id  downT ∘ upT≡ BB ∘ fmap unBT ∘ fmap BT ∘ unBB≡ BB ∘ fmap (unBT ∘ BT) ∘ unBB≡ BB ∘ fmap id ∘ unBB≡ BB ∘ id ∘ unBB≡ BB ∘ unBB≡ id``

Consider a perfect binary leaf tree of depth $n$, i.e., an $n$-deep binary tree with each level full and data only at the leaves (where a leaf is depth $0$ tree.) We can view such a tree as top-down, or bottom-up, or as a hybrid.

Each of these three views is really $n+1$ views:

• Top-down: a depth $n$ tree, or a pair of depth $n-1$ trees, or a pair of pairs of depth $n-2$ trees, etc.
• Bottom-up: a depth $n$ tree, or a depth $n-1$ tree of pairs, or a depth $n-2$ tree of pairs of pairs, etc.
• Hybrid: a depth $n$ tree of depth $0$ trees, or a depth $n-1$ tree of depth $1$ trees, or, …, or a depth $0$ tree of depth $n$ trees.

In the hybrid case, counting from $0$ to $n$, the ${k}^{th}$ such view is a depth $n-k$ bottom-up tree whose elements (leaf values) are depth $k$ top-down trees. When $k=n$, we have a bottom-up tree whose leaves are all single-leaf trees, and when $k=0$, we have a single-leaf bottom-up tree containing a top-down tree. Imagine a horizontal line at depth $k$, dividing the bottom-up outer structure from the top-down inner structure. The `downT` function moves the dividing line downward, and the `upT` function moves the line upward. Both functions are partial.

### Generalizing

The role of `Pair` in the tree types above is simple and regular. We can abstract out this particular type constructor, generalizing to an arbitrary functor. I’ll call this generalization "functor trees". Again, there are top-down and bottom-up versions:

``data FT f a = FLT a | FBT { unFBT ∷ f (FT f a) } deriving Functordata FB f a = FLB a | FBB { unFBB ∷ FB f (f a) } deriving Functor``

And a hybrid version, with generalized versions of `upT` and `downT`:

``type FH f a = FB f (FT f a)upH   ∷ Functor f ⇒ FH f a → FH f aupH   = fmap FBT ∘ unFBBdownH ∷ Functor f ⇒ FH f a → FH f adownH = FBB ∘ fmap unFBT``

These definitions specialize to the ones (for binary trees) by substituting `Pair` for the parameter `f`.

### Depth-typing

The upward and downward view-changing functions above are partial, as they can fail at extreme tree views (at depth $0$ or $n$). We could make this partiality explicit by changing the result type to `Maybe (TH a)` for binary hybrid trees and to `Maybe (FH f a)` for the functor generalization. Alternatively, make the tree sizes explicit in the types, as in a few recent posts, including A trie for length-typed vectors. (In those posts, I used the terms "right-folded" and "left-folded" in place of "top-down" and "bottom-up", reflecting the right- or left-folding of functor composition. The "folded" terms led to some confusion, especially in the context of data type folds and scans.) In the depth-typed versions, "leaves" are zero-ary compositions, and "branches" are $\left(m+1\right)$-ary compositions for some $m$.

Top-down:

``data (➴) ∷ (* → *) → * → (* → *) where  ZeroT ∷ a → (f ➴ Z) a  SuccT ∷ IsNat n ⇒ f ((f ➴ n) a) → (f ➴ S n) aunZeroT ∷ (f ➴ Z) a → aunZeroT (ZeroT a) = aunSuccT ∷ (f ➴ S n) a → f ((f ➴ n) a)unSuccT (SuccT fsa) = fsainstance Functor f ⇒ Functor (f ➴ n) where  fmap h (ZeroT a)  = ZeroT (h a)  fmap h (SuccT fs) = SuccT ((fmap∘fmap) h fs)``

Bottom-up:

``data (➶) ∷ (* → *) → * → (* → *) where  ZeroB ∷ a → (f ➶ Z) a  SuccB ∷ IsNat n ⇒ (f ➶ n) (f a) → (f ➶ S n) aunZeroB ∷ (f ➶ Z) a → aunZeroB (ZeroB a) = aunSuccB ∷ (f ➶ S n) a → (f ➶ n) (f a)unSuccB (SuccB fsa) = fsainstance Functor f ⇒ Functor (f ➶ n) where  fmap h (ZeroB a)  = ZeroB (h a)  fmap h (SuccB fs) = SuccB ((fmap∘fmap) h fs)``

Hybrid:

``type H p q f a = (f ➶ p) ((f ➴ q) a)``

Upward and downward shift become total functions, and their types explicitly describe how the line shifts between $\left(p+1\right)/q$ and $p/\left(q+1\right)$:

``up   ∷ (Functor f, IsNat q) ⇒ H (S p) q f a → H p (S q) f aup   = fmap SuccT ∘ unSuccBdown ∷ (Functor f, IsNat p) ⇒ H p (S q) f a → H (S p) q f adown = SuccB ∘ fmap unSuccT``

### So what?

Why care about the multitude of views on trees?

• It’s pretty.
• A future post will show how these hybrid trees enable an elegant formulation of parallel scanning that lends itself to an in-place, GPU-friendly implementation.