Implementing `concat` using `foldTree` on Rose Tree
edit: indeed, (++) will cause perfomance degradation on degenerate left-leaning trees. This is overcome with

-- toList = treeFold (\x y -&gt; x ++ (foldr (++) [] y)) (\x -&gt; [x])

toList t = treeFold (\x y -&gt; x . foldr (.) id y) (\x -&gt;([x]++)) t []


but that's equivalent to using the DL monoid mentioned in Petr Pudlák's answer.



Because foldr (++) [] y is just concat y, you can write it down as \x y -&gt; concat (x:y), or, pointfree,

-- treeFold :: (t -&gt; [b] -&gt; b) -&gt; (a -&gt; t) -&gt; Tree a -&gt; b

toList = treeFold ((concat .) . (:)) (: [])


but that's minor. Do take note that treeFold's inferred type is more general than what you specified.

Similarly, to sum the tree of numbers,

sumRoseTree = treeFold ((sum .) . (:)) id 


(or replace id with some other number-producing function, in cased the tree carries some other type).