Conal Elliott

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 Functor

data 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 a
upT   = fmap BT ∘ unBB

downT ∷ TH a → TH a
downT = BB ∘ fmap unBT

  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 Functor

data 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 a
upH   = fmap FBT ∘ unFBB

downH ∷ Functor f ⇒ FH f a → FH f a
downH = 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 $(m+1)$-ary compositions for some $m$.

Top-down:

data (➴) ∷ (* → *) → * → (* → *) where
  ZeroT ∷ a → (f ➴ Z) a
  SuccT ∷ IsNat n ⇒ f ((f ➴ n) a) → (f ➴ S n) a

unZeroT ∷ (f ➴ Z) a → a
unZeroT (ZeroT a) = a

unSuccT ∷ (f ➴ S n) a → f ((f ➴ n) a)
unSuccT (SuccT fsa) = fsa

instance 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) a

unZeroB ∷ (f ➶ Z) a → a
unZeroB (ZeroB a) = a

unSuccB ∷ (f ➶ S n) a → (f ➶ n) (f a)
unSuccB (SuccB fsa) = fsa

instance 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 $(p+1)/q$ and $p/(q+1)$:

up   ∷ (Functor f, IsNat q) ⇒ H (S p) q f a → H p (S q) f a
up   = fmap SuccT ∘ unSuccB

down ∷ (Functor f, IsNat p) ⇒ H p (S q) f a → H (S p) q f a
down = 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.

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...