如何在Haskell中的树之间移动子树？

Question

对于两个多路树,t1和t2,定义使用

type Forest a = [Tree a]
data Tree a   = Node {
        rootLabel :: a,     
        subForest :: Forest a
    }

如何编写一个从t1中删除子树并将其插入t2中给定节点的函数？

我想象签名看起来像

moveSubTree :: ((Tree x a) x (Tree x a)) -> (Tree x Tree)

即,它需要一个树和父节点定义要删除的子树,以及第二个树和节点,它定义插入原始子树的点.

如有必要,可以组合要删除然后添加子树的单独函数.

Answer 1

您可以在树中进行"在路径上"的编辑和读取.

data Dir    = L | R
type Path   = [Dir]
data Tree a = Leaf | Node a (Tree a) (Tree a)

read :: Path -> Tree a -> Maybe (Tree a)
read []     t = t
read (s:ss) t = case t of
  Leaf       -> Nothing
  Node a l r -> case s of
    L -> read ss l
    R -> read ss r

edit :: Path -> (Tree a -> Tree a) -> Tree a -> Maybe (Tree a)
edit []     f t = Just (f t)
edit (s:ss) f t = case t of
  Leaf       -> Nothing
  Node a l r -> case s of
    L -> do
      l' <- edit ss f l
      return (Node a l' r)
    R -> do
      r' <- edit ss f r
      return (Node a l r')

然后使用此工具,您可以将子树从一个路径"复制并粘贴"到另一个路径

cnp :: Path -> Path -> Tree a -> Maybe (Tree a)
cnp readPath writePath t = do
  subtree <- read readPath t
  edit writePath (const subtree) t

有趣的是,"路径上的子树"形成了一个Lens包含这两个操作之间的共同结构的东西.