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/iii/solution

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 , with output . 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], [].

New to topics? Read the docs here!