How to move a subtree between trees in Haskell?

function, functional-programming, haskell, recursion, types

Solution

You can make edits and reads "at a path" in a 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')

And then using this tool you can "copy and paste" subtrees from one path to another

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

Interestingly, "subtree at path" forms a `Lens` which subsumes the common structure between these two operations.

Problem

For two multi-way trees, t1 and t2, defined using ``` type Forest a = [Tree a] data Tree a = Node { rootLabel :: a, subForest :: Forest a } ``` how can I write a function that will remove a subtree from t1 and insert it at a given node in t2? I imagine the signature would look something like ``` moveSubTree :: ((Tree x a) x (Tree x a)) -> (Tree x Tree) ``` i.e. it takes a tree and parent node defining a subtree to be removed, and a second tree and node that defines the point at which to insert the original subtree. Separate functions to remove and then add the subtree could be composed if necessary.

Original source