haskell fold rose tree paths
fold, haskell, tree
Solution
I think this is pretty easy with comprehensions:
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]
Problem
let us say we have a tree... ``` data Tree a = Node a [Tree a] deriving (Show) ``` and that tree has some nodes ``` t = Node 1 [Node 2 [Node 3 []], Node 4 [], Node 5 [Node 6 []]] ``` the following function will `collect` the paths in a tree. ``` paths :: Tree a -> [[a]] paths (Node n []) = [[n]] paths (Node n ns) = map ((:) n . concat . paths) ns ``` like so: ``` *Main> paths t [[1,2,3],[1,4],[1,5,6]] ``` But now how could we `fold` these paths? Obviously we could do this. Which folds 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 I can some is: ``` 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 like there should be something cleaner than this below ``` *Main> foldTreePaths (\node base -> [node + sum base]) [0] a [[6],[5],[12]] ``` Basically I do not know how to write `foldTreePaths` with the following signature: `foldTreePaths :: (a -> b -> b) -> b -> Tree a -> [b]`