如何合并Haskell中的两棵树

Question

假设我使用的是使用以下结构的树：

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

如何创建一个能够将每个等效节点/叶w/out中找到的值相加在一起的函数--导入任何库(将我留给Prelude库)，并且与

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

作为一个例子，假设输入是

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

那么输出应该是

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

任何和所有的帮助都将不胜感激。

Answer 1

如果我们仔细考虑merge_trees参数的不同组合，这是非常简单的。

• A叶和另一叶。
• A叶在左边，节点在右边。
• A节点在左边，叶子在右边。
• A节点在左边，节点在右边。

F 210

第一种情况很简单。

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

第二种和第三种情况只要求我们将叶的值添加到节点的值中，并将节点的其余部分不变地返回。

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

最后一种选择需要做的工作最多，但从根本上说是简单明了的。我们将两个节点的值相加，并使用该值构造一个新节点，并将merge_trees递归应用于两个节点的相应分支。

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))