haskell - 给出一棵树，其中每个节点的值包含子节点的总和

试图弄清楚如何制作一棵树，其中每个节点的值都包含子节点的总和

data Tree a = LEAF a | NODE a  (Tree a)  (Tree a)
              deriving (Show, Read, Eq)

addNode:: Num a => Tree a -> Tree a
addNode(NODE x (LEAF a) (LEAF b)) = (NODE (a+b)  (LEAF a) (LEAF b))
addNode(NODE x left right) = (NODE x (addNode(left)) (addNode(right)))

tree1 = NODE 1
     (NODE 2 (NODE 3 (LEAF 4) (LEAF 5)) (LEAF 6))
     (NODE 7 (LEAF 8) (LEAF 9))

当我运行代码时，我得到:

addNode tree1
NODE 1 (NODE 2 (NODE 9 (LEAF 4) (LEAF 5)) *** Exception: testTree.hs:(105,1)-(106,89) Non-exhaustive patterns in function addNode

无法弄清楚是什么原因，非常感谢任何帮助

最佳答案

我们可以生成一个函数来生成一个二元组，其中第一项是树的总和，第二项是 Tree 本身:

addNode' :: Num a => Tree a -> (a, Tree a)
addNode' l@(LEAF x) = (x, l)
addNode' (NODE _ a b) = (sab, NODE sab ta tb)
    where (sa, ta) = addNode' a
          (sb, tb) = addNode' b
          sab = sa + sb

因此，我们应该同时考虑 LEAF 和 NODE。可能我们需要递归计算子树的总和，并在节点中将它们相加，因此在这里使用 2-tuple 来存储到目前为止的总和结果更有效。

然后我们可以定义一个 addNode 函数来解包 2 元组并只返回最后一个元素:

addNode :: Num a => Tree a -> Tree a
addNode = snd . addNode'

因此，这将产生一棵树，如:

Prelude> addNode tree1
NODE 32 (NODE 15 (NODE 9 (LEAF 4) (LEAF 5)) (LEAF 6)) (NODE 17 (LEAF 8) (LEAF 9))

关于haskell - 给出一棵树，其中每个节点的值包含子节点的总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58088102/