从树中删除（删除）节点

Question

是否可以在Rascal中从树中删除节点？以ColoredTree为例。

您如何编写函数deleteNode？例如：

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

Answer 1

很有趣。

示例中的ColoredTree的定义是这样：

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

与Java枚举类似，类型ColoredTree可以是以下三种内容之一：leaf，red或black构造函数。没有“ nothing”，Rascal没有“ null”（故意！请参见https://en.wikipedia.org/wiki/Tony_Hoare）

如果要删除某些内容，则必须在遗留正确值的上下文中，例如列表，集合或映射中的元素。或者您可能想引入自己的特殊“空”值。

这里是一个例子。我们为ColoredTree添加了替代方法以表示虚无：

data ColoredTree = choppedTheBranch();

现在我们可以像您建议的那样重写树：

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

尽管这在习惯上是这样写的：

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

一种不同的方法是使用诸如列表之类的容器。在这里，我将红色和黑色节点更改为具有子项列表，而不是只有左和右子项：

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

这使我们能够从这些列表中删除元素，而不会破坏树的类型正确性。例如：

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

我通常确保匹配列表周围的上下文，以避免意外匹配，例如：

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)])
   };

此示例使它看起来像是代码克隆，但是在AST分析中，通常最好使两个节点需要相同的处理为显式/声明性的事实，并且通常每个节点都需要不同的处理。