Remove (delete) node from a tree

Question

Is it possible to remove a node from a tree in Rascal? Take the ColoredTree for an example.

How do you write a function deleteNode? For example:

public ColoredTree deleteNode(ColoredTree t){
   return visit(t) {
     case red(l, r) => someProperty ? DELETE : DO NOTHING;   
   };
}

Answer 1

That is interesting.

See the definition of ColoredTree in the example is this:

data ColoredTree = leaf(int N)      
                 | red(ColoredTree left, ColoredTree right) 
                 | black(ColoredTree left, ColoredTree right);

Similar to a Java enum the type ColoredTree can be one of 3 things: a leaf, a red or a black constructor. There is no alternative for "nothing" and Rascal has no "null" (on purpose! see https://en.wikipedia.org/wiki/Tony_Hoare)

If you want to remove something, it must be in a context where a correct value is left over, such as elements in a list, a set or a map. Or you might want to introduce your own special "null" value.

Here is an example. We add an alternative to ColoredTree to represent nothingness:

data ColoredTree = choppedTheBranch();

and now we can rewrite the tree like you proposed:

ColoredTree deleteNode(ColoredTree t){
   return visit(t) {
     case t:red(l, r) => someProperty ? choppedTheBranch() : t;   
   };
}

Although this is more idiomatically written as:

ColoredTree deleteNode(ColoredTree t){
   return visit(t) {
     case t:red(l, r) => choppedTheBranch() when someProperty;
   };
}

A different approach is to use containers such as lists. Here I changed red and black nodes to have a list of children rather than only a left and right child:

data ColoredTree = leaf(int N)      
                 | red(list[ColoredTree] children) 
                 | black(list[ColoredTree] children);

This allows us to remove elements from these lists without destroying the type-correctness of the trees. For example:

ColoredTree deleteNode(ColoredTree t){
   return visit(t) {
     case list[ColoredTree] children => [c | c <- children, !someProperty(c)]
   };
}

I usually make sure to match a context around a list, to avoid accidental matches, like so:

ColoredTree deleteNode(ColoredTree t){
   return visit(t) {
     case red(children) => red([c | c <- children, !someProperty(c)])
     case black(children) => black([c | c <- children, !someProperty(c)])
   };

This example makes it look like a code clone, but in AST analysis often the fact that two nodes require the same treatment is best made explicit/declarative, and more often each node requires a different treatment.