How to move subtree between trees in Haskell?

Question

For two multi-track trees t1 and t2 defined with

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

how can I write a function that removes a subtree from t1 and inserts it into the given node in t2?

I guess the signature will look something like

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

i.e. requires a tree and a parent node that define the subtree to be deleted, and a second tree and node that defines the point at which to insert the original subtree.

If necessary, separate functions can be created for deletion, and then adding a subtree.

Answer 1

You can edit and read "along the way" in the 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 alr -> case s of L -> read ss l R -> read ss r edit :: Path -> (Tree a -> Tree a) -> Tree a -> Maybe (Tree a) edit [] ft = Just (ft) edit (s:ss) ft = case t of Leaf -> Nothing Node alr -> case s of L -> do l' <- edit ss fl return (Node al' r) R -> do r' <- edit ss fr return (Node al r') 

And then with 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, the "subtree along the path" forms a Lens , which includes a common structure between the two operations.