How to merge two trees in Haskell-CodePudding

Assuming I am using a tree structured using the following:

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

How would I go about creating a function capable of adding together the values found at each equivalent node/leaf w/out importing any libraries (leaving me with the Prelude library), and is compatible with

function :: Num a => Tree a -> Tree a -> Tree a

As an example, assume the input is

left = NODE 1 (NODE 2 (NODE 3 (LEAF 4) (LEAF 5)) (LEAF 6)) (NODE 7 (LEAF 8) (LEAF 9)) 
 
right = NODE 1 (NODE 2 (LEAF 3) (LEAF 6)) (NODE 7 (NODE 8 (LEAF 10) (LEAF 11)) (LEAF 9)) 

merge_trees left right

Then the output should be

NODE 2  
(NODE 4 (NODE 6 (LEAF 4) (LEAF 5)) (LEAF 12))  
(NODE 14 (NODE 16 (LEAF 10) (LEAF 11)) (LEAF 18))

Any and all help would be appreciated.

CodePudding user response：

This is really quite straightforward if we think through the different combinations of arguments to merge_trees.

A leaf and another leaf.
A leaf on the left and a node on the right.
A node on the left and a leaf on the right.
A node on the left and a node on the right.

The first case is very simple.

merge_trees (LEAF a) (LEAF b) = LEAF (a   b)

The second and third cases only require us to add the value of the leaf to the value of the node, and return the rest of the node unchanged.

merge_trees (LEAF a) (NODE b l r) = NODE (a   b) l r
merge_trees (NODE b l r) (LEAF a) = NODE (a   b) l r

The last option takes the most work but is fundamentally straightforward. We add the values of both nodes, and construct a new node with that value and the results of recursively applying merge_trees to the corresponding branches of both nodes.

merge_trees (NODE a l r) (NODE b l' r') = NODE v l'' r''
  where 
    v = a   b
    l'' = merge_trees l l'
    r'' = merge_trees r r'

Prelude> left = NODE 1 (NODE 2 (NODE 3 (LEAF 4) (LEAF 5)) (LEAF 6)) (NODE 7 (LEAF 8) (LEAF 9))
Prelude> right = NODE 1 (NODE 2 (LEAF 3) (LEAF 6)) (NODE 7 (NODE 8 (LEAF 10) (LEAF 11)) (LEAF 9))
Prelude> merge_trees left right
NODE 2 (NODE 4 (NODE 6 (LEAF 4) (LEAF 5)) (LEAF 12)) (NODE 14 (NODE 16 (LEAF 10) (LEAF 11)) (LEAF 18))