= 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 $\boxed{\operatorname{Node}(x,children):rest\ \longmapsto\ children\mathbin{++}rest}$, 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]`, `[]`.
Back to article page
