Implementing `concat` using `foldTree` on Rose Tree I attempted (incorrectly) to implement foldTree here.

Recently, I updated it per Petr's help:

treeFold :: (b -&gt; [b] -&gt; b) -&gt; (a -&gt; b) -&gt; Tree a -&gt; b
treeFold f g tree = f (g (rootLabel tree)) (map (treeFold f g) (subForest tree))


I implemented toList:

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


Test

ghci&gt; stringTree
Node {rootLabel = "foo", 
      subForest = 
                [Node {rootLabel = "bar", subForest = []},
                 Node {rootLabel = "bippy", subForest = []},
                 Node {rootLForest = []}]}

ghci&gt; toList stringTree
["foo","bar","bippy","baz"]


I'm not sure if it's idiomatic to include the foldr call. Nor am I sure if I like the usage of ++. 

Please review this code.
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).