= Solution
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 $\boxed{\operatorname{dftF}=\operatorname{foldRTree}\bigl(\lambda x\ rs.\ x:\operatorname{concat}(rs)\bigr)}$. 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>.
Back to article page
