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

对于两个多路树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)

即，它需要一个树和一个父节点来定义要删除的子树，以及另一个树和节点来定义要插入原始子树的点。

如有必要，可以组成单独的函数来删除然后再添加子树。

最佳答案

您可以进行编辑并在树中读取“在路径上”。

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，它包含了这两个操作之间的 public 结构。

关于function - 如何在Haskell的树之间移动子树？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24723233/