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 / c / Solution

For a rose tree, fold each child recursively, retaining their order, and supply the resulting list with the current label to the combining function:

foldRTree :: (a -> [b] -> b) -> RTree a -> b
foldRTree f (Node x ts) = f x (map (foldRTree f) ts)

The defining tree fold equation is $\boxed{\mathrm{foldRTree}f(\mathrm{Node}xts)=fx(\mathrm{map}(\mathrm{foldRTree}f)ts)}$. A leaf passes [] as the list of child results; an internal node passes one result per child. Thus the combining function controls both cases without a separate leaf constructor.