Re: [scalaz] Tree Grafts/Transplants

[Tony Morris]

TreeLoc#cobind? Or something like it, would have to do some twiddling to figure it out for sure, but I would start there.

On Oct 19, 2012 10:56 AM, "Ryan Watts" <rtwa...@gmail.com> wrote:

I would think this has been done before but I've been looking around for a straightforward solution and haven't come across anything yet.

The problem is this:

I have a Tree[A] and I want to take all the children of a node designated by a certain path P1 and move them to another node designated by path P2.  I want this to be recursive so if the children have children, they are moved as well.

Can anyone point me in the right direction?

--
You received this message because you are subscribed to the Google Groups "scalaz" group.
To view this discussion on the web visit https://groups.google.com/d/msg/scalaz/-/vSSsvUp_OlMJ.
To post to this group, send email to sca...@googlegroups.com.
To unsubscribe from this group, send email to scalaz+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/scalaz?hl=en.

[Runar Bjarnason]

TreeLoc will definitely do this for you. You can use findChild
repeatedly to walk into the tree along a path. Do this with both
paths, then use setTree to replace one with the other.


def walkPath[A](t: Tree[A], path: List[A]): TreeLoc[A] =
path.foldLeft(tree.loc)((t, e) => t.findChild(_.rootLabel == e))

def graft[A](t: Tree[A], p1: List[A], p2: List[A]): Tree[A] =
walkPath(t, p1).setTree(walkPath(t, p2).tree).root


Something like that.

Runar

[Ryan Watts]

Thanks for the help.  I ended up using a slight variation on your code:

def walkPath[A](t: Tree[A], path: List[A]): TreeLoc[A] = 

    path.tail.foldLeft(t.loc)((t, e) => t.findChild(_.rootLabel == e).getOrElse(t))

 

  def graft[A](t: Tree[A], to: List[A], from: List[A]): Tree[A] = 

    walkPath(t, to).insertDownLast(walkPath(t, from).tree).root.tree 

Basically the same except for the getOrElse and turning the graft result into a tree.  In order to get the "transplant" behavior I was hoping for -- i.e. "take this branch and move it here" I had to add one additional method:

def prune[A](t: Tree[A], path: List[A]): Tree[A] = 

    walkPath(t, path).delete.map(_.root.tree).getOrElse(t)

By combining graft and prune I was able to create my transplant method:

def transplant[A](t: Tree[A], to: List[A], from: List[A]): Tree[A] = 

    prune(graft(t, to, from), from)

I will probably change the syntax around a little bit, but that's basically the functionality I was looking for.

Thanks again for the help!