haskell 折叠玫瑰树路径

Question

假设我们有一棵树...

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

那棵树有一些节点

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

以下函数将收集树中的路径。

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

像这样:

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

但是现在我们如何折叠这些路径呢？显然我们可以做到这一点。找到路径后会折叠。

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]

我能找到的最接近的是:

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]]

但我觉得应该有比下面更干净的东西

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

基本上我不知道如何使用以下签名编写foldTreePaths:

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

Answer 1

我认为这对于理解来说非常简单:

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]