Haskell 中的树合并算法

Question

我需要一个函数，它需要两棵树，检查是否有任何公共分支从树干上脱落，并在可能的情况下将这些树合并为一棵树。

如果 rootLabels 相等，则可以认为节点相同。不能合并具有不同根的两棵树。两棵同根树可以合并，递归检查它们的分支是否可以合并

任何人都可以建议通过 test1 和 test2 的函数 merge（下面）的实现（即函数 return True）吗？我确信有一个简单、优雅的解决方案，但目前它正在逃避我。或者，是否有我可以使用的现有库函数？

import Data.Tree

merge :: (Eq a) => Tree a -> Tree a -> Either (Tree a, Tree a) (Tree a)
merge = undefined

test1 :: Bool
test1 = 
    Node 'a' 
            [Node 'b' 
                [Node 'c' 
                    [], 
                Node 'g' 
                    []], 
            Node 'd' 
                []]
    `merge`
    Node 'a' 
            [Node 'b' 
                [Node 'c' 
                    [Node 'h'
                        []]], 
            Node 'e' 
                [Node 'f' 
                    []]]
    == 
    Right 
    (Node 'a' 
        [Node 'b' 
            [Node 'c' 
                [Node 'h'
                    []], 
            Node 'g' 
                []], 
        Node 'd' 
            [],
        Node 'e' 
            [Node 'f' 
                []]])

test2 :: Bool
test2 =  
    let l = Node 'a' []
        r = Node 'b' []
    in  l `merge` r == Left (l,r)

Answer 1

我想我终于明白了；

merge :: (Eq a) => Tree a -> Tree a -> Either (Tree a, Tree a) (Tree a)
merge l r = 
    if rootLabel l == rootLabel r
        then Right $ merge' l r 
        else Left (l,r)

merge' :: (Eq a) => Tree a -> Tree a -> Tree a
merge' l r = l { subForest = foldl mergeNode (subForest l) (subForest r) }

mergeNode :: Eq a => [Tree a] -> Tree a -> [Tree a]
mergeNode [] y = [y]
mergeNode (x:xs) y 
    | rootLabel x == rootLabel y = x `merge'` y : xs
    | otherwise = x : xs `mergeNode` y

Haskell 中的树合并算法

Tree merge algorithm in Haskell

algorithm

tree

haskell