从树中移除（删除）节点

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）

如果要删除某些内容，它必须位于保留了正确值的上下文中，例如列表、集合或映射中的元素。或者您可能想介绍自己的特殊 "null" 值。

这是一个例子。我们给 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 分析中，两个节点需要相同处理的事实通常是最好的 explicit/declarative，而且更常见的是每个节点需要不同的处理。

从树中移除（删除）节点

Remove (delete) node from a tree

rascal