 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/i/solution

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

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

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].

 New to topics? Read the docs here!