在 Haskell 中将值向上传播 Data.Tree

Question

使用 Data.Tree 我可以这样定义一棵树：

mkTree :: T.Tree Double
mkTree = T.Node 0 [ T.Node 4 []
                  , T.Node 0 [T.Node 5 [], T.Node 4 []]
                  , T.Node 0 [T.Node 2 [], T.Node 1 []]
                  ]

这将转移到这个：

0.0
|
+- 4.0
|
+- 0.0
|  |
|  +- 5.0
|  |
|  `- 4.0
|
`- 0.0
   |
   +- 2.0
   |
   `- 1.0

我现在想要转换树，以便每个 T.Node 现在包含其子项的总和（或其他一些函数）：

16.0
|
+- 4.0
|
+- 9.0
|  |
|  +- 5.0
|  |
|  `- 4.0
|
`- 3.0
   |
   +- 2.0
   |
   `- 1.0

问题是我无法使用 fmap 访问节点的子节点。到目前为止，我所拥有的是这些功能：

propagate :: Num a => T.Tree a -> T.Tree a
propagate (T.Node x []) = T.Node x []
propagate (T.Node _ ts) = T.Node (sum $ map gather ts) (map propagate ts)

gather :: Num a => T.Tree a -> a
gather (T.Node n []) = n
gather (T.Node _ ts) = sum $ map gather ts

但这似乎太复杂了，尤其是如果我要用另一个函数替换 sum。也许有更好的方法使用 Foldable 或 Traversable?

Answer 1

您希望为每个节点操作所有子树（包括节点标签），那么一个有用的函数可能是

subtrees :: Tree a -> Tree (Tree a)
subtrees n@(Node _ xs) = Node n (map subtrees xs)

现在，您可以将任何树函数应用于任何树中的树

sumSubtree :: Num a => Tree a -> Tree a
sumSubtree = fmap sum . subtrees

得到了想要的结果。

正如 Daniel 所说，sumSubtree 效率低下，因为从叶子到根的总和具有最优子结构。

但是，不存在唯一的解决方案，寻找下一个折叠版本

foldTree :: (a → Forest b → b) → Tree a → Tree b
foldTree f (Node x xs) = Node (f x xs') xs'
                         where xs' = foldTree f ↥ xs

现在仅当 f 不需要根和先前分支来计算某些分支值（例如求和问题）时才是最优的。但是（例如）如果在每个节点上都存储了一些密钥，这个总和实现也将是低效的。

(利用前面的折法，求和题可能写成foldTree (λx xs → ∑(x: map rootLabel xs)))

Answer 2

我认为 Foldable 没有公开足够的 Tree 结构来做你想做的事。 Traversable 可能，但要做到这一点似乎比较棘手；我想我更愿意实现这样的递归模式：

foldTree :: (a -> [b] -> b) -> Tree a -> b
foldTree f = go where
    go (Node value children) = f value (map go children)

然后你可以将你的求和操作实现为

sums :: Num a => Tree a -> Tree a
sums = foldTree (\val children -> Node (sum (val:map rootLabel children)) children)

甚至使用 sconcat 和 (:|) 代替 sum 和 (:).[=21 从 Num 推广到 Semigroup =]

在 Haskell 中将值向上传播 Data.Tree

Propagate values up a Data.Tree in Haskell

tree

haskell

functional-programming