Дайте дерево, в котором значение каждого узла содержит сумму дочерних узлов.

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

Мы можем сгенерировать функцию, которая генерирует 2-кортеж, где первый элемент является суммой дерева, а второй элемент, сам 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-кортеж, чтобы сохранить результат суммирования.

затеммы можем определить функцию 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))

Answer 2

Вы где так близко, вам просто нужен базовый случай, LEAF:

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

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

sumT :: Num a => Tree a -> a
sumT (LEAF a) = a
sumT (NODE _ left right) = (sumT left) + (sumT right)

t1 = NODE 1 t4 t3
t2 = NODE 3 (LEAF 4) (LEAF 5)
t3 = NODE 7 (LEAF 8) (LEAF 9)
t4 = NODE 2 t2 (LEAF 6)

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

$> addNode t1

NODE 32 (NODE 15 (NODE 9 (LEAF 4) (LEAF 5)) 
                 (LEAF 6))
        (NODE 17 (LEAF 8) (LEAF 9))

(В общем случае функция, которая работает с определенным типом - например, с деревом - должна соответствовать шаблону по каждому значениюконструктор этого типа, иначе Haskell будет вызывать ошибку неисчерпывающего совпадения с шаблоном)