如何在 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))