# Flattening trees

This section is my own interpolation.  The depth-first section uses the
dft and dff functions, but doesn’t show how to derive them as folds.

We can define a depth-first 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 point-free }

      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


## Breadth-first traversal

BFT “goes against the grain” because it is not compositional: we can’t
define traversing a forest in terms of traversing its trees.

## Level-order traversal

“The level-order 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 level-lists.  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 breadth-first traversal in terms
of level-order 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)


## Level-order traversal as an unfold

We can also express levelt and levelf as list unfolds.

    levelf = unfoldL nil (mapL root) (concatL ∘ mapL kids)