How to replace a subtree with some other tree?

Question

In Scala macro, I want to do something like this:

I have a Tree (possibly large). Now I want to find a subtree of this tree that has some concrete form, e.g. Apply(_, _). And now I want to create a new tree that is a copy of the original tree, but the found subtree is replaced by some other tree.

With something like this, I could for example replace invocation of some method with invocation of some other method.

Is something like this possible?

Answer 1

I'm very interested in seeing alternative approaches to tree transformation, however, they have yet to arrive (and we actually have an ongoing investigation in this direction).

To get things done in the meanwhile, you can extend Transformer, override its transform method and then pattern match against the concrete form of trees you're interested in. Call super.transform to recursively replace in subtrees.

Answer 2

Is it possible??? Definitively Yes!

The general concept is that of "persistent data structures." Those that "persist" as much as possible of the original value in the new variant.

When it comes to trees, the "Zipper" concept is applicable. It lets you navigate into a graph structure while maintaining a data structure that allows the reconstruction of a new value that shares maximally with the original modulo the changes you've applied to create the new variant.

Check it out. Many references can be found, as well as implementations, including ScalaZ.