# Flattening trees
This section is my own interpolation. The depthfirst section uses the
dft and dff functions, but doesn’t show how to derive them as folds.
We can define a depthfirst flattening function by
dft ∷ Rose α → List α
dft (Node a ts) = Cons a (concatL (mapL dft ts))
where concatL is the familiar list fold:
concatL ∷ List (List α) → List α
concatL = foldL append Nil
We can calculate a foldR instance for dft, and an accompanying function
for Forests.
Using the universal property of foldR, we have
dft (Node a ts) = f a (foldF f g ts)
and reason as follows:
f a (foldF f g ts) = dft (Node a ts)
≡ { dft.1 }
f a (foldF f g ts) = Cons a (concatL (mapL dft ts))
If we can derive a solution for
concatL ∘ mapL dft = foldF f g (*)
with the induction hypothesis dft = foldR f g, we can take f = Cons.
So for (finite) ts ∷ Forest α:
foldF f g ts = concatL (mapL dft ts)
≡ { foldF.1 }
g (mapL (foldR f g) ts) = concatL (mapL dft ts)
≡ { hypothesis }
g (mapL dft ts) = concatL (mapL dft ts)
≡ { generalizing (mapL dft ts), rewrite pointfree }
g = concatL
So we can take f = Cons, which gives us the desired definition:
dft = foldR Cons concatL
Using this def. in (*) above, we have
foldF f g ts = concatL (mapL (foldR Cons concatL) ts)
and so
dff = foldF Cons concatL
### sumR
How about a function defined by
sumR ∷ Num α ⇒ Rose α → α
sumR = sum ∘ dft
where
sum ∷ Num α ⇒ List α → α
sum = foldL + 0
We seek a solution for f and g in the following:
sumR = foldR f g
Thinking in terms of foldR fusion, we have
sum (foldR Cons concatL) = foldR f g
holds if
(g ∘ mapL sum = sum ∘ concatL)
∧
(∀x (f x) ∘ sum = sum ∘ (Cons x))
The first equation is actually the canonical example of the ‘bookeeping
law’ (Bird, IFPH p. 132):
sum ∘ concatL = sum ∘ mapL sum
So we have g = sum.
We need to derive something for f.
(f x) ∘ sum = sum ∘ (Cons x)
It’s pretty clear what we’re going to get. But let’s calculate.
sum (Cons x xs) = foldL + 0 (Cons x xs)
= x + (foldL + 0 xs)
= (+ x) (sum xs)
so we have f = (+). We can now apply foldR fusion:
sumR = foldR + sum
## Unfolds for trees and forests
We have the following mutually recursive unfolds for rose trees:
unfoldR ∷ (β → α) → (β → List β) → β → Rose α
unfoldR f g x = Node (f x) (unfoldF f g x)
unfoldF ∷ (β → α) → (β → List β) → β → Forest α
unfoldF f g x = mapL (unfoldR f g) (g x)
It's interesting to note that g is likely an unfoldL instance.
Eliminators for convenience:
root ∷ Rose α → α
root (Node x _) = x
kids ∷ Rose α → Forest α
kids (Node _ ts) = ts
## Breadthfirst traversal
BFT “goes against the grain” because it is not compositional: we can’t
define traversing a forest in terms of traversing its trees.
## Levelorder traversal
“The levelorder traversal of a list is obtained by gluing together the
traversals of its trees.”
levelt ∷ Rose α → List (List α)
levelf ∷ Forest α → List (List α)
(levelt, levelf) = (foldR f g, foldF f g)
where
f x xss = Cons (wrap x) xss
g = foldL (lzw appendL) Nil
This gives us a list of levellists. e.g.
A
/  \
B C D ⇒ [[A], [B, C, D], [E, F, G], [H]]
  \
E F G

H
lzw (“long zip with”) is just a variant of zipWith:
lzw ∷ (α → α → α) → List α → List α → List α
lzw f Nil ys = ys
lzw f xs Nil = xs
lzw f (Cons x xs) (Cons y ys) = Cons (f x y) (lzw f xs ys)
It is straightforward to define a breadthfirst traversal in terms
of levelorder traversal:
bft ∷ Rose α → List α
bft = concatL ∘ levelt
bff ∷ Forest α → List α
bff = concatL ∘ levelf
We can eliminate the repeated list concatenations of levelt and
levelf by using accumulating parameters. The specifications are:
levelt' ∷ Rose α → List (List α) → List (List α)
levelt' t = lzw appendL (levelt t)
levelf' ∷ Forest α → List (List α) → List (List α)
levelf' ts = lzw appendL (levelf ts)
## Levelorder traversal as an unfold
We can also express levelt and levelf as list unfolds.
levelf = unfoldL nil (mapL root) (concatL ∘ mapL kids)