CODEWITHSUNDEEP
functionhaskellrecursiontypesfunctional-programming
Rich Ashworth
Rich Ashworth

Reputation: 2015

How to move a subtree between trees in Haskell?

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.

Upvotes: 7

Views: 556

Answers (1)

J. Abrahamson
J. Abrahamson

Reputation: 74354

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.

Upvotes: 9

Related Questions