如何在 Haskell 中合并两棵树

How to merge two trees in Haskell

假设我使用的树结构如下:

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

我将如何着手创建一个函数,该函数能够将在每个等效 node/leaf 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)) 

我们将不胜感激。

如果我们仔细考虑 merge_trees 的参数的不同组合,这真的很简单。

  • 一片叶子又一片叶子。
  • 左边是叶子,右边是节点。
  • 左边一个节点,右边一个叶子。
  • 左边一个节点,右边一个节点。

第一种情况非常简单。

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

第二种和第三种情况只需要我们将叶子的值加到节点的值上,return节点的其余部分不变

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