我想将一个特定的AST节点替换为另一个,并且该替换的节点由交互式用户输入指定。

在非功能编程中,可以使用可变数据结构,并且每个AST节点都有一个对象引用,因此当我需要引用特定节点时,可以使用此引用。

但是在函数式编程中,建议不要使用IORef,因此我需要为每个AST节点生成ID,并且我希望此ID是稳定的,这意味着:


当节点未更改时,生成的ID也不会更改。
更改子节点时,其父节点的ID不会更改。


并且,为了清楚起见,它是一个ID而不是哈希值:


对于比较相等但对应于表达式的不同部分的两个不同子节点,它们应具有不同的id。


那么,我应该怎么做呢?

最佳答案

也许您可以使用从根到节点的路径作为该节点的ID。例如,对于数据类型

data AST = Lit Int
         | Add AST AST
         | Neg AST


你可能会喜欢

data ASTPathPiece = AddGoLeft
                  | AddGoRight
                  | NegGoDown

type ASTPath = [ASTPathPiece]


这满足条件2和3,但是,las总的来说不满足1。例如,如果在先前位置插入节点,则列表索引将发生变化。

如果将AST呈现为另一种格式,则可能可以在结果节点中添加隐藏的属性,以标识导致它们的ASTPathPiece。将结果节点向上遍历到根将使您可以重构ASTPath

关于haskell - 如何在函数式编程中为AST节点生成稳定的ID?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/50960866/

10-12 04:00
查看更多