= 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{\operatorname{foldRTree}\ f\ (\operatorname{Node}\ x\ ts)=f\ x\ (\operatorname{map}(\operatorname{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.
Back to article page
