Implementing `concat` using `foldTree` on Rose Tree

I attempted (incorrectly) to implement foldTree here.

Recently, I updated it per Petr's help:

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

I implemented toList:

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

Test

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

ghci> 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 -> x ++ (foldr (++) [] y)) (\x -> [x])

toList t = treeFold (\x y -> x . foldr (.) id y) (\x ->([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 -> concat (x:y), or, pointfree,

-- treeFold :: (t -> [b] -> b) -> (a -> t) -> Tree a -> 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).

StackExchange Code Review Q#69798, answer score: 2