 Solution

ID: 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/ii/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

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.

 New to topics? Read the docs here!