Haskell folds rose trees paths

Question

let's say we have a tree ...

data Tree a = Node a [Tree a] deriving (Show)

and this tree has several nodes

t = Node 1 [Node 2 [Node 3 []], Node 4 [], Node 5 [Node 6 []]]

The next function will be the collectpaths in the tree.

paths :: Tree a -> [[a]]
paths (Node n []) = [[n]]
paths (Node n ns) = map ((:) n . concat . paths) ns

So:

*Main> paths t
[[1,2,3],[1,4],[1,5,6]]

But how could we go foldthese ways? Obviously, we could do that. Which bends after finding the paths.

wastefullFold :: (a -> b -> b) -> b -> Tree a -> [b]
wastefullFold f z (Node n ns) = map (foldr f z) $ paths (Node n ns)

*main> wastefullFold (+) 0 t
[6,5,12]

The closest may be:

foldTreePaths :: (a -> [b] -> [b]) -> [b] -> Tree a -> [[b]]
foldTreePaths f z (Node n []) = [f n z]
foldTreePaths f z (Node n ns) = map (f n . concat . foldTreePaths f z) ns

*Main> foldTreePaths (:) [] a
[1,2,3],[1,4],[1,5,6]]

*Main> foldTreePaths ((:) . (+ 1)) [] a
[[2,3,4],[2,5],[2,6,7]]

but I feel there must be something cleaner than this below

*Main> foldTreePaths (\node base -> [node + sum base]) [0] a
[[6],[5],[12]]

Basically I don't know how to write foldTreePathswith the following signature:

foldTreePaths :: (a -> b -> b) -> b -> Tree a -> [b]

Answer 1

I think this is pretty easy with the understanding:

foldRose f z (Node x []) = [f x z]
foldRose f z (Node x ns) = [f x y | n <- ns, y <- foldRose f z n]

> foldRose (:) [] t
[[1,2,3],[1,4],[1,5,6]]
> foldRose (+) 0 t
[6,5,12]