Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 3 / d

Emit the root label, then concatenate the depth-first traversals of the child rose trees in order:

dft :: RTree a -> [a]
dft (Node x ts) = x : concatMap dft ts

This is preorder traversal:

dft (Node x [t_{1}, \dots, t_{k}]) = [x] + + dft (t_{1}) + + \dots + + dft (t_{k}) .

(1)

The Haskell concatMap function preserves child order and finishes each child subtree before moving to the next. A leaf yields its singleton label; the source example yields [1,2,3,4,5,6,7].

Solution

 0  0

The child results supplied by the tree fold are already their depth-first traversals. Prepend the current label to their list concatenation:

dftF :: RTree a -> [a]
dftF = foldRTree visit
  where
    visit :: a -> [[a]] -> [a]
    visit x childLists = x : concat childLists

Thus

dftF = foldRTree (λ x rs . x : concat (rs))

. Substituting the equation for the tree fold gives exactly the recursive preorder traversal equation from part (i), proving equality by structural induction on a finite rose tree.

A list unfold needs an explicit state describing the unvisited work. Use a list of pending rose trees, with the next tree first. Emit that tree's root label, and replace it by its children followed by the remaining pending trees:

dftU :: RTree a -> [a]
dftU t = unfold null label advance [t]
  where
    label :: [RTree a] -> a
    label (Node x _ : _) = x

    advance :: [RTree a] -> [RTree a]
    advance (Node _ children : rest) = children ++ rest

The boxed state transition is

Node (x, c hi l d re n) : res t ⟼ c hi l d re n + + res t

, with output

x

. The stopping test prevents either helper from being applied to [].

The loop invariant is that concatenating the depth-first traversals of the pending trees gives exactly the unproduced output. Removing the next root emits its first label; replacing that tree by its children preserves the remainder of that preorder traversal. Adding children at the front realizes an explicit-stack depth-first tree traversal; placing them at the end would give a different visiting order. The first states for the source example have roots [1], [2,5,6], [3,4,5,6], [4,5,6], [5,6], [6], [7], [].