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

Question

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

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

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

Answer 1

我们可以生成一个生成二元组的函数，其中第一项是树的总和，第二项是 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。可能我们需要递归地计算子树的总和，并在节点中对它们求和，因此在这里使用二元组来存储到目前为止的总和结果更有效。

然后我们可以定义一个 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))